1E. Echoes of Edges

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.