Problem1394--#6037. 「雅礼集训 2017 Day4」猜数列

1394: #6037. 「雅礼集训 2017 Day4」猜数列

Time Limit: 5 Sec  Memory Limit: 512 MB
Submit: 1  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

有一个长度为 m m m 的,由 1 1 19 9 9 之间的数构成的未知数列 am a_m am

你现在有 n n n 个线索,每个线索都是用如下方式生成的:

  • 选择序列 am a_m am 的某一个位置 p p p 作为开始;
  • 选择某个方向(向左或向右);
  • p p p 出发往你选择的方向走,每遇到一个之前未出现的数就将它加到线索中。

(可以发现,每条线索的长度都不超过 9 9 9。)
现在你需要求出满足所有线索的长度最小的序列的长度。

Input

第一行一个整数 n n n,表示线索的数量。
接下来 n n n 行,每行有若干个以 0 0 0 结尾的整数,表示一条线索。

Output

如果无解请输出 −1 -1 1,否则输出可能的最小长度。

Sample Input Copy

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

Sample Output Copy

7

HINT

对于 20% 20\% 20% 的数据,答案不超过 10 10 10
对于另外 40% 40\% 40% 的数据,保证存在一个解,使得所有线索都可以通过从某个位置向右遍历得到;
对于 100% 100\% 100% 的数据,1≤n≤10 1 \leq n \leq 10 1n10

Source/Category