Description

“Invisible Integers” is a simple number-guessing game. In this game, given $n$ hints, the player tries to guess a sequence consisting only of the digits 1 to 9, such that all $n$ hints are satisfied. Each hint is a sequence of pairwise distinct integers between 1 and 9, generated as follows:

1. Randomly choose a position in the sequence as the starting point.
2. Randomly choose a direction, either left or right.
3. Starting from the chosen position and moving along the chosen direction to the end, record, in order, the first time each digit is seen.

Find a sequence of minimum length that satisfies all $n$ hints.

Input Format

The first line contains a positive integer $n$ ($1 \le n \le 10$), the number of hints.

Each of the next $n$ lines contains a hint: several pairwise distinct integers between 1 and 9, terminated by a 0.

Output Format

Output a single integer: the minimum possible length. If there is no solution, output $-1$.

5
1 2 0
3 4 0
1 4 3 0
3 1 4 2 0
1 2 4 3 0

7

Hint

One feasible sequence is (1, 2, 1, 4, 1, 3, 4).

For the hint (1, 2), you can choose position 3 and then walk to the left.

For the hint (3, 4), you can choose position 6 and then walk to the right.

For the hint (1, 4, 3), you can choose position 3 and then walk to the right.

For the hint (3, 1, 4, 2), you can choose position 6 and then walk to the left.

For the hint (1, 2, 4, 3), you can choose position 1 and then walk to the right.

Translated by ChatGPT 5