고슴도치 그래프 2

이 문제는 인터랙티브 문제입니다.

고슴도치 귀엽지 않나요?

귀여운 고슴도치!

키파는 "성게 그래프"도 만들었는데, 이렇게 귀여운 고슴도치에 대응하는 그래프가 없는 것은 말이 안 된다고 생각해서 고슴도치 그래프를 만들기로 했습니다.

고슴도치 그래프는 다음 두 가지 성질을 만족하는 방향 없는 연결 그래프입니다. 이 그래프에는 self-loop(정점 $v$를 자기 자신과 잇는 간선)와 multiedge(서로 다른 두 정점 $v$와 $w$를 잇는 서로 다른 간선 $e_{1}$과 $e_{2}$)가 없습니다.

• 사이클이 정확히 하나 있습니다. 이 사이클을 고슴도치의 몸통이라고 합니다. 몸통의 크기는 사이클에 속한 정점의 개수입니다. 사이클은 항상 존재하므로 몸통의 크기는 항상 $3$ 이상입니다.
• 사이클에 속하지 않은 정점의 차수는 $1$입니다.

키파는 고슴도치 그래프를 열심히 키운 결과, 정점이 $V = 10^{6}$개인 고슴도치 그래프를 총 $N$개 가지게 되었습니다. 키파는 각 고슴도치 그래프를 다음 방법으로 쓰다듬기로 했습니다.

1. 각 노드에 붙은 간선의 방향을 정하되, 모든 노드가 나가는 방향의 간선을 정확히 하나씩 갖도록 합니다. 임의의 고슴도치 그래프에 대해 이 조건을 만족하도록 방향을 정하는 것이 항상 가능함을 증명할 수 있습니다.
2. 다음을 최대 $M = 900$번 반복합니다.
   1. 정점 $v$와 $5 \times 10^{18}$ 이하의 임의의 양의 정수 $x$를 고릅니다.
   2. $v$에서 화살표를 $x$번 따라가며 고슴도치 그래프를 쓰다듬습니다. 모든 노드가 나가는 간선을 하나씩 가지므로 도착 노드는 하나로 정해지고, 그 노드가 어디인지 알 수 있습니다.

과정 1의 방향은 키파가 이미 임의로 정했습니다.

키파는 고슴도치 그래프를 쓰다듬는 것뿐 아니라 각 고슴도치 그래프의 몸통 크기도 알고 싶어 합니다. 하지만 키파는 이것까지 생각하기에는 머리가 너무 아팠기 때문에, 과정 2를 여러분에게 맡기기로 했습니다.

여러분은 각 고슴도치 그래프에 대해 과정 2를 실행한 뒤 얻은 정보로 각 고슴도치의 몸통 크기를 알아내야 합니다.

첫째 줄에 $10$ 이하의 양의 정수 $N$이 주어집니다. 그 뒤로 인터랙션이 시작됩니다.