Hedgehog Graph 2

This is an interactive problem.

Isn't a hedgehog cute?

A cute hedgehog!

Kipa also has the "sea urchin graph," but it makes no sense for there to be no graph matching such a cute hedgehog. So Kipa decided to make the hedgehog graph.

A hedgehog graph is an undirected connected graph that satisfies the following two properties. It has no self-loops (an edge connecting a vertex $v$ to itself) and no multiedges (distinct edges $e_{1}$ and $e_{2}$ connecting the same two distinct vertices $v$ and $w$).

• There is exactly one cycle. This cycle is called the body of the hedgehog. The size of the body is the number of vertices on the cycle. A cycle always exists, so the body size is always at least $3$.
• Every vertex not on the cycle has degree $1$.

Kipa raised many hedgehog graphs, and now has $N$ hedgehog graphs, each with $V = 10^{6}$ vertices. Kipa decided to pet each hedgehog graph in the following way.

1. Orient every edge so that each vertex has exactly one outgoing edge. It can be proven that such an orientation always exists for any hedgehog graph. Kipa has already chosen the orientations arbitrarily, so this step is done.
2. Repeat the following up to $M = 900$ times.
   1. Choose a vertex $v$ and a positive integer $x$ at most $5 \times 10^{18}$.
   2. Starting from $v$, follow the arrows $x$ times to pet the hedgehog graph. Since every vertex has exactly one outgoing edge, the endpoint is uniquely determined, and you can find out which vertex it is.

Kipa wants to know the body size of each hedgehog graph, not just pet them. Kipa finds this too hard to figure out, so the second step is left to you.

You must find the body size of each hedgehog graph from the information you get after running step 2 on it.

The first line contains a positive integer $N$ at most $10$. The interaction starts after that.