고슴도치 그래프

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

고슴도치 귀엽지 않나요?

귀여운 고슴도치!

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

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

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

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

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

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

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

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

고슴도치 그래프

문제

입력