Kênh truyền

Một hệ thống máy tính gồm có $N$ máy chủ được đánh số từ $1$ đến $N$. Ban đầu, giữa các máy chủ chưa có bất kỳ kênh truyền trực tiếp nào.

Trong $M$ bước thiết lập tiếp theo, mỗi bước sẽ có một kênh truyền hai chiều mới được kích hoạt. Cụ thể, ở bước thứ $i$, kênh truyền nối giữa hai máy chủ $u_i$ và $v_i$ bắt đầu hoạt động.

Hệ thống nhận được $Q$ yêu cầu kiểm tra. Mỗi yêu cầu gồm hai máy chủ $a$ và $b$. Với mỗi yêu cầu, hãy xác định số thứ tự của bước thiết lập sớm nhất mà hai máy chủ này có thể truyền tin cho nhau qua các kênh truyền đã hoạt động. Nếu hai máy chủ không bao giờ kết nối được với nhau, hãy in ra $-1$.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên $N, M, Q$ ($1 ≤ N, M, Q ≤ 2 · 10^5$), lần lượt là số lượng máy chủ, số lượng kênh truyền được thiết lập và số lượng yêu cầu kiểm tra.

Trong $M$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $u_i, v_i$ ($1 ≤ u_i, v_i ≤ N$, $u_i ≠q v_i$) mô tả kênh truyền được kích hoạt ở bước thứ $i$ nối giữa hai máy chủ $u_i$ và $v_i$.

Trong $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a, b$ ($1 ≤ a, b ≤ N$) mô tả một yêu cầu kiểm tra giữa hai máy chủ $a$ và $b$.

Kết quả

Với mỗi yêu cầu kiểm tra, in ra trên một dòng số thứ tự của bước thiết lập sớm nhất để hai máy chủ $a$ và $b$ liên thông với nhau, hoặc $-1$ nếu chúng không bao giờ liên thông.

Chấm điểm

Subtask 1 (30 points). $N, M, Q ≤ 1000$

Subtask 2 (70 points). $1 ≤ N, M, Q ≤ 2 · 10^5$

Ví dụ

Input

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

Output

2
-1
4

Ghi chú

Giải thích ví dụ:

Ở bước 1, kênh truyền giữa máy chủ 1 và 2 được thiết lập.

Ở bước 2, kênh truyền giữa máy chủ 2 và 3 được kích hoạt. Lúc này máy chủ 1 và 3 đã liên thông với nhau qua máy chủ 2, do đó kết quả của yêu cầu đầu tiên là 2.

Máy chủ 4 không có bất kỳ kênh truyền nào trong suốt quá trình, vì vậy máy chủ 1 và 4 không bao giờ kết nối được với nhau, kết quả là $-1$.

Ở bước 4, kênh truyền giữa máy chủ 2 và 5 được kích hoạt, giúp máy chủ 5 kết nối tới máy chủ 1 thông qua máy chủ 2, do đó kết quả của yêu cầu thứ ba là 4.