Có $n$ thành phố và $m$ con đường. Các con đường được tiến hành xây dựng lần lượt theo một thứ tự cho trước.

Bạn được cung cấp $q$ truy vấn, mỗi truy vấn gồm hai thành phố $a$ và $b$. Nhiệm vụ của bạn là đối với mỗi truy vấn, hãy xác định thời điểm sớm nhất (tương đương với số lượng con đường tối thiểu cần được xây dựng kể từ ban đầu) để hai thành phố $a$ và $b$ liên thông với nhau.

Dữ liệu vào (Input)

Dòng đầu tiên chứa ba số nguyên $n$, $m$ và $q$: số lượng thành phố, số lượng con đường và số lượng truy vấn. Các thành phố được đánh số thứ tự từ $1$ đến $n$.

• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$: mô tả một con đường được xây dựng kết nối thành phố $a$ và thành phố $b$. Thứ tự xuất hiện của các dòng này cũng chính là thứ tự thời gian các con đường được xây.

• $q$ dòng cuối cùng, mỗi dòng chứa hai số nguyên $a$ và $b$: mô tả một truy vấn yêu cầu kiểm tra thời điểm liên thông giữa thành phố $a$ và thành phố $b$.

Kết quả (Output)

In ra $q$ số nguyên (mỗi số trên một dòng hoặc cách nhau bởi dấu cách) đại diện cho đáp án của từng truy vấn tương ứng. Với mỗi truy vấn, in ra số lượng con đường tối thiểu cần xây. Nếu hai thành phố không bao giờ liên thông với nhau ngay cả khi đã xây toàn bộ $m$ con đường, in ra $-1$.

Giới hạn (Constraints)

• $1 \le n, m, q \le 2 \cdot 10^5$

• $1 \le a, b \le n$

Example

Input:

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

Output:

2
-1
4