Chỉ số đầu tiên

Thành phố \(X\) là một thành phố cực kì rộng lớn với \(n\) ngôi nhà được đánh số theo thứ tự từ \(1\) đến \(n\), kết nối với nhau bằng \(m\) con đường hai chiều, sao cho ngôi nhà này luôn đi tới đường ngôi nhà khác bằng cách đi qua những con đường đã có. Một đoàn thanh tra di chuyển đến thành phố \(X\) để khảo sát về mạng lưới giao thông ở đây. Huy là thị trưởng thành phố, Huy phải trả lời \(Q\) câu hỏi, mỗi câu hỏi gồm hai số nguyên dương \(l\) và \(r\). Yêu cầu của mỗi câu hỏi chính là tìm ra số nguyên không âm \(k\) đầu tiên, sao cho thỏa mãn điều kiện sau:

Với mọi cặp \((a, b)\) sao cho \(l ≤ a ≤ b ≤ r\), hai đỉnh \(a\), \(b\) đều đi đến được với nhau chỉ sử dụng \(k\) con đường đầu tiên trong \(m\) con đường đã cho, nếu không cần sử dụng con đường nào thì \(k = 0\).

Do số lượng câu hỏi đôi lúc có thể quá nhiều, nếu Huy tự làm sẽ mất rất nhiều thời gian, Huy cần các bạn giúp Huy viết chương trình để có thể trả lời các câu hỏi này một cách nhanh và đúng nhất có thể!

Input

Dòng đầu tiên là ba số nguyên dương \(n, m, q\) \((2 ≤ n ≤ 10^5, 1 ≤ m, q ≤ 2.10^5)\) -- số ngôi nhà, số con đường và số câu hỏi cần phải trả lời.

\(M\) dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương \(u_{i}, v_{i}\) \((1 ≤ u_{i}, v_{i} ≤ n)\) -- cạnh thứ \(i\) nối hai ngôi nhà \(u_{i}\) và \(v_{i}\).

\(Q\) dòng cuối cùng, mỗi dòng gồm 2 số nguyên dương \(l, r\) \((1 ≤ l ≤ r ≤ n)\) -- mô tả câu hỏi.

Output

Gồm \(Q\) số nguyên không âm, mỗi số cách nhau \(1\) dấu cách .

Example

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

3 3 0 5 5 

Scoring

\(30\%\) số test có \(n, m, q ≤ 50\).

\(20\%\) số test có \(n, m, q ≤ 1000\), trong tất cả các câu hỏi \(l + 1 = r\).

\(20\%\) số test có \(m = n - 1\), trong tất cả các câu hỏi \(l + 1 = r\), đồ thị có dạng đường thẳng.

\(15\%\) số test đồ thị có dạng cây, trong tất cả các câu hỏi \(l + 1 = r\)

\(15\%\) số test còn lại không có ràng buộc gì thêm.