Ở đất nước Byteland có \(N\) thành phố nhưng không có đường nào di chuyển giữa chúng. Tuy nhiên, mỗi ngày, một con đường mới sẽ được xây. Tổng cộng có \(m\) con đường.Trả lời \(q\) truy vấn: "Sau bao nhiêu ngày ta có thể di chuyển từ thành phố \(a\) sang \(b\)".

Input

• Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(Q\): số thành phố, con đường và truy vấn. Các thành phố được đánh số \(1, 2, \ldots, n\).
• \(M\) dòng sau thể hiện con đường được xây dựng. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): có đường nối giữa \(a\) và \(b\)
• \(Q\) dòng cuối thể hiện mỗi truy vấn. Mỗi dòng gồm hai số nguyên \(a\) và \(b\): muốn di chuyển từ thành phố \(a\) sang \(b\).

Output

• Với mỗi truy vấn, in ra số ngày hoặc \(-1\) nếu không thể di chuyển.

Constraints

• \(1 \ \leq \ N, M, Q \ \leq \ 2 \times 10^5\)
• \(1 \ \leq a, b \ \leq \ n\)

Example

Sample input

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

2
-1
4