시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 61 23 19 45.238%

문제

은진이는 도미노 게임을 좋아한다. 도미노는 직사각형 모양이고, 두 개의 정사각형으로 나누어져 있다. 그리고, 각 정사각형에는 0보다 크거나 같고, 9보다 작거나 같은 정수가 하나 써 있다. 따라서, 가능한 모든 조각은 45조각이다. 조각은 뒤집을 수도 있어서, 숫자 1과 2가 포함된 조각은 다음과 같이 하나이다.

안타깝게도, 장엄지가 조각 몇 개를 가지고 가버렸다. 따라서, 은진이는 은진이답게 남은 도미노 조각을 가지고 할 수 있는 게임을 생각했다. 바로 “남은 도미노 조각을 가지고 사이클 콜렉션을 만들 수 있을까?” 이다.

사이클 콜렉션이란, 조각을 공유하지 않는 1개 또는 그 이상의 사이클이 모인 집합이다. 사이클은 i번째 놓인 조각의 왼쪽 번호와 i-1번째 놓인 조각의 오른쪽 번호가 같은 것 끼리 배열한 것이다. 그리고, 가장 처음에 놓은 조각의 왼쪽 번호와 가장 마지막에 놓은 조각의 오른쪽 번호도 같아야 한다.

위의 그림은 같은 조각의 집합을 가지고 만들 수 있는 세 가지 사이클 콜렉션이다.


조각이 연결되어 있다는 말은, 조각을 둘러 싸고 있는 두 조각과 연결되어 있는 것이다. 물론, 처음 조각과 마지막 조각도 연결되어 있는 것이다.

두 사이클이 같다는 말은 각 조각이 두 사이클에서 같은 조각과 연결되어 있을 때이고, 두 사이클 콜렉션이 같다는 말은, 같은 사이클의 집합을 포함할 때이다.

남은 조각이 주어질 때, 사이클 콜렉션을 총 몇 개 만들 수 있는지 구하는 프로그램을 작성하시오. 조각은 모두 사용해야 한다.

입력

첫째 줄에 조각의 개수 N (1 ≤ N ≤ 45)이 주어진다. 둘째 줄부터 N개의 줄에는 각 조각이 주어진다. 조각은 2개의 숫자로 되어 있고, 앞에 있는 숫자는 항상 뒤에 있는 숫자보다 작다. 조각은 중복되지 않는다.

출력

첫째 줄에 만들 수 있는 사이클 콜렉션의 개수를 출력한다. 이 값은 2^63보다 작다.

예제 입력

6
12
25
45
24
28
18

예제 출력

3

예제 입력 2

7
09
12
24
14
57
79
05

예제 출력 2

1

힌트

출처