Ngày Kết Nối Đầu Tiên

Ban đầu có $n$ thành phố và chưa có con đường nào. Trong $m$ ngày liên tiếp, mỗi ngày đúng một con đường hai chiều được xây; con đường ở dòng thứ $i$ được hoàn thành vào cuối ngày $i$.

Với mỗi truy vấn gồm hai thành phố $u$ và $v$, hãy tìm ngày sớm nhất mà ta có thể đi từ $u$ đến $v$ bằng các con đường đã xây. Một hành trình có thể đi qua nhiều thành phố và đường. Nếu hai thành phố không bao giờ liên thông sau cả $m$ ngày, in $-1$. Khi $u=v$, đáp án là $0$ vì không cần chờ xây đường.

Các con đường có thể lặp lại hoặc nối một thành phố với chính nó; những con đường không làm thay đổi tính liên thông vẫn chiếm một ngày trong lịch xây dựng.

Input

• Dòng đầu chứa ba số nguyên $n$ $m$ $q$: số thành phố, số con đường và số truy vấn.
• $m$ dòng tiếp theo mô tả các con đường theo đúng thứ tự xây dựng. Dòng thứ $i$ chứa hai số $a$ $b$, cho biết con đường ngày $i$ nối hai thành phố đó.
• $q$ dòng cuối, mỗi dòng chứa hai số $u$ $v$ của một truy vấn.

Output

• Với mỗi truy vấn, in trên một dòng:
• $0$ nếu hai đầu truy vấn là cùng một thành phố;
• ngày kết nối sớm nhất nếu chúng từng liên thông;
• $-1$ nếu chúng vẫn không liên thông sau ngày $m$.

Constraints

• $1\le n,m,q\le 2\cdot 10^5$.
• Mọi chỉ số thành phố trong các con đường và truy vấn đều thuộc $[1,n]$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,m,q\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

0
1
3
-1