Metro Route Swaps and Shortest Time

You are given N metro stations numbered from 1 to N where your home is station 1 and your school is station N. There are W one‐way pedestrian paths between stations; each path takes 1 minute to traverse.

In addition, there is a circular metro line that visits stations in the order \(S_1,S_2,\dots,S_N\) (a permutation of \(\{1,2,\dots,N\}\)) with the guarantee that \(S_1=1\). Every day, exactly one metro train departs from station \(S_1\) at time 0 and stops at station \(S_i\) at minute \(i-1\) (i.e. the train is at station \(S_1\) at time 0, at \(S_2\) at time 1, and so on).

You may only board the metro at time 0 from station 1. Once on board, you can choose to disembark at any stop. After disembarking, you may use the pedestrian paths. Alternatively, you can walk from your starting point. Thus, if you disembark at the i-th stop (i.e. station \(S_i\)) you finish your metro ride at time \(i-1\) and then need additional foot travel time from \(S_i\) to station N.

You are also given a fixed pedestrian network. Let foot[u] be the minimum time to reach station N from station u using only pedestrian paths. (Each pedestrian edge takes exactly 1 minute.)

Initially, the permutation \(S\) is the identity, i.e. \(S_i=i\) for \(1\le i\le N\). For the next D days, you will be given a pair of indices \(X_i\) and \(Y_i\). On that day, you swap \(S_{X_i}\) and \(S_{Y_i}\) (this change is permanent) and then you must answer a query: What is the minimum time required to travel from station 1 (your home) to station N (your school) if you can choose either to walk (using the pedestrian paths) from the beginning or to board the metro at time 0 and then, after disembarking, walk using the pedestrian paths?

The answer for each day is the minimum of:

• The walking time directly from station 1 to station N, i.e. foot[1].
• For every metro stop \(i\) (\(1\le i\le N\)): the time \((i-1) + foot[S_i]\), since the metro ride takes \(i-1\) minutes and then you need to walk from station \(S_i\) to station N.

All formulas are given in LaTeX format.

inputFormat

The first line contains three integers \(N\), \(W\), and \(D\) — the number of stations, the number of one‐way pedestrian paths, and the number of days (queries), respectively.

Then follow \(W\) lines, each containing two integers \(u\) and \(v\) (\(1 \le u,v \le N\)) indicating there is a one‐way pedestrian path from station \(u\) to station \(v\) (which takes 1 minute).

Then follow \(D\) lines. Each line contains two integers \(X_i\) and \(Y_i\) (\(1 \le X_i,Y_i \le N\)). It is guaranteed that the swaps will not involve the first position (i.e. \(S_1\) remains 1 after any swap).

Note: Initially, the metro line permutation is \(S=[1,2,\dots,N]\).

outputFormat

For each of the D days, output a single integer — the minimum time (in minutes) required to travel from station 1 to station N after performing the swap of that day.

sample

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

1
2
2

</p>