Problem Description

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$.

Input Format

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 Format

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

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

1
2
3

Hint

$$3\leq N\leq 200000,0\leq W\leq 200000,1\leq D\leq 200000$$

Translated from CCC2021 S4。

Please pay attention to constants.

Translated by ChatGPT 5