Both Directions - Repovive Opening Round | Repovive

0E. Both Directions

2500 pts2s256 MB

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.

Input

t \\[0.5em] \left. \begin{array}{l} n \quad m \\ v_1 \quad u_1 \\ \vdots \\ v_m \quad u_m \end{array} \right\} \times t

Output

\begin{array}{l} ans_1 \\ \vdots \\ ans_t \end{array}

Where for each test case:

If a valid orientation exists: print the maximum value
If unbounded: output $-1$ .

Samples

Input

Explanation

Sample: path (1,2), path (2), triangle (-1), square (1), pentagon (-1)

Output

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.

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.

t \\[0.5em] \left. \begin{array}{l} n \quad m \\ v_1 \quad u_1 \\ \vdots \\ v_m \quad u_m \end{array} \right\} \times t

\begin{array}{l} ans_1 \\ \vdots \\ ans_t \end{array}

Where for each test case:

If a valid orientation exists: print the maximum value
If unbounded: output $-1$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

0E. Both Directions

Input

Output

Samples

0E. Both Directions

Constraints

Input

Output

Samples

Constraints