Starred-Transferred

건축가 제이크는 우주 배달 사업에 대하여 영감을 얻어 스타트업 스타티링크(Star-T-Link)를 창업하였다. 제이크는 우주에 $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$와 달라야 한다.
• 모든 단말 행성에서 비콘으로 편지 각 $1$장을 배달한다.
• $C\_i \[j]$($0 \leq j \leq 2$)번 노드에서 비콘 $i$로 온 편지가 있다고 하자. $i$번 비콘이 암흑 물질의 영향을 받고 있다면 해당 편지를 $C\_i \[R\_i \[j]]$번 노드로 보내고, 그렇지 않다면 해당 편지를 $C\_i \[3 - j - R\_i \[j]]$번 노드로 보낸다.
• 편지가 단말 행성에 도착한다면 배달이 끝난다.

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