로봇

시간 제한1초메모리 제한1024 MB

요약

LRATB가 S에서 F까지 가는 최소 밤 수를 구합니다. AtlasTiger가 T에서 어떻게 움직이든 같은 날 같은 마을에 머물지 않아야 합니다.

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

문제

Cimrman Dynamics사는 신형 모델인 Long Range Autonomous Trekking Bot(LRATB)을 시험하고 있다. LRATB는 지역 안의 마을 $S$ 에서 마을 $F$ 까지 이동해야 한다. 환경과 안전을 이유로 LRATB는 밤에만 움직이며, 매일 밤 자전거 도로로 연결된 인접한 마을 하나로만 옮겨 갈 수 있다.

Overseas Dynamics사도 같은 지역에서 비슷한 제품을 시험하고 있다. 이 회사의 휴머노이드 로봇 AtlasTiger도 밤에만 움직이며, 매일 밤 현재 마을에서 인접한 마을 하나로 이동한다.

두 로봇이 하루 종일(새벽부터 해질 때까지) 같은 마을에 머물면 신호 간섭으로 항법 시스템이 손상될 수 있다. 따라서 LRATB는 같은 날 두 로봇이 같은 마을에 있지 않도록 경로를 짜야 한다. 팀이 아는 것은 첫날 AtlasTiger의 위치 $T$ 뿐이고, 그 뒤의 움직임은 모른다. LRATB는 마을을 떠나지 않고 그곳에서 하룻밤 머무를 수 있다. 밤에 두 로봇이 같은 길을 반대 방향으로 지나치며 잠깐 만나는 경우에는 위험이 없다.

두 로봇은 같은 날 새벽에 각자의 출발 마을에서 출발한다. AtlasTiger가 어떻게 움직이든 간섭이 일어나지 않도록, LRATB가 $F$ 에 도달하는 가장 짧은 시간을 구하라.

입력

첫 줄에 정수 다섯 개 $N$ , $M$ , $F$ , $T$ , $S$ 가 주어진다. $N$ 은 마을 수, $M$ 은 길의 수, $F$ 는 도착 마을, $T$ 는 AtlasTiger의 출발 마을, $S$ 는 LRATB의 출발 마을이다. 이어지는 $M$ 개의 줄에는 길로 직접 연결된 두 마을의 번호가 주어진다.

제한: $1 \le N \le 10^5$ , $0 \le M \le 2 \cdot 10^5$ , $0 \le F, T, S \le N-1$ . 마을은 $0, 1, \ldots, N-1$ 로 번호가 매겨져 있다. 자기 자신과 잇는 길이나 같은 두 마을을 잇는 길은 없다.

출력

간섭이 일어나지 않음을 보장하면서 LRATB가 마을 $F$ 에 도달하는 데 필요한 최소 밤 수를 출력한다. 그런 경로가 없으면 death를 출력한다.

예제4

예제 1
입력
```
5 4 0 1 4
0 1
1 2
2 3
3 4
```
예상 출력
```
4
```
예제 2
입력
```
5 5 0 1 4
0 1
1 2
1 3
2 3
3 4
```
예상 출력
```
death
```
예제 3
입력
```
3 2 0 2 1
2 1
0 1
```
예상 출력
```
1
```
예제 4
입력
```
4 3 0 1 3
2 1
2 3
0 1
```
예상 출력
```
4
```