Hippy Commune

Statement

Goal

A commune with N hippies wants to figure out the minimum number of beds needed to accommodate everyone. Each bed holds a maximum of three people, and each hippy lists the names of everyone they are willing to share a bed with.

Input

First line: Number of hippies.
Next N lines: String with a hippy name, followed by the names of everyone they are willing to sleep with (always at least one).

Output

The minimum number of beds needed.

Constraints

3 ≤ N ≤ 1000

Example

Input

5
Moonbeam Jerry Gary Saffron
Jerry Moonbeam
Saffron Moonbeam
Gary Jerry Saffron
Steve Gary Saffron Jerry Moonbeam

Output

Tags

Difficulty

Medium

Test cases

Test 1 Test

Input

5 Moonbeam Jerry Gary Saffron Jerry Moonbeam Saffron Moonbeam Gary Jerry Saffron Steve Gary Saffron Jerry Moonbeam

Output

Validator 1 Validator

Input

8 Moonbeam Jerry Gary Saffron Sam Harry Lee Jerry Moonbeam Sam Harry Lee Saffron Moonbeam Sam Harry Lee Gary Jerry Saffron Sam Harry Lee Steve Gary Saffron Jerry Moonbeam Sam Harry Lee Sam Gary Saffron Jerry Moonbeam Harry Gary Saffron Jerry Moonbeam Lee Gary Saffron Jerry Moonbeam

Output

Test 2 Test

Input

5 Moonbeam Jerry Gary Saffron Jerry Moonbeam Saffron Moonbeam Gary Jerry Saffron Steve Gary Saffron Jerry Moonbeam

Output

Validator 2 Validator

Input

5 Moonbeam Jerry Gary Saffron Jerry Moonbeam Saffron Moonbeam Gary Jerry Saffron Steve Gary Saffron Jerry Moonbeam

Output

Test 3 Test

Input

5 Moonbeam Jerry Gary Saffron Jerry Moonbeam Saffron Moonbeam Gary Jerry Saffron Steve Gary Saffron Jerry Moonbeam

Output

Validator 3 Validator

Input

5 Moonbeam Jerry Gary Saffron Jerry Moonbeam Saffron Moonbeam Gary Jerry Saffron Steve Gary Saffron Jerry Moonbeam

Output

Test 4 Test

Input

5 Moonbeam Jerry Gary Saffron Jerry Moonbeam Saffron Moonbeam Gary Jerry Saffron Steve Gary Saffron Jerry Moonbeam

Output

Validator 4 Validator

Input

5 Moonbeam Jerry Gary Saffron Jerry Moonbeam Saffron Moonbeam Gary Jerry Saffron Steve Gary Saffron Jerry Moonbeam

Output

Solution language

Solution

Stub generator input