TimeLimit:1000MS  MemoryLimit:128MB

64-bit integer IO format:%I64D

Problem Description

欲知前情如何，请看第十届福建工程学院校赛赛题。

 

小A和小C正在私奔的路上，遇到一个前来追赶他们的特工，然而这个特工明显是个临时工，三下五除二就把特工打晕了，缴获了一部手机。小A和小C想要通过这个特工的手机获取情报，而这台手机有图案密码锁。大概由于这个特工比较健忘，手机的密码提示写了一排数字，小A根据数字滑动密码锁，却不能打开。

小C说：“是不是要换个顺序才能打开？”

小A觉得很有道理，但是这个情况数好像很多的样子，然而小A是个聪明的程序员，他有足够的信心破解这个手机图案密码。

现在小A已经知道手机图案锁是只由哪几个位置组成的,手机图案锁的解锁只能通过一笔画解决,他最多需要多少次情况就一定能够破解该图案锁的密码？每个位置必须经过，每个位置只能够被经过一次。

 

图案锁的组成有9个位置分别为：

1    2    3

4    5    6

7    8    9

如上图所示：

会提示你密码包含1，2，3，4，5，6，7，8，9.

其中的一种画法如上图：5->4->2->6->7->1->9->8->3.

经过小A多次研究，发现以下规律：

如果你还没有经过5, 然后 你连接了1, 再去连接9的话, 则会经过5.

如果你已经经过5, 然后你连接1, 再去连接9的话, 则不会在重新经过5.

同理可得1和3、4和6等也满足如上规律。

Input

有多组测试案例.
每一组测试案例的第一行输入一个整数N(1<=N<=9),表示图案锁由N个密码组成。
接下来输入N个数值，表示这N密码的位置。

Output

输出最多需要多少次便能够解锁，如果不能够解锁，请输出-1。

SampleInput

1

1

2

1 9

2

1 5

3

1 5 9

SampleOutput

1

-1

2

4
题意：一个n,然后n个数字。代表密码包含的数字，算出所有密码的组合就是答案，答案是全排列减去不符合的情况。
思路：典型的深搜。为什么呢？假如密码为1,5,9。那么第一个数字可能是1,5，或9，然后他们有分别对应不同的第二步。但又不是简单的排列，
因为如果某一次选择1，那么在5没有选之前不能选9.这样我们可以画出一颗树状图，递归遍历所有情况，当走到头的时候计数器加以，最后输出计数器，
计数器为0是输出-1.典型的深搜。我们可以用深搜模拟选择密码，在遇到不符合条件的组合不选即可。

标号【1】的部分代码加上可以看见你选了那些数字。dfs舍去了不符合组合减去的函数。挺简单的自己写下。暴力就学我，16个if ╮(╯▽╰)╭
大概这样
然后学长的判断是这样写的

比如1的坐标是（1,1）,9的坐标是（3,3）
他们的中点是(2,2)，所以检查一下在（2,2）上的5