#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Cute Game on Graph - Repovive Premier Round 3 | Repovive

6D. Cute Game on Graph

2000 pts2s256 MB

Alice and Bob are playing a game on a simple undirected graph with $n$ vertices labeled from $1$ to $n$ and $m$ edges. Initially, a token is placed on vertex $1$ .

They play in turns, and Alice plays first. In each turn:

Alice chooses one edge of the graph and marks it.
Then Bob may either keep the token on its current vertex, or move the token along one unmarked edge to an adjacent vertex.
After Bob's choice, the marked edge becomes unmarked again.

Bob may end the game at any moment, including before the first turn. When the game ends, the label of the vertex containing the token is called the outcome.

Alice wants the outcome to be as small as possible. Bob wants the outcome to be as large as possible. Both players play optimally.

For each test case, determine the largest possible outcome that Bob can guarantee.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \cdot 10^5$
$0 \le m \le 2 \cdot 10^5$
The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .
The sum of $m$ over all test cases does not exceed $2 \cdot 10^5$ .

Input

t

\left. \begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

1 0

Case 2

Case 3

Case 4

Case 5

Explanation

Case 1

The token starts on the only vertex, so Bob can end the game immediately and get outcome $1$ .

Case 2

The graph is a path. Whenever Bob is at vertex $1$ , Alice can mark the only edge leaving it. Therefore Bob cannot guarantee reaching a larger label, and the answer is $1$ .

Case 3

Alice can mark only one of the two edges leaving vertex $1$ . Bob can move through the other one and guarantee an outcome of at least $2$ . However, Alice can stop Bob from guaranteeing vertex $3$ , so the answer is $2$ .

Case 4

The graph is complete on four vertices. Bob cannot guarantee reaching vertex $4$ , because Alice can always mark the edge leading to it. But Bob can guarantee reaching either vertex $2$ or vertex $3$ , so the answer is $3$ .

Case 5

Bob cannot guarantee reaching vertex $6$ alone, because Alice can block the needed edge whenever there is only one way toward it. But vertices $5$ and $6$ together give Bob enough choices to force reaching a vertex with label at least $5$ .

Output

Case 1

Case 2

Case 3

Case 4

Case 5

Alice and Bob are playing a game on a simple undirected graph with $n$ vertices labeled from $1$ to $n$ and $m$ edges. Initially, a token is placed on vertex $1$ .

They play in turns, and Alice plays first. In each turn:

Alice chooses one edge of the graph and marks it.
Then Bob may either keep the token on its current vertex, or move the token along one unmarked edge to an adjacent vertex.
After Bob's choice, the marked edge becomes unmarked again.

Bob may end the game at any moment, including before the first turn. When the game ends, the label of the vertex containing the token is called the outcome.

Alice wants the outcome to be as small as possible. Bob wants the outcome to be as large as possible. Both players play optimally.

For each test case, determine the largest possible outcome that Bob can guarantee.

$1 \le t \le 10^4$
$1 \le n \le 2 \cdot 10^5$
$0 \le m \le 2 \cdot 10^5$
The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .
The sum of $m$ over all test cases does not exceed $2 \cdot 10^5$ .

t

\left. \begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

The token starts on the only vertex, so Bob can end the game immediately and get outcome $1$ .

The graph is a path. Whenever Bob is at vertex $1$ , Alice can mark the only edge leaving it. Therefore Bob cannot guarantee reaching a larger label, and the answer is $1$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

6D. Cute Game on Graph

Constraints

Input

Output

Samples

6D. Cute Game on Graph

Constraints

Input

Output

Samples