Starred-Transferred

건축가 제이크는 우주 배달 사업에서 영감을 얻어 스타트업을 창업하였다. 제이크는 우주에 $N$개의 비콘을 설치하여 $N+2$개의 단말 행성 사이에서 택배를 배달하려고 한다. 비콘과 단말 행성 사이의 네트워크 구성은 처음 구축할 때 고정되며, 이후 바뀌지 않는다. 편의상 모든 비콘과 단말 행성을 노드라고 부르자. 이 네트워크는 다음 규칙을 만족한다.

• 모든 비콘은 정확히 3개의 노드와 직접 연결되어야 한다.
• 모든 단말 행성은 정확히 하나의 비콘과 직접 연결되어야 한다.
• 네트워크는 모든 노드를 직접 또는 간접적으로 연결해야 한다.

제이크는 단말 행성에 $-(N+2)$ 이상 $-1$ 이하의 정수 번호를, 비콘에 $0$ 이상 $N-1$ 이하의 정수 번호를 붙였다. 비콘과 단말 행성 사이에서 가능한 네트워크 구성의 예는 아래 그림과 같다.

우주 공간에 있는 $N$개의 비콘은 가끔 암흑 물질의 영향을 받아 택배 서비스 성능이 다소 불안정해질 수 있다. 그래서 제이크는 다음과 같이 작동하는 프로토콜을 설계하였다.

• 비콘 $i$($0 \leq i < N$)에 연결된 노드의 번호를 $C_i[0]$, $C_i[1]$, $C_i[2]$라고 하자.
• 각 비콘마다 정책 $R_i[0]$, $R_i[1]$, $R_i[2]$를 $0$ 이상 $2$ 이하의 정수로 미리 정한다. $R_i[j]$는 $j$와 달라야 한다.
• 모든 단말 행성에서 비콘으로 편지를 한 장씩 배달한다.
• 노드 $C_i[j]$($0 \leq j \leq 2$)에서 비콘 $i$로 편지가 왔다고 하자. 비콘 $i$가 암흑 물질의 영향을 받고 있다면 그 편지를 노드 $C_i[R_i[j]]$로 보낸다. 그렇지 않다면 노드 $C_i[3 - j - R_i[j]]$로 보낸다.
• 편지가 단말 행성에 도착하면 배달이 끝난다.

제이크는 정책 $R$을 적절히 정하면, 각 단말 행성에 도달하는 편지의 수만 확인해도 $N$개의 비콘이 암흑 물질의 영향을 받고 있는지 알 수 있다고 생각하는 것 같다. 이 생각이 맞는지 프로그램으로 확인해 보자.