Invisible Integers

Time limit5sMemory limit512 MB

Summary

Given up to 10 hints, each a walk order of distinct digits 1 to 9, find the shortest hidden integer sequence that can produce every hint.

Level: Hard8 of 10
Topics: Backtracking, DFS, Implementation, Brute force
Solved: No attempts yet

Problem

Invisible integers is a guessing game. A player reconstructs a hidden sequence of integers between 1 and 9 from a few hints. Each hint is a sequence of distinct integers, built like this.

Pick a starting position in the hidden sequence.
Pick a direction, either left or right.
Starting at the chosen position, walk through the integers of the hidden sequence in the chosen direction until you leave the sequence. Append every integer you meet to the end of the hint, skipping the integers already in the hint.

Find the length of the shortest hidden sequence consistent with all the given hints.

Input

The first line contains an integer $n$ ( $1 \le n \le 10$ ), the number of hints. Each of the next $n$ lines contains one hint: at least 1 and at most 9 distinct integers between 1 and 9, separated by spaces and terminated by the integer 0.

Output

Print -1 if no sequence is consistent with all the hints. Otherwise print a single integer, the length of the shortest such sequence.

Note

In the first example, $(1, 2, 1, 4, 1, 3, 4)$ is one shortest sequence consistent with the given hints.

Hint $(1, 2)$ comes from starting at the 3rd element and heading left.
Hint $(3, 4)$ comes from starting at the 6th element and heading right.
Hint $(1, 4, 3)$ comes from starting at the 3rd element and heading right.
Hint $(3, 1, 4, 2)$ comes from starting at the 6th element and heading left.
Hint $(1, 2, 4, 3)$ comes from starting at the 1st element and heading right.

Examples2

Example 1

Input

Expected output

Example 2
Input
```
3
1 2 0
2 3 0
3 4 0
```
Expected output
```
-1
```