Random Walks in a Big City

City N has $n$ crossroads and $m$ two-way roads connecting them. Every crossroad has at least two roads leaving it, and the road network connects every crossroad to every other crossroad. Any two crossroads are joined by at most one road.

A student has just left a nightlife venue near crossroad $s$ and wants to go home, which is near crossroad $t$. Each minute, the following happens:

1. The student chooses one of the roads leaving the current crossroad and walks along it.
2. If the student is now at crossroad $t$, they go home immediately and go to sleep.
3. Otherwise, driven by an irresistible thirst for adventure, the student picks a road leaving the current crossroad at random and walks along it. The only restriction is that the student never picks the road they just used to arrive at this crossroad (the road used in step 1 of the current minute).
4. If after this move the student is at crossroad $t$, they go home.

Given the road network and the crossroads $s$ and $t$, determine whether the student is guaranteed to get home in a finite number of steps. If so, find the minimum $x$ such that the student is guaranteed to be home within $x$ minutes, no matter which random choices they make in step 3 of each minute.

The first line contains one integer $t$ ($1 \leq t \leq 100\,000$), the number of test cases. Each test case starts with a line containing four integers $n$, $m$, $s$, and $t$ ($3 \leq n, m \leq 300\,000$, $1 \leq s, t \leq n$, $s \neq t$): the number of crossroads, the number of roads, the crossroad where the student starts, and the crossroad where the student wants to go. Each of the next $m$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$), the endpoints of the $i$-th two-way road. It is guaranteed that every crossroad can reach every other crossroad using these roads, every crossroad has at least two roads, and no two roads join the same pair of crossroads. The sums of $n$ and of $m$ over all test cases each do not exceed $1\,000\,000$.

For each test case, print one integer. If the student can wander forever by making unlucky random choices, print $-1$. Otherwise, print the minimum number of minutes in which the student is guaranteed to get home when they make the best possible choice in step 1 of every minute.

In the first example, the student first walks to crossroad 3. Then they randomly choose the road to crossroad 2 or crossroad 4. If they choose crossroad 2, they get home immediately. Otherwise, they are at the crossroad next to home at the start of the next minute.

In the second example, the student can keep wandering between the pair of crossroads $(2, 3)$ and the pair $(4, 5)$. Each time they walk toward crossroad 4 or 5, they may make an unlucky random choice and end up at crossroad 2 or 3.