시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 93 43 34 53.125%

문제

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

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

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

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


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

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

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

입력

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

출력

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

예제 입력 1

6
12
25
45
24
28
18

예제 출력 1

3

예제 입력 2

7
09
12
24
14
57
79
05

예제 출력 2

1

출처