Robots

Time limit1sMemory limit1024 MB

Summary

Find the fewest nights for LRATB to reach village F from S without ever sharing a village with AtlasTiger, whose route after day one is unknown.

Level: Medium7 of 10
Topics: BFS, Graph
Solved: No attempts yet

Statement

Cimrman Dynamics is testing its new model, the Long Range Autonomous Trekking Bot (LRATB). LRATB has to travel from village $S$ to village $F$ in the region. For environmental and safety reasons, LRATB moves only at night, and each night it may relocate only to a village adjacent to its current one along a cycling path.

Overseas Dynamics is testing a similar product in the same area. Its humanoid robot AtlasTiger also moves only at night, and each night it relocates from its village to an adjacent one.

If both robots stay in the same village for the whole day (from dawn to dusk), the signal interference may damage the navigation systems. LRATB must therefore follow a route where the two robots are never in the same village during the same day. The team knows only where AtlasTiger is on the first day, $T$ , and knows nothing about its later moves. LRATB may stay in a village overnight without leaving it. If the two robots cross each other on the same path at night in opposite directions, there is no risk.

Both robots start at dawn of the same day in their starting villages. Find the shortest time for LRATB to reach $F$ such that no interference can occur, whatever AtlasTiger does.

Input

The first line contains five integers $N$ , $M$ , $F$ , $T$ , $S$ . Here $N$ is the number of villages, $M$ is the number of paths, $F$ is the destination village, $T$ is the starting village of AtlasTiger, and $S$ is the starting village of LRATB. Each of the next $M$ lines contains two village labels that are connected by a path.

Constraints: $1 \le N \le 10^5$ , $0 \le M \le 2 \cdot 10^5$ , $0 \le F, T, S \le N-1$ . Villages are labelled $0, 1, \ldots, N-1$ . No path connects a village to itself, and no two paths connect the same pair of villages.

Output

Print the minimal number of nights LRATB needs to reach village $F$ with no interference guaranteed. If no such route exists, print death.

Examples4

Example 1
Input
```
5 4 0 1 4
0 1
1 2
2 3
3 4
```
Expected output
```
4
```
Example 2
Input
```
5 5 0 1 4
0 1
1 2
1 3
2 3
3 4
```
Expected output
```
death
```
Example 3
Input
```
3 2 0 2 1
2 1
0 1
```
Expected output
```
1
```
Example 4
Input
```
4 3 0 1 3
2 1
2 3
0 1
```
Expected output
```
4
```