Cho một rừng cây gồm \(n\) đỉnh và \(m\) cạnh.

Có \(q\) câu hỏi có dạng \(x\) \(y\) mang ý nghĩa sau:

• Gọi \(X\) là tập đỉnh thuộc thành phần liên thông chứa \(x\).
• Gọi \(Y\) là tập đỉnh thuộc thành phần liên thông chứa \(y\).
• Có \(|X| \times |Y|\) cách để thêm một cạnh vào cây sao cho \(x\) và \(y\) thuộc cùng một thành phần liên thông. Chắc chắn thành phần liên thông mới được tạo ra là một cây.
• Hãy tính tổng đường kính của cây được tạo ra trong \(|X| \times |Y|\) trường hợp đó.
• Trong tình huống ngay từ đầu \(x\) và \(y\) thuộc cùng một thành phần liên thông thì xem như đáp án bằng \(0\).
• Lưu ý rằng các câu hỏi là các tình huống giả định và không thêm cạnh vào rừng.

Input

• Dòng đầu tiên chứa ba số nguyên dương \(n, m\) và \(q\) \((1 \leq n, m, q \leq 10^{6}; m \leq n - 1)\).
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u\) và \(v\) \((1 \leq u, v \leq n)\) thể hiện một cạnh của rừng.
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(x\) và \(y\) \((1 \leq x, y \leq n)\) thể hiện một câu hỏi.

Output

• Gồm \(q\) dòng, dòng thứ \(i\) chứa một số nguyên thể hiện kết quả của truy vấn thứ \(i\).

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n, m, q \leq 100\).
• Subtask \(2\) (\(17\%\) số điểm): \(m = n - 1\).
• Subtask \(3\) (\(20\%\) số điểm): \(m = n - 2\).
• Subtask \(4\) (\(23\%\) số điểm): \(|u - v| \leq 1\).
• Subtask \(5\) (\(25\%\) số điểm): không có giới hạn gì thêm.

Examples

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

0
8
8
1