Đất nước ABC có ~N~ thành phố được đánh số thứ tự từ ~1~ đến ~N~ và ~m~ con đường hai chiều trực tiếp nối các thành phố với nhau. Hiện tại các con đường giữa các thành phố đang được nâng cấp, con đường hai chiều thứ ~i~ nối hai thành phố ~u_i, v_i~, và sẽ được khánh thành vào ngày ~d_i~. Các thành phố luôn có đường đi đến với nhau (trực tiếp hoặc gián tiếp), giữa hai thành phố bất kì chỉ có nhiều nhất một con đường hai chiều trực tiếp nối chúng và không có đường đi nối một thành phố với chính nó.

Yêu cầu

Có ~q~ đoàn khách du lịch đến tham quan đất nước ABC. Đoàn khách thứ ~i~ đang ở thành phố ~a_i~ có nhu cầu đi tham quan thành phố ~b_i~. Bạn hãy giúp các đoàn biết sớm nhất là ngày bao nhiêu thì đường đi từ thành phố ~a_i~ đến thành phố ~b_i~ được thông suốt để đoàn có thể khởi hành. Chú ý rằng nếu thành phố đang ở và thành phố muốn đến tham quan trùng nhau ~(a_i = b_i)~ thì đoàn có thể đi ngay được luôn nên quy ước ngày đi sẽ là ngày ~0~.

Dữ liệu đầu vào

Gồm ~m + q + 1~ dòng:

• Dòng thứ nhất ghi ba số nguyên dương ~N, m, q~ lần lượt là số lượng thành phố, số lượng con đường trực tiếp và số lượng đoàn khách du lịch ~(1 \le N, q \le 10^5;\ 1 \le m \le 2 \times 10^5)~
• ~m~ dòng tiếp theo, dòng thứ ~i~ ghi ba số nguyên dương ~u_i, v_i, d_i~ mô tả con đường hai chiều thứ ~i~ nối hai thành phố ~u_i, v_i~, và sẽ được khánh thành vào ngày ~d_i~ ~(1 \le u_i, v_i \le N;\ 1 \le d_i \le 10^9)~
• ~q~ dòng tiếp theo, dòng thứ ~i~ ghi hai số nguyên dương ~a_i, b_i~ lần lượt là thành phố đang ở và thành phố mà đoàn khách thứ ~i~ muốn đến tham quan ~(1 \le a_i, b_i \le N)~

Chú ý: Các số trên một dòng được ghi cách nhau một dấu cách.

Dữ liệu đầu ra

Gồm ~q~ dòng, dòng thứ ~i~ ghi số nguyên ~t_i~ là ngày sớm nhất mà đường đi từ thành phố ~a_i~ đến thành phố ~b_i~ được thông suốt.

Ràng buộc dữ liệu

• Có 50% số test tương ứng với 50% số điểm: ~N, m, q \le 200~.
• Có 25% số test tương ứng với 25% số điểm: ~N, m, q \le 2000~.
• Có 25% số test tương ứng với 25% số điểm: không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

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

OUTPUT

2
4
1
1