[CERC2016]Invisible Integers

时间限制:80s      空间限制:512MB

题目描述

《隐形的整数》是一个简单的猜数游戏。在这个游戏中,给定n个提示,玩家将尝试去猜一个仅包含自然数1到9的
数字序列,满足所有n个提示。每个提示是一个包含若干互不相同的1到9之间的整数序列,它是这样生成的:
1.随机选择一个序列中的位置作为起点。
2.随机选择任意一个方向,左或者右。
3.从起点开始沿着选定的方向走,遍历完这个方向的每个数字,将每个数字第一次出现的顺序记录下来。
请找到长度最短的满足所有n个提示的序列。


输入格式

第一行包含一个正整数n(1<=n<=10),表示提示的个数。
接下来n行,每行若干个互不相同的1到9之间的整数,依次表示每个提示,每一行以0为终止。


输出格式

输出一行一个整数,即最短长度,若无解则输出-1。


样例输入

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

样例输出

7
一个可行的序列是(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,然后往右走。

提示

没有写明提示


题目来源

没有写明来源

Menuappsclose