대도시에서의 무작위 산책

도시 N에는 $n$개의 교차로와 이들을 잇는 $m$개의 양방향 도로가 있다. 모든 교차로에서는 도로가 적어도 두 개 출발한다. 도로망을 따라 어떤 교차로에서든 다른 모든 교차로에 갈 수 있다. 두 교차로를 직접 잇는 도로는 많아야 한 개다.

한 학생이 교차로 $s$ 근처의 유흥업소를 막 나와서 교차로 $t$ 근처에 있는 자기 집으로 가려고 한다. 매분 다음 일이 일어난다.

1. 학생은 현재 교차로에서 출발하는 도로 중 하나를 골라 그 도로를 따라 걷는다.
2. 학생이 교차로 $t$에 도착했다면 즉시 집에 가서 잠을 잔다.
3. 그렇지 않으면 참을 수 없는 모험심에 이끌려, 학생은 현재 교차로에서 출발하는 도로 하나를 무작위로 골라 그 도로를 따라 걷는다. 단, 학생은 이 교차로에 도착할 때 방금 사용한 도로(이번 분의 1단계에서 쓴 도로)는 절대 고르지 않는다.
4. 이 이동 후 학생이 교차로 $t$에 있다면 집에 간다.

도로망과 교차로 $s$, $t$가 주어졌을 때, 학생이 유한한 횟수의 이동 안에 반드시 집에 도착할 수 있는지 판단하라. 가능하다면, 매분 3단계에서 어떤 무작위 선택을 하더라도 학생이 반드시 $x$분 이내에 집에 도착하는 최소의 $x$를 구하라.

첫 줄에는 테스트 케이스의 수 $t$($1 \leq t \leq 100\,000$)가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 네 개 $n$, $m$, $s$, $t$($3 \leq n, m \leq 300\,000$, $1 \leq s, t \leq n$, $s \neq t$)가 주어진다. 각각 교차로의 수, 도로의 수, 학생이 출발하는 교차로, 학생이 가려는 교차로다. 이어지는 $m$개의 줄에는 정수 두 개 $u_i$, $v_i$($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$)가 주어지며, 이는 $i$번째 양방향 도로가 잇는 두 교차로다. 모든 교차로에서 도로망을 따라 다른 모든 교차로에 갈 수 있고, 모든 교차로에서 도로가 적어도 두 개 출발하며, 같은 두 교차로를 잇는 도로는 없다고 보장된다. 모든 테스트 케이스에 걸친 $n$의 합과 $m$의 합은 각각 $1\,000\,000$을 넘지 않는다.

각 테스트 케이스마다 정수 하나를 출력한다. 학생이 운 나쁜 무작위 선택을 거듭하며 영원히 돌아다닐 수 있다면 $-1$을 출력한다. 그렇지 않다면, 학생이 매분 1단계에서 최선의 선택을 할 때 반드시 집에 도착하는 최소 분 수를 출력한다.

첫 번째 예제에서 학생은 첫 분에 교차로 3번으로 간다. 그다음 교차로 2번 또는 4번으로 가는 도로를 무작위로 고른다. 교차로 2번을 고르면 즉시 집에 도착한다. 그렇지 않으면 다음 분이 시작될 때 집 근처 교차로에 있게 된다.

두 번째 예제에서 학생은 교차로 쌍 $(2, 3)$과 $(4, 5)$ 사이를 계속 오갈 수 있다. 교차로 4번이나 5번 쪽으로 갈 때마다 운 나쁜 무작위 선택을 해서 교차로 2번이나 3번에 도착할 수 있다.