Vào ngày Chủ Nhật, Koi, Kon và Kui quyết định cùng nhau đến tham quan một công viên giải trí. Trong công viên mới mở một trò chơi mê cung thu hút rất nhiều người chơi, các phòng của mê cung được đánh số từ \(1\) tới \(n\). Mỗi phòng đều có tối đa hai cửa: một cửa dẫn tới phòng khác và một cửa dẫn về chính phòng đó, người chơi chỉ có thể đi theo một chiều trên đường nối giữa hai phòng. Đồng thời mê cung đã được thiết kế sao cho giữa hai phòng có không quá một đường đi đơn - đường đi mà không đi vào phòng nào quá hai lần. Koi, Kon và Kui bắt đầu từ ba phòng khác nhau và đều thử tìm đường để gặp nhau tại một phòng trong mê cung. Nhiệm vụ của bạn là xác định căn phòng để ba bạn gặp nhau và có tổng khoảng cách tới ba bạn là nhỏ nhất - Chú ý rằng do cách xây dựng của mê cung, chỉ tồn tại không quá một căn phòng như vậy.

Đầu vào

Dòng đầu tiên chứa số nguyên dương \(n, m, q\) \((1 \le n \le 1000, 1 \le q \le 500000, 1 \le m \le 2n - 2)\) lần lượt là số lượng các phòng, số đường nối giữa hai phòng và số lượng truy vấn.

\(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) \((1 \le u, v \le n)\) mô tả một đường đi của mê cung (có thể đi đường một chiều từ phòng \(u\) tới phòng \(v\)).

\(q\) dòng cuối cùng, mỗi dòng chứa ba số nguyên \(x, y, z\) \((1 \le x, y, z \le n)\) lần lượt là vị trí phòng của Koi, Kon, Kui đang đứng.

Đầu ra

\(q\) dòng, mỗi dòng chứa duy nhất một số nguyên duy nhất là kết quả của một test con. Nếu không tồn tại căn phòng thỏa mãn đề bài thì xuất ra \(0\).

Subtask

\(20\%\) số test có \(n \le 100, q \le 5000\).

\(20\%\) số test có \(q \le 5000\).

\(20\%\) số test có \(m = 2n - 2\).

Ví dụ

Đầu vào:

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

Đầu ra:

2
6
0

Giải thích: Từ đầu vào ta có đồ thị các phòng và các đường đi như sau:

Trong truy vấn đầu tiên, cả ba bạn có thể gặp nhau ở phòng \(2\):

• Koi đi qua các phòng: \(5 \to 2\).
• Kon đi qua các phòng: \(7 \to 3 \to 1 \to 2\).
• Kui đi qua các phòng: \(8 \to 3 \to 1 \to 2\).