Ở thành phố có ~N~ trạm xe bus. Hàng ngày, An sẽ xuất phát từ nhà lúc 6 giờ 00 phút ở trạm xe bus số 1 để tới trường ở trạm xe bus ~N~. Vì thành phố không có nhiều người, hàng ngày, chỉ có một chuyến xe bus xuất phát từ trạm xe số 1 lúc 6 giờ 00 phút và đi với lộ trình ~p_1, p_2, \dots, p_N~ để đi qua ~N~ trạm xe bus. Trong đó ~p_1, p_2, \dots, p_N~ là một hoán vị của dãy số từ 1 đến ~N~ và ~p_1~ luôn bằng 1. Thời gian di chuyển qua các trạm là 1 phút. Xe bus sẽ dừng lại khi đi qua hết ~N~ trạm. Người dân xây thêm ~M~ con đường một chiều nối giữa các trạm xe bus, con đường thứ ~j~ nối từ trạm ~a_j~ tới trạm ~b_j~. Thời gian di chuyển trên con đường này cũng là 1 phút.

Trong ~K~ ngày, mỗi ngày xe bus sẽ hoán đổi lộ trình giữa trạm thứ ~x~ và ~y~ trong lộ trình. Lưu ý xe bus luôn đảm bảo lộ trình xuất phát từ trạm số 1, và những thay đổi lộ trình này vẫn sẽ được giữ nguyên cho những ngày sau.

Yêu cầu: Trong ~K~ ngày này, bạn hãy giúp An kiểm tra xem thời gian ít nhất để tới được trường là bao nhiêu phút.

Input

• Dòng đầu tiên chứa ba số nguyên ~N, M, K~ (~1 \le N, M, K \le 2 \times 10^5~).
• Trong ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a_j, b_j~.
• Dòng tiếp theo chứa dãy ~N~ số ~p_1, p_2, \dots, p_N~.
• Trong ~K~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~.

Output

• Gồm ~K~ dòng, mỗi dòng chứa một số nguyên là thời gian ít nhất cần để An tới trường.

Sample Input 1

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

Sample Output 1

1
2
3