藍橋杯模拟賽:滑動解鎖

題目：滑動解鎖

滑動解鎖是智能手機一項常用的功能。你需要在3x3的點陣上，從任意一個點開始，反複移動到一個尚未經過的”相鄰”的點。這些劃過的點所組成的有向折線，如果與預設的折線在圖案、方向上都一緻，那麼手機将解鎖。

所謂兩個點“相鄰”：當且僅當以這兩個點為端點的線段上不存在尚未經過的點。

此外，許多手機都約定：這條折線還需要至少經過4個點。

為了描述友善，我們給這9個點從上到下、從左到右依次編号1-9。即如下排列：

1 2 3

4 5 6

7 8 9

那麼1->2->3是非法的，因為長度不足。

1->3->2->4也是非法的，因為1->3穿過了尚未經過的點2。

2->4->1->3->6是合法的，因為1->3時點2已經被劃過了。

某大神已經算出：一共有389112種不同的解鎖方案。沒有任何線索時，要想暴力解鎖确實很難。

不過小Hi很好奇，他希望知道，當已經瞥視到一部分折線的情況下，有多少種不同的方案。

遺憾的是，小Hi看到的部分折線既不一定是連續的，也不知道方向。

例如看到1-2-3和4-5-6，

那麼1->2->3->4->5->6，1->2->3->6->5->4, 3->2->1->6->5->4->8->9等都是可能的方案。

你的任務是編寫程式，根據已經瞥到的零碎線段，求可能解鎖方案的數目。

輸入：

每個測試資料第一行是一個整數N(0 <= N <= 8)，代表小Hi看到的折線段數目。

以下N行每行包含兩個整數 X 和 Y (1 <= X, Y <= 9)，代表小Hi看到點X和點Y是直接相連的。

輸出：

對于每組資料輸出合法的解鎖方案數目。

例如：

8

1 2 2 3

3 4 4 5

5 6 6 7

7 8 8 9

程式應該輸出：

2

再例如：

4

2 4

2 5

8 5

8 6

258