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

Có $n$ đỉnh và ban đầu chưa có cạnh. Trong ngày thứ $i(1\le i\le m)$, cạnh vô hướng thứ $i$ trong input được thêm vào đồ thị; không cạnh nào bị xóa.

Với mỗi truy vấn gồm hai đỉnh $u$ và $v$, hãy tìm số ngày nhỏ nhất $d$ sao cho sau khi đã thêm $d$ cạnh đầu tiên, $u$ và $v$ nằm trong cùng một thành phần liên thông. Ngày $0$ là thời điểm trước khi thêm cạnh nào. Nếu điều đó không xảy ra ngay cả sau ngày $m$, in $-1$.

Input

• Dòng đầu chứa $n,m$ và $q$.
• $m$ dòng tiếp theo chứa hai đầu mút của cạnh được thêm trong ngày tương ứng.
• $q$ dòng cuối chứa hai đỉnh của một truy vấn.

Output

• Với mỗi truy vấn, in ngày nhỏ nhất làm hai đỉnh liên thông; in $-1$ nếu sau $m$ ngày vẫn không liên thông.

Constraints

• $1\le n,m,q\le 2\cdot 10^5$.
• Mỗi đầu mút nằm trong $[1,n]$ và hai đầu của một cạnh khác nhau.
• Hai đỉnh trong truy vấn có thể trùng nhau.

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

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

3
-1
0
3