정올이의 취미는 고에너지 물리실험을 수행해보는 것인데

최근 실험의 결과로 의도하지 않은 결과를 얻게 되었다.

다름아닌 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가 증가하는 방향으로 진행한다고 한다고 할 때,

무한 반복이 일어나도록 포털에 짝을 짓는 경우의 수를 구하는 프로그램을 작성하시오.

순간이동(Wormholes) timer 1s memory 256MB

순간이동(Wormholes) 1s 256MB