32197번 - 절연 구간 최소화

문제

지하철의 전기를 공급받는 방식(급전 방식)은 직류와 교류로 구분된다. 열차 운행 중 급전 방식이 바뀌게 되면 잠시 전력 공급이 중단된다. 이러한 현상을 절연이라 부른다. 열차 탑승객의 만족도는 절연이 적게 발생할수록 높아진다.

서울특별시에는 $N$개의 지하철역이 있고, 두 역을 직접 잇는 선로 $M$개가 설치되어 있다. 각 역에는 1ドル$부터 $N$번까지의 번호가, 선로에는 1ドル$부터 $M$번까지의 번호가 붙어있다. 설치되어 있는 선로만으로 임의의 두 역 사이를 이동할 수 있다. 각 선로는 직류 또는 교류 중 하나의 방식으로 전기를 공급하며 양방향으로 통행할 수 있다.

열차는 어떤 역과 이어진 선로를 통해 다른 역으로 이동하는 과정을 몇 번이든 반복할 수 있다. 이 때, 이용하는 선로의 급전 방식이 직류에서 교류로, 또는 교류에서 직류로 바뀐다면 절연이 발생한다.

당신은 열차 기관사이다. 당신은 $A$번 역에서 출발해서, 선로를 통해 $B$번 역까지 열차를 운행하고자 한다. 이 때 절연이 일어나는 횟수를 최소로 하는 경로로 운행할 때, 절연이 몇 번 발생하는지 구해보자.

입력

첫 줄에 지하철역의 수 $N$과 선로의 수 $M$이 정수의 형태로 사이에 공백을 두고 주어진다.

다음 $M$개의 줄에 걸쳐, $i$ (1ドル \le i \le M$)번째 줄에 세 정수 $S_i,ドル $E_i,ドル $T_i$가 사이에 공백을 두고 주어진다. 이는 $i$번 선로가 $S_i$번 역과 $E_i$번 역을 직접 연결하며, $T_i = 0$이라면 직류로, $T_i = 1$이라면 교류로 전기를 공급받음을 나타낸다.

다음 줄에 시작 역과 끝 역을 나타내는 두 정수 $A,ドル $B$가 사이에 공백을 두고 주어진다.

출력

$A$번 역에서 $B$번 역까지 열차를 운행할 때 급전 방식이 바뀌는 최소 횟수를 정수의 형태로 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• 2ドル \le N \le 100 000$
• 1ドル \le M \le 150 000$
• 1ドル \le S_i \le N$
• 1ドル \le E_i \le N$
• $S_i \ne E_i$
• $T_i = 0$ 혹은 $T_i = 1$
• 1ドル \le A \le N$
• 1ドル \le B \le N$
• $A \ne B$
• 임의의 두 역 사이를 주어진 선로를 이용해 이동할 수 있다.
• 두 역을 직접 잇는 선로는 최대 한 개 존재한다.

힌트