P3685 [CERC2016] Invisible Integers

“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.

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 a single integer: the minimum possible length. If there is no solution, output $-1$.

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