Minimum Time to Catch czx in the Park

The park where czx "ghosts" is modeled as an undirected, connected graph \(G\) with \(n\) vertices and \(m\) edges (no self-loops). The searcher, lty, enters the park from the entrance located at node \(b\) at time \(0\) and wants to catch czx. Initially, czx is at node \(e\).

czx follows a predetermined movement plan. Specifically, czx stays in his current node until a given time then moves instantly to another node. Formally, at time \(a_1\) he moves to node \(x_1\), at time \(a_2\) he moves to node \(x_2\), and so on. After his last move, czx remains on that node indefinitely. It is guaranteed that lty knows the entire plan in advance.

Assuming that traveling through an edge takes exactly one unit of time, determine the minimum time lty must spend starting at time \(0\) from node \(b\) so that he can intercept czx, i.e. be at the same node at the same time as czx. Note that lty may wait at any node if necessary.

Hint: You can compute the shortest distances from \(b\) to all nodes, and then, for each period in which czx is static (from time \(T_{start}\) to \(T_{end}\)), check if lty can arrive in time. The earliest meeting time in a period is \(\max(\text{distance}(b, v), T_{start})\), where \(v\) is czx's location during that period. The answer is the minimum such time over all periods (if possible). Guaranteed that an answer exists.

inputFormat

The input is given as follows:

• The first line contains two integers \(n\) and \(m\) (\(1 \leq n, m \leq 10^5\)), the number of nodes and the number of edges.
• The next \(m\) lines each contain two integers \(u\) and \(v\) representing an edge between nodes \(u\) and \(v\).
• The following line contains three integers \(b\), \(e\), and \(k\): the starting node for lty (the park entrance), the initial position of czx, and the number of moves czx will make.
• The next \(k\) lines each contain two integers \(a_i\) and \(x_i\) representing that at time \(a_i\) (in units of time) czx moves to node \(x_i\). The \(a_i\) values are given in strictly increasing order.

It is guaranteed that the graph is connected and that czx will eventually stay at his last node indefinitely.

outputFormat

Output a single integer --- the minimum time at which lty can catch czx, i.e., be present at the same node at the same time.

sample

3 2
1 2
2 3
1 3 1
3 2

2