C. SeaTac
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Seba and Cam are roommates in Seattle. Seba is a frequent flyer, and Cam often has to drive Seba to and from SeaTac airport. Cam's car gets decent gas mileage, but not enough to be driving Seba around Seattle for free all the time, so Cam asks Seba to reimburse him for the gas. Seba needed a ride to SeaTac today, so Seba agreed to fill up Cam's tank when they arrived at SeaTac. The catch is Seba will be giving Cam directions and can direct him anywhere in Seattle, leaving him none the wiser.

Seattle can be modeled as an undirected, connected graph with $$$n$$$ nodes and $$$m$$$ roads. Seba and Cam's house is at node $$$1$$$, and SeaTac is at node $$$n$$$. A path $$$P$$$ of length $$$k$$$ is a sequence of $$$k$$$ nodes such that for all $$$1 \leq i \leq k-1$$$, there is an edge between $$$P_i$$$ and $$$P_{i+1}$$$. Seba can choose any path $$$P$$$ such that $$$P_1 = 1$$$ and $$$P_k = n$$$.

Cam's gas tank can hold $$$g$$$ gallons of gasoline, and it starts off full. It takes one gallon of gasoline to traverse a single road. Whenever Cam runs out of gas, he has to stop and fill up, paying out of his own pocket. Suppose the gas tank has $$$x$$$ gallons when Seba and Cam reach SeaTac. Then, Seba will pay for the remaining $$$g-x$$$ gallons of gasoline.

Seba wants to direct Cam on a route such that the amount of gas Seba is required to pay for is minimized! Seba is far too busy last minute packing for their trip, so they have tasked you with finding an optimal route through Seattle from their house to SeaTac.

Cam's car is European, so the capacity of his gas tank is always prime.

Input

The first line contains three integers $$$n$$$, $$$m$$$, and $$$g$$$ ($$$2 \leq n \leq 2\cdot10^5$$$, $$$1 \leq m \leq 2\cdot10^5$$$, $$$2 \leq g \leq 2\cdot10^5$$$, $$$g$$$ is prime) — the number of nodes, the number of roads, and the size of Cam's gas tank, respectively.

Each of the following $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i,v_i \leq n$$$, $$$u_i \ne v_i$$$) — $$$i$$$th undirected edge connecting nodes $$$u_i$$$ and $$$v_i$$$.

It is guaranteed that the graph is connected and that there is at most one edge between any pair of nodes.

Output

Output the number of gallons of gasoline that Seba has to pay for.

Examples
Input
5 5 2
1 2
1 3
2 4
3 4
4 5
Output
1
Input
4 3 3
1 2
2 3
3 4
Output
0