Có \(𝑚\) lối đi một chiều chạy giữa các ga, lối đi thứ \(𝑖\) cho phép bạn đi bộ từ ga \(u_i\) đến ga \(v_i (1≤u_i,v_i≤n,u_i≠v_i)\) trong 1 phút. Có thể có nhiều lối đi kết nối cùng một cặp ga nhất định nào đó.

Tuyến tàu điện ngầm đi theo một lộ trình nhất định qua \(𝑛\) ga, bắt đầu từ ga 1 và đến mỗi ga một lần.

Ban đầu, tuyến đường này sẽ đi theo hành trình \(S_1,S_2,...,S_n \) theo thứ tự đó. \(S_1=1 \) và \(S_2,...,S_n\) là hoán vị của các số nguyên \(2,...,n.\)

Chỉ có một chuyến tàu điện ngầm chạy dọc theo tuyến đường này mỗi ngày, khởi hành từ ga \(1\) lúc \(6h\) sáng và mất \(1\) phút để đến ga tiếp theo. Điều này có nghĩa là, \(𝑡\) phút sau 6 giờ sáng, tàu sẽ đến ga \(S_t+1\) (hoặc tại ga \(S_n\) nếu \(t≥n-1\) ).

Tuy nhiên, trong khoảng thời gian \(K\) ngày, lộ trình của tuyến tàu điện ngầm sẽ tiếp tục thay đổi. Vào đầu ngày thứ \(𝑖\), ga thứ \(𝑋\) và ga thứ \(𝑌\) \((2≤X,Y≤n,X≠Y)\) trong tuyến sẽ được hoán đổi.

Lưu ý rằng, sau mỗi lần thay đổi như vậy, tuyến đường sẽ vẫn bắt đầu tại nhà ga \(1\) và sẽ đến tất cả \(𝑛\) nhà ga một lần. Các thay đổi sẽ được sử dụng sang những ngày tiếp theo - tuyến đường sẽ không tự động đặt lại ban đầu \(S_1,S_2,...,S_n.\)

Vào mỗi ngày trong số \(𝑘\) ngày này, bạn muốn xác định xem mình có thể đến trường (ga \(n\)) nhanh như thế nào để có thể bắt đầu học mọi thứ. Vào ngày thứ \(𝑖\), bắt đầu lúc 6 giờ sáng (sau lần cập nhật thứ \(𝑖\) về tuyến đường tàu điện ngầm), bạn sẽ bắt đầu chuyến đi đến ga \(𝑛\).

Mỗi phút, bạn có thể đi tàu điện ngầm đến điểm dừng tiếp theo (nếu bạn hiện đang ở cùng ga với tàu và nó chưa hoàn thành lộ trình), hoặc đi bộ từ ga hiện tại của bạn đến ga khác, hoặc đợi ở ga hiện tại của bạn. Lưu ý rằng chuyến đi của bạn bắt đầu cùng lúc với lộ trình của tàu, có nghĩa là bạn có thể chọn đi ngay nếu muốn và bạn có thể chọn rời đi rồi quay lại tàu trong chuyến đi của mình.

Input

• Dòng đầu tiên chứa số nguyên \(n,m,k\).

• \(𝑚\) dòng tiếp theo, mỗi dòng chứa các số nguyên \(u,v\) mô tả một đường nối từ \(𝑢\) đến \(𝑣\).

• Dòng tiếp theo chứa \(𝑛\) số nguyên \(S_i\)

• \(𝑘\) dòng tiếp theo mỗi dòng chứa hai số \(𝑋, 𝑌.\)

Giới hạn: \(3≤n≤2×10^5,0≤m≤2×10^5,1≤k≤2×10^5 \)

Output

• Ghi ra \(𝑘\) dòng, dòng thứ \(i\) mô tả kết quả của các ngày thứ \(i\).

Sample Input

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

Sample Output

1
2
3