Time Machine

Time limit1sMemory limit1024 MB

Summary

Find the minimum time to reach vertex N from vertex 1 when one edge a to b rewinds the clock by c, or report x if unreachable or -inf if the time can shrink forever.

Level: Medium6 of 10
Topics: Shortest path, Graph, BFS
Solved: No attempts yet

Problem

A directed graph with $N$ vertices and $M$ edges is given. Moving along each edge takes $1$ unit of time. Vertex $a$ has a time machine. Using it moves you to vertex $b$ and sends the clock back by $c$ . There is no limit on how many times the time machine can be used. Starting at vertex $1$ at time $0$ , find the minimum arrival time at vertex $N$ . You may keep moving after you reach vertex $N$ .

Input

The first line contains $N$ , $M$ , $a$ , $b$ , and $c$ , separated by spaces. $(1 \leq N,M \leq 200\ 000; 1 \leq a,b \leq N; 1 \leq c \leq 10^9)$

From the second line to the $(M+1)$ -th line, line $i+1$ contains two integers $u_i$ and $v_i$ . This means the $i$ -th edge goes from $u_i$ to $v_i$ . $(1 \leq u_i, v_i \leq N; u_i \neq v_i)$

Output

Print the minimum arrival time on the first line. If it is impossible to reach vertex $N$ , print x. If the arrival time can be made arbitrarily small, print -inf.

Examples3

Example 1
Input
```
5 4 3 4 2
1 2
2 3
2 4
4 5
```
Expected output
```
1
```
Example 2
Input
```
5 3 3 4 2
1 2
2 3
2 4
```
Expected output
```
x
```
Example 3
Input
```
5 4 4 3 3
1 2
3 2
2 4
4 5
```
Expected output
```
-inf
```