Cho một đồ thị vô hướng liên thông có ~n~ đỉnh và ~m~ cạnh. Các đỉnh của đồ thị được đánh số từ ~1~ đến ~n~, các cạnh được đánh số từ ~1~ đến ~m~. Nhiệm vụ của bạn là trả lời ~q~ truy vấn, mỗi truy vấn gồm hai số nguyên ~l~ và ~r~. Kết quả của mỗi truy vấn là số nguyên không âm lớn nhất ~k~ thỏa mãn điều kiện sau:

• Có ít nhất một cặp số nguyên ~(a, b)~ sao cho ~l \le a < b \le r~, hai đỉnh ~a~ và ~b~ không thể đi đến nhau chỉ bằng cách sử dụng ~k~ cạnh đầu tiên (tức là các cạnh ~1, 2, \dots, k~).

Input

• Dòng đầu tiên của mỗi test chứa ba số nguyên ~n, m, q~ ~(2 \le n \le 10^5, 1 \le m, q \le 2 \cdot 10^5)~ tương ứng là số lượng đỉnh, cạnh, và số truy vấn.

• Mỗi dòng trong ~m~ dòng tiếp theo chứa hai số nguyên ~u_i, v_i~ ~(1 \le u_i, v_i \le n)~ - biểu diễn cạnh thứ ~i~ nối đỉnh ~u_i~ và ~v_i~. Dữ liệu đảm bảo rằng đồ thị luôn liên thông, không có cạnh trùng lặp hoặc vòng tự nối (self-loop).

• Mỗi dòng trong ~q~ dòng tiếp theo chứa hai số nguyên ~l, r~ ~(1 \le l < r \le n)~ - mô tả một truy vấn.

Output

• In ra ~q~ số nguyên trên một dòng (các số cách nhau một dấu cách) là kết quả của các truy vấn.

Scoring

Sample Input 1

2 1 1
1 2
1 2

Sample Output 1

0

Sample Input 2

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

Sample Output 2

2 2 4 4