웜홀

농부 존이 주말마다 즐기던 고에너지 물리 실험이 역효과를 내는 바람에 농장에 웜홀 $N$개가 생겼다 ($2 \le N \le 12$, $N$은 짝수). 웜홀은 농장 2차원 지도 위의 서로 다른 점에 하나씩 놓여 있다.

존의 계산에 따르면 웜홀은 $N/2$개의 쌍으로 연결된다. 웜홀 A와 B가 한 쌍이면 A로 들어간 물체는 B에서 같은 방향으로 나오고, B로 들어간 물체는 A에서 같은 방향으로 나온다. 이 성질은 꽤 성가신 결과를 낳는다. 예를 들어 $(0,0)$의 웜홀 A와 $(1,0)$의 웜홀 B가 한 쌍이고, 소 베시가 $(1/2, 0)$에서 $+x$ 방향으로 출발한다고 하자. 베시는 B로 들어가 A로 나오고, 다시 B로 들어가기를 끝없이 반복하며 무한 순환에 갇힌다.

존은 웜홀의 위치를 모두 알고 있고, 베시가 언제나 $+x$ 방향으로 걷는다는 것도 안다. 다만 베시가 지금 어디에 있는지는 기억하지 못한다. 베시가 운 나쁜 지점에서 출발하면 무한 순환에 갇힐 수 있는 짝짓기가 몇 가지인지 세어라. 쌍의 구성이 하나라도 다르면 서로 다른 짝짓기로 센다.

• 첫째 줄에 웜홀의 개수 $N$이 주어진다.
• 다음 $N$개 줄에는 웜홀 하나의 $x$ 좌표와 $y$ 좌표가 공백을 사이에 두고 주어진다. 두 좌표 모두 0 이상 1,000,000,000 이하의 정수다.

첫째 줄에 베시가 어떤 지점에서 $+x$ 방향으로 걷기 시작했을 때 순환에 갇힐 수 있는 짝짓기의 수를 출력한다.

웜홀 네 개가 정사각형의 꼭짓점 $(0,0)$, $(1,0)$, $(1,1)$, $(0,1)$에 이 순서대로 놓여 1번부터 4번까지 번호가 붙은 경우를 보자. 1번과 2번, 3번과 4번을 짝지으면 베시는 $(0,0)$과 $(1,0)$ 사이 또는 $(0,1)$과 $(1,1)$ 사이 어디에서 출발해도 갇힌다. 1번과 3번, 2번과 4번을 짝지어도 같은 출발점에서 갇힌다. 1번과 4번, 2번과 3번을 짝지은 경우에만 베시가 평면 위 어느 점에서 출발하든 순환 없이 $+x$ 방향으로 계속 걸어갈 수 있다.