보이지 않는 정수

보이지 않는 정수는 힌트 몇 개만 보고 숨겨진 수열을 알아맞히는 놀이다. 숨겨진 수열은 1부터 9까지의 정수로 이루어진다. 각 힌트는 서로 다른 정수의 수열이고, 다음 방법으로 만든다.

• 숨겨진 수열에서 시작 위치를 하나 고른다.
• 방향을 하나 고른다. 왼쪽 또는 오른쪽이다.
• 고른 위치에서 출발해 고른 방향으로 숨겨진 수열의 끝까지 정수를 차례로 따라간다. 따라가며 만난 정수를 힌트 뒤에 덧붙이되, 이미 힌트에 들어 있는 정수는 건너뛴다.

주어진 힌트를 모두 만족하는 숨겨진 수열 중 가장 짧은 것의 길이를 구하라.

첫째 줄에 힌트의 개수 $n$이 주어진다 ($1 \le n \le 10$). 다음 $n$개 줄에 힌트가 한 줄에 하나씩 주어진다. 각 힌트는 1 이상 9 이하의 서로 다른 정수를 1개 이상 9개 이하 공백으로 구분해 나열하고, 마지막에 정수 0을 붙인 것이다.

모든 힌트를 만족하는 수열이 없으면 -1을 출력한다. 있으면 그런 수열 중 가장 짧은 것의 길이를 정수 하나로 출력한다.

첫 번째 예제에서 $(1, 2, 1, 4, 1, 3, 4)$는 주어진 힌트를 모두 만족하는 가장 짧은 수열 중 하나다.

• 힌트 $(1, 2)$는 3번째 원소에서 출발해 왼쪽으로 가면 나온다.
• 힌트 $(3, 4)$는 6번째 원소에서 출발해 오른쪽으로 가면 나온다.
• 힌트 $(1, 4, 3)$은 3번째 원소에서 출발해 오른쪽으로 가면 나온다.
• 힌트 $(3, 1, 4, 2)$는 6번째 원소에서 출발해 왼쪽으로 가면 나온다.
• 힌트 $(1, 2, 4, 3)$은 1번째 원소에서 출발해 오른쪽으로 가면 나온다.