0E. Both Directions

You are given a connected undirected graph with $n$ vertices and $m$ edges. You want to assign a direction to every edge.

After fixing an orientation, each undirected edge $\{u,v\}$ becomes either $u\to v$ or $v\to u$. Traversing an edge has cost:

• $-1$ if you traverse it along its assigned direction,
• $+1$ if you traverse it against its assigned direction.

A path from $1$ to $n$ is allowed to be any walk: vertices and edges may repeat, and the walk may traverse the same edge multiple times. The cost of a walk is the sum of the costs of its traversed edges.

For a fixed orientation, define the shortest-path value as the minimum possible walk cost from vertex $1$ to vertex $n$ (over all walks).

Among all orientations, choose one that maximizes this shortest-path value. Output this maximum value.

If for every orientation the shortest-path value is $-\infty$ (i.e., for every orientation there exist walks from $1$ to $n$ with arbitrarily small total cost), output $-1$.

Constraints

• $1 \le t \le 200$
• $2 \le n \le 2 \times 10^5$
• $n - 1 \le m \le 2 \times 10^5$
• $1 \le u_i, v_i \le n$
• The graph is connected.
• $\sum n \le 2 \times 10^5$ over all test cases.
• $\sum m \le 2 \times 10^5$ over all test cases.