P9026 [CCC 2021 S4] Daily Commute

There are $N$ subway stations. Your home is at $1$, and your school is at $N$. There are $W$ one-way walking paths. Each path takes one minute to travel. In addition, there is a circular subway line that visits $S_1,S_2,\cdots,S_N$ in order, and it is guaranteed that $S_1=1$. Every day, there is **exactly one** subway train that departs from $S_1$ at time $0$, and it arrives at $S_i$ at exactly minute $i$. Over the next $D$ days: - Swap $S_{X_i}$ and $S_{Y_i}$. Note that the change is permanent. - Query the shortest time from $1$ to $N$. When you depart, the subway is at $1$.

The first line: $N,W,D$. The next $W$ lines: $A_i,B_i$ represent a one-way walking path. The next line contains $N$ numbers: $S$. The next $D$ lines: $X_i,Y_i$, and it is guaranteed that $2\leq X_i,Y_i\leq N,X_i\neq Y_i$.

Output $D$ lines, the answer for each day.

$$3\leq N\leq 200000,0\leq W\leq 200000,1\leq D\leq 200000$$ Translated from [CCC2021 S4](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2021/ccc/seniorEF.pdf)。 Please pay attention to constants. Translated by ChatGPT 5