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

内存限制:512 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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

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

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

输入格式

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

输出格式

如果无解请输出 -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

样例解释 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 个元素向右遍历得到;

样例输入 2

3
1 2 0
2 3 0
3 4 0

样例输出 2

-1

数据范围与提示

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