운전자 의견 불일치

시간 제한2초메모리 제한512 MB

요약

교차로마다 왼쪽과 오른쪽 출구와 탑 가시 여부가 주어집니다. A와 B에서 같은 회전 순서를 따를 때 탑 가시 여부가 처음 달라지는 최소 회전 수를 구합니다.

난이도: 보통10점 중 7점
유형: 그래프, BFS, 유니온 파인드
정답자: 아직 제출이 없습니다

문제

앨리스와 밥은 차를 타고 이탈리아를 여행하던 중 길을 잘못 들었다. 지금은 피사의 도심 한가운데에 갇혀 있다. 도심에서 운전하려면 통행 허가가 필요하므로 벌금을 물 위험이 있다. 두 사람은 지도는 가지고 있지만 GPS는 없다. 지도에는 모든 교차로가 표시되어 있다. 각 교차로에서는 좌회전 또는 우회전만 할 수 있다. 많은 도로가 일방통행이라서 직진이나 유턴은 할 수 없다.

앨리스는 자신들이 교차로 $A$ 에 있다고 생각하고, 밥은 교차로 $B$ 에 있다고 생각한다. 누가 맞는지 알아내기 위해 두 사람은 실험을 하기로 한다. 같은 회전 순서를 지도 위에서 $A$ 에서 출발한 경우와 $B$ 에서 출발한 경우로 각각 따라간다. 지도에는 피사의 사탑이 보이는 교차로가 표시되어 있다. 한쪽에서는 사탑이 보이고 다른 쪽에서는 보이지 않는 순간, 창밖을 보면 누가 맞는지 알 수 있다. 둘 중 정확히 한 명만 맞다고 가정해도 된다.

누가 맞는지 보일 수 있는 최소 회전 횟수를 구하라.

입력

첫 줄에 세 정수 $n$ , $A$ , $B$ 가 주어진다. 여기서 $2 \le n \le 10^5$ , $0 \le A, B < n$ , $A \ne B$ 이다.

이어서 $n$ 개의 줄이 주어진다. $i$ 번째 줄에는 세 정수 $l_i$ , $r_i$ , $t_i$ 가 주어진다. 교차로 $i$ 에서 좌회전하면 $l_i$ 에 도착하고, 우회전하면 $r_i$ 에 도착한다. 교차로 $i$ 에서 피사의 사탑이 보이면 $t_i = 1$ 이고, 보이지 않으면 $t_i = 0$ 이다.

출력

둘 중 누가 맞는지 보여 줄 수 있는 회전 횟수의 최솟값을 출력한다. 어떤 실험으로도 앨리스와 밥 중 누가 맞는지 구분할 수 없다면 indistinguishable을 출력한다.

예제3

예제 1

입력

예상 출력

indistinguishable

예제 2
입력
```
2 0 1
1 1 1
0 0 0
```
예상 출력
```
0
```
예제 3
입력
```
3 1 2
1 2 0
2 0 1
0 1 1
```
예상 출력
```
1
```