Second Shortest Path with Cautious Navigation

You are given an undirected graph with n nodes and m edges. Each edge has a fixed weight w (i.e. it takes w units of distance to traverse any edge). The starting node is 1 and the exit is node n. However, the traveler (zrz) doesn’t want to take the shortest path but rather the second shortest path.

The second shortest path is defined as the smallest path length strictly greater than the shortest path length. Note that even if the second candidate path shares some edges with the shortest path (or even repeats some nodes and edges), it is still considered valid. Also, if there are multiple distinct paths whose lengths equal the shortest path distance, then none of these are counted as the second shortest path.

There is one more twist: before entering any node v (except the starting node 1 and the exit node n), the traveler checks the number of nodes directly connected to v (i.e. the degree of v). If this number is strictly less than an integer k, then the traveler is too frightened to go there, and that node cannot be used as an intermediate vertex in the path.

Your task is to compute the length of the second shortest path from node 1 to node n based on these rules. If no such path exists, output -1.

Note: All edges are bidirectional and have equal weight w. Repetition of nodes and edges is allowed as long as the conditions above are met.

inputFormat

The first line contains four integers n, m, w, and k, where

• n (2 ≤ n ≤ 10⁵) is the number of nodes.
• m (1 ≤ m ≤ 10⁵) is the number of edges.
• w (1 ≤ w ≤ 10⁴) is the weight of every edge.
• k (0 ≤ k ≤ n) is the caution parameter.

The next m lines each contain two integers u and v (1 ≤ u, v ≤ n), indicating that there is an undirected edge connecting nodes u and v.

Note: There might be multiple edges or self-loops. Intermediate nodes (i.e. any node except 1 and n) are only allowed if their degree (number of adjacent nodes) is at least k.

outputFormat

Output a single integer representing the length of the second shortest path from node 1 to node n under the given conditions. If such a path does not exist, output -1.

sample

4 4 2 2
1 2
2 3
3 4
1 4

6