문제
정올이의 취미는 고에너지 물리실험을 수행해보는 것인데
최근 실험의 결과로 의도하지 않은 결과를 얻게 되었다.
다름아닌 N( 2 <= N <= 12, 짝수)개의 순간이동 포털이 그의 대지에 만들어진 것이다.
편의상 정올이의 대지를 2차원 평면으로 생각하자.
각 포털은 2차원 평면의 서로 다른 위치에 생성되었다.
정올이의 계산에 따르면 N개의 포털은 N/2개의 쌍들로 이루어지며
각 쌍은 서로의 위치로 순간이동이 가능하다.
다시 말해 A포털과 B포털이 쌍을 이룬다면 A지역에서 B지역으로 또는
B지역에서 A지역으로 순간이동 할 수 있다.
예를 들어 아래 그림과 같이 A포털이 (1, 1)에 있고 B포털이 (5, 1)에 만들어졌고
이 두 포털이 쌍으로 연결되어 있다고 가정하자.
이제 정올이가 (2, 1)에서 출발하여 (5, 1)B포털로 들어가면 (1, 1) A포털로 나오고
A포털에서 나온 후 x값이 증가하는 방향으로 정올이가 전진하면 다시 B포털로 들어가는
일을 무한히 반복하게 된다.
N개의 포털이 주어질 때, 적절히 짝을 지으면 포털을 이동하는 과정이 무한히 반복하게 되는 경우가 생길 수 있다.
정올이는 이러한 경우가 몇 가지가 되는지 알고자 한다.
정올이는 포탈에서 나오면 x가 증가하는 방향으로 진행한다고 한다고 할 때,
무한 반복이 일어나도록 포털에 짝을 짓는 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫 행에 포털의 수 N이 입력된다. (2 <= N <= 12, N은 짝수) 다음 행 부터 N개의 행에 포털의 좌표 xi, yi가 주어진다. (0 <= xi, yi <= 1,000,000)
출력
포털 사이의 이동이 무한히 반복하게 되도록 포털끼리 짝을 짓는 경우의 수를 출력한다.
예제 #1
4
0 0
1 0
1 1
0 1
2
입력 예1의 포털을 순서대로 1, 2, 3, 4번 포털이라 번호를 매기면 아래와 같이 포털이 배치된다.
4 3 1 2
무한 반복이 존재하게 되는 경우는 다음 두 가지이다.
* 한 가지 방법은 1번과 2번을 짝으로 3번과 4번을 짝으로 하는 경우이다. 4번과 3번사이에서 출발하거나 1번과 2번사이에서 출발하면 무한 반복하게 된다.
* 다른 방법은 1번과 3번을 짝으로 4번과 2번을 짝으로 하는 경우이다. 4번과 3번사이에서 출발하거나 1번과 2번사이에서 출발하면 무한 반복하게 된다.
예제 #2
6
2 1
5 1
3 2
1 2
3 3
4 4
6
입력 예2의 포털을 순서대로 1, 2, 3, 4, 5, 6번 포털이라 번호를 매기면 아래와 같이 포털이 배치된다.
6 5 4 3 1 2
이제 다음과 같이 짝을 지으면 무한 반복하는 경우가 존재한다.
* 1번-2번 포털, 3번-4번 포털, 5번-6번 포털을 짝으로 하는 경우 : 1번과 2번 사이 또는 3번과 4번 사이에서 출발하면 무한 반복한다.
* 1번-2번 포털, 3번-5번 포털, 4번-6번 포털을 짝으로 하는 경우 : 1번과 2번 사이에서 출발하면 무한 반복한다.
* 1번-2번 포털, 3번-6번 포털, 4번-5번 포털을 짝으로 하는 경우 : 1번과 2번 사이에서 출발하면 무한 반복한다.
* 3번-4번 포털, 1번-5번 포털, 2번-6번 포털을 짝으로 하는 경우 : 3번과 4번 사이에서 출발하면 무한 반복한다.
* 3번-4번 포털, 1번-6번 포털, 2번-5번 포털을 짝으로 하는 경우 : 3번과 4번 사이에서 출발하면 무한 반복한다.
* 1번-3번 포털, 2번-4번 포털, 5번-6번 포털을 짝으로 하는 경우 : 1번과 2번 사이 또는 3번과 4번 사이에서 출발하면 무한 반복한다.
로그인해야 코드를 작성할 수 있어요.