hyperopia

There is a forest with $N$ labeled vertices in Ddasland. The vertices are numbered $1,2,\cdots,N$. One Ddas stands on each vertex.

The Ddas standing on vertex $v$ cannot see any edge incident to $v$. They can see every other edge and all vertex labels. Every Ddas knows the following facts.

• The given graph is a forest.
• Every Ddas reasons perfectly logically.
• Every Ddas knows that every other Ddas reasons perfectly logically. This fact is common knowledge.

One day, Dadas publicly announces the following fact to everyone.

This forest contains at least one edge.

The days are then numbered starting from day $1$. On every day, all Ddases simultaneously make exactly one of the following public declarations using all declarations from earlier days.

• They know that at least one edge is incident to their vertex.
• They cannot determine whether an edge is incident to their vertex.

A declaration made by another Ddas on the same day cannot be used on that day. Every declaration becomes public information on later days.

The actual forest is given. Find the first day on which some Ddas knows that at least one edge is incident to their vertex.

The input is given from Standard Input in the following format:

$T$ case$_1$ case$_2$ $$

For each test case, print the first day satisfying the condition on one line.

• $1 \leq T \leq 200$.
• $2 \leq N \leq 200\,000$.
• $1 \leq M \leq N-1$.