T4 怪盗德基

题目信息

时间限制: 1s

空间限制: 512M

输入文件: hidden.in

输出文件: hidden.out

题目描述

东洋国有 $9$ 个国家博物馆，编号是 $1\sim 9$。公元 3202 年，怪盗德基在东洋国的 $9$ 大国家博物馆犯下全国震惊的盗窃案，并扬言没有人能在犯罪现场捉到他。德基声称，他会在 3203 年按照一个特定的盗窃序列造访 $9$ 大国家博物，盗窃顺序由以下 $n$ 条线索生成：

1. 选择序列的某一个位置 $p$ 作为开始；
2. 选择某个方向（序列中位置 $p$ 开始向左或向右）；
3. 从 $p$ 出发往选择的方向，每遇到一个之前未出现过的国家博物馆，就将该博物馆的编号加入线索中。

名侦探南柯希望破译怪盗德基的盗窃序列，那么怪盗德基的盗窃序列的最小长度是多少呢？

输入格式

第一行一个整数 $n$，表示线索的数量。

接下来 $\mathrm{n}$ 行，每行有若干个以 $0$ 结尾的整数，表示一条线索。保证一条线索中的数在 $[1,9]$ 中且不会出现相同的数。

输出格式

如果无解请输出 $-1$，否则输出盗窃序列可能的最小长度。

样例

样例输入 1

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

样例输出 1

7

样例输入 2

3
1 2 0
2 3 0
3 4 0

样例输出 2

-1

数据范围与提示

• 对于 $20 \%$ 的数据，答案不超过 $10$。
• 对于另外 $40 \%$ 的数据，保证存在一个最优解，使得所有线索都可以通过向右遍历得到。
• 对于 $100 \%$ 的数据，$1 \leqslant n \leqslant 10$。