고슴도치 그래프 2

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

고슴도치 귀엽지 않나요?

귀여운 고슴도치!

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

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

사이클이 정확히 하나 존재합니다. 이 사이클을 고슴도치의 몸통이라고 부르겠습니다. 몸통의 크기는 사이클에 속한 정점의 개수입니다. 사이클이 항상 존재하기 때문에 몸통의 크기는 항상 $3$ 이상이라는 점에 유의하세요.
사이클에 속하지 않은 정점의 차수가 $1$입니다.

키파는 고슴도치 그래프를 열심히 키운 결과 각 그래프가 $V = 10^{6}$개의 정점으로 이루어진 고슴도치 그래프를 총 $N$개 가지게 되었습니다. 키파는 각 고슴도치 그래프를 다음과 같은 방법으로 어루만져 주기로 했습니다.

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

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

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

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

고슴도치 그래프 2

문제

입력