Giữa tình hình dịch bệnh căng thẳng, Bedao High School for Gifted Students cần lập một kế hoạch cụ thể để đưa học sinh trở lại trường nhanh nhất có thể. Trước mắt do yêu cầu của Bộ Y Tế, trường học sẽ phải chia học sinh ra hai nhóm và theo học 2 ca khác nhau (sáng và chiều).

Trường học gồm có ~N~ học sinh đánh số từ ~1~ tới ~N~. Do dịch bệnh phức tạp, các bạn học sinh bắt buộc phải học online trong quãng thời gian rất dài, và từ đó đã xảy ra ~M~ mâu thuẫn giữa các cặp học sinh, khiến các học sinh này không thể học chung ca với nhau. Mâu thuẫn thứ ~i~ xảy ra giữa hai bạn ~u_i~ và ~v_i~, tuy nhiên do có tin nhà trường cho quay trở lại học, hai bạn này sẽ cố gắng giảng hoà và có thể học chung một ca với nhau sau ~i~ ngày. Nếu có nhiều mâu thuẫn xảy ra giữa cùng một cặp học sinh, số ngày cần để giảng hoà sẽ là chỉ số ~i~ lớn nhất biểu diễn cặp mâu thuẫn đó.

Ngoài việc lên kế hoạch dựa trên các cặp mâu thuẫn đã biết trước, nhà trường cũng cần chuẩn bị cho ~Q~ tình huống khác nhau, trong đó tình huống thứ ~i~ biểu diễn một mâu thuẫn không thể giảng hoà giữa hai bạn ~a_i~ và ~b_i~. Với mỗi tình huống, bạn hãy giúp nhà trường xác định số ngày tối thiểu cần thiết để các bạn giảng hoà với nhau trước khi có thể chia ~N~ học sinh vào hai ca học để việc học tập trực tiếp có thể được thực hiện.

Input

• Dòng đầu tiên gồm ba số nguyên dương ~N, M, Q~.
• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u_i~ và ~v_i~ ~(u_i \neq v_i, u_i, v_i \leq n)~ biểu diễn mâu thuẫn thứ ~i~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~a_i~ và ~b_i~ ~(a_i \neq b_i, a_i, b_i \leq n)~ biểu diễn tình huống thứ ~i~.

Output

• In ra ~Q~ số nguyên không âm trên ~Q~ dòng, số nguyên thứ ~i~ biểu diễn số ngày ít nhất cần để chờ các học sinh giảng hoà trước khi trường có thể quay lại học. Nếu không cần thiết phải giảng hoà, in ra ~0~.

Subtask

• Subtask 1 (50% số điểm): ~N, M, Q \leq 2000~.
• Subtask 2 (50% số điểm): ~N, M, Q \leq 5 \times 10^{5}~.

Sample Input 1

3 3 2
1 2
2 3
3 1
1 2
3 1

Sample Output 1

2
1

Sample Input 2

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

Sample Output 2

0
2