“隐形整数”是一个简单的游戏，玩家需要根据给出的若干提示，猜出一个由 1 到 9 之间的整数组成的隐藏序列。每个提示都是一个由不同整数组成的序列，生成方式如下：

• 在隐藏序列中选择一个任意起始位置。
• 选择一个任意方向——向左或向右。
• 从选定的位置开始，沿选定方向遍历隐藏序列中的所有整数。将遍历到的整数追加到提示的末尾，如果该整数已在提示中出现，则跳过。

求出符合给定提示的最短隐藏序列的长度。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10$)，表示提示的数量。接下来的 $n$ 行，每行包含一个提示。每个提示是一个包含至少 1 个、至多 9 个不同整数的序列，这些整数在 1 到 9 之间（包含 1 和 9），并以整数 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

输入 2

3
1 2 0
2 3 0
3 4 0

输出 2

-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 个元素开始向右遍历得到。