405099: GYM101790 I Key brute forcing

The phone lock screen consists of 9 numbered dots arranged in three rows three pieces each.

The unlock key is a sequence of two or more non-repeating dots. The segments between adjacent dots in the unlock key can not pass through another dot. Thus, in the unlock keys, the following pairs of points can not be adjacent (in any order): {1, 3}, {4, 6}, {7, 9}, {1, 7}, {2, 8}, {3, 9}, {1, 9}, {3, 7}.

On the phone screen between segments of the dots are visible segments with fingerprints, which means that such a pair of dots should be present in the unlock key, and they should be adjacent.

Determine how many unlock keys exist that satisfy the condition of the task. It is guaranteed that the answer will not be zero.

The first line contains the number of segments with traces from the finger N (0 ≤ N ≤ 8).

Each of the next N lines contains two integers A_i and B_i (1 ≤ A_i, B_i ≤ 9), denoting the i-th segment between two number dots.

Display one integer: the number of unlock keys.

6
1 8
8 7
7 5
4 5
2 4
2 6

6

4
3 5
5 2
2 6
6 1

110

Segments from first sample are shown at the picture. Suitable keys are: 1875426, 18754263, 18754269, 36245781, 6245781, 96245781.