Chase on the Graph

Professor Shou is chased by Professor Pang on an undirected, unweighted simple graph. Initially, Professor Shou is at vertex \(1\) and his destination is vertex \(n\), while Professor Pang is at vertex \(k\). The game proceeds in seconds. In each second, Professor Shou moves from his current vertex to an adjacent vertex. Immediately after he moves, Professor Pang attacks according to the following rule:

• Let \(d\) be Professor Pang's attack range and \(\text{dis}\) be the shortest-path distance (i.e. the number of edges) between Professor Pang's current vertex and Professor Shou's new vertex.
• If \(\text{dis} < d\), the damage dealt is \(d - \text{dis}\) and Professor Pang remains at his current vertex.
• If \(\text{dis} \ge d\), Professor Pang cannot deal non‐positive damage. Instead, he teleports to the vertex where Professor Shou is and deals a fixed damage of \(d\).

Note that Professor Shou also takes an attack immediately after arriving at vertex \(n\) (i.e. the last move still triggers an attack). Your task is to compute the minimum total damage that Professor Shou receives in order to reach vertex \(n\) starting from vertex \(1\).

inputFormat

The first line contains four integers \(n\), \(m\), \(d\) and \(k\) where \(n\) is the number of vertices, \(m\) is the number of edges, \(d\) is Professor Pang's attack range, and \(k\) is the starting vertex of Professor Pang.

Each of the following \(m\) lines contains two integers \(u\) and \(v\) indicating that there is an undirected edge between vertices \(u\) and \(v\).

You may assume that \(1 \leq u, v \leq n\) and that the graph is simple (no self-loops or multiple edges). It is guaranteed that there is at least one path from vertex \(1\) to vertex \(n\).

outputFormat

Output a single integer, the minimum total damage that Professor Shou receives when he reaches vertex \(n\).

sample

3 3 2 2
1 2
2 3
1 3

1