Repovive

You are given an undirected connected graph with $n$ vertices and $m$ edges. Each edge is colored either blue or red. The graph has no self-loops and no multiple edges.

A color sequence of length $k$ is a string $c_1c_2\ldots c_k$ where each $c_i \in \{0,1\}$ ( $0$ means blue, $1$ means red).

A color sequence $c_1c_2\ldots c_k$ is called reachable if there exists a walk that:

starts at vertex $1$ ,
traverses exactly $k$ edges (vertices and edges may be repeated),
and the colors of the traversed edges, in order, are exactly $c_1,c_2,\ldots,c_k$ .

For each test case, find the minimum integer $k \ge 1$ such that there exists at least one non-reachable color sequence of length $k$ . If every color sequence of every length is reachable, output $-1$ .

Constraints

$1 \le n \le 2 \times 10^5$
$n-1 \le m \le 2 \times 10^5$
$1 \le u,v \le n,\ u \ne v$
$c \in \{0,1\}$
The graph is connected, and has no self-loops and no multiple edges.
$\sum n \le 2 \times 10^5$ and $\sum m \le 2 \times 10^5$ over all test cases.

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

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

$n=4$ , cycle with edges $(1,2,B), (2,3,R), (3,4,B), (4,1,R)$

A cycle alternating blue-red-blue-red. From any vertex, we can reach any color sequence. Answer: -1.

$n=3$ , path with edges $(1,2,B), (2,3,B)$

Only blue edges exist. The sequence "R" is unreachable. Answer: 1.

You are given an undirected connected graph with $n$ vertices and $m$ edges. Each edge is colored either blue or red. The graph has no self-loops and no multiple edges.

A color sequence of length $k$ is a string $c_1c_2\ldots c_k$ where each $c_i \in \{0,1\}$ ( $0$ means blue, $1$ means red).

A color sequence $c_1c_2\ldots c_k$ is called reachable if there exists a walk that:

starts at vertex $1$ ,
traverses exactly $k$ edges (vertices and edges may be repeated),
and the colors of the traversed edges, in order, are exactly $c_1,c_2,\ldots,c_k$ .

Constraints

$1 \le n \le 2 \times 10^5$
$n-1 \le m \le 2 \times 10^5$
$1 \le u,v \le n,\ u \ne v$
$c \in \{0,1\}$
The graph is connected, and has no self-loops and no multiple edges.
$\sum n \le 2 \times 10^5$ and $\sum m \le 2 \times 10^5$ over all test cases.

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

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

$n=4$ , cycle with edges $(1,2,B), (2,3,R), (3,4,B), (4,1,R)$

A cycle alternating blue-red-blue-red. From any vertex, we can reach any color sequence. Answer: -1.

$n=3$ , path with edges $(1,2,B), (2,3,B)$

Only blue edges exist. The sequence "R" is unreachable. Answer: 1.

5E. Echoes of Edges

Constraints

Input

Output

Samples

Constraints