Cho một đồ thị vô hướng gồm \(n\) đỉnh và \(m\) cạnh. Đồ thị đảm bảo từ một đỉnh \(u\) có đường đi đến đỉnh \(v\) bất kì.

Gọi \(f(u, v)\) là số lượng cạnh cầu ít nhất trên đường đi từ \(u\) đến \(v\).

Cho \(q\) truy vấn, mỗi truy vấn có dạng: \((u, v, w)\) yêu cầu tìm đỉnh \(x\) sao cho \(f(u, x) + f(v, x) + f(w, x)\) nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa 3 số nguyên dương \(n, m, q\) (\(n, q \leq 10^5, m \leq \min(\frac{n \cdot (n-1)}{2}, 5 \cdot 10^5)\)) lần lượt là số đỉnh, số cạnh của đồ thị, số truy vấn cần xử lí.
• \(m\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(u, v\) (\(u, v \leq n\)) mô tả một cạnh của đồ thị.
• \(q\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương \(u, v, w\) (\(u, v, w \leq n\)) mô tả một truy vấn.

Output

• Gồm \(q\) dòng, dòng thứ \(i\) chứa một số duy nhất là kết quả của truy vấn thứ \(i\).

Example

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

1
0

Scoring

• Subtask 1 (\(10\%\) số điểm): \(n, q \leq 20\).
• Subtask 2 (\(20\%\) số điểm): \(n \leq 700, m \leq 3000, q \leq 700\).
• Subtask 3 (\(30\%\) số điểm): Đồ thị là cây.
• Subtask 4 (\(40\%\) số điểm): Không có ràng buộc gì thêm.