Thành phố HP xinh đẹp có địa điểm được nối với nhau bởi con đường hai chiều đảm bảo bất kỳ hai địa điểm nào cũng đến được nhau thông qua các các con đường này.
Thành phố HP dự định xây công viên giải trí ở trong địa điểm, tuy nhiên theo chủ trương “của dân, do dân và vì dân” nên các nhà lãnh đạo quyết định hỏi ý kiến của mọi người. Những người dân ở địa điểm mong muốn công viên giải trí được xây dựng ở địa điểm .
Các nhà lãnh đạo của thành phố HP đã cử ra phóng viên uy tín đi hỏi, phóng viên thứ sẽ xuất phát từ địa điểm , đi đến địa điểm theo con đường ngắn nhất và sẽ hỏi một người dân bất kỳ (vì mọi người dân ở địa điểm đó đều có câu trả lời như nhau) ở mỗi địa điểm đi qua (tính cả và ). Sau khi hỏi xong, phóng viên đó sẽ báo cáo ra địa điểm mà có quá nửa số người dân mà phóng viên đã hỏi mong muốn xây dựng công viên giải trí. Nếu không tìm được địa điểm như vậy thì phóng viên đó sẽ không báo cáo.
Yêu cầu: Với mỗi phóng viên bạn cần đưa ra báo cáo của phóng viên đó hoặc in ra nếu phóng viên đó không tìm được địa điểm thỏa mãn.
Dữ liệu:
Dòng đầu tiên chứa số nguyên là số địa điểm;
Dòng tiếp theo chứa số nguyên, số thứ là ;
Dòng thứ trong dòng tiếp theo chứa hai số nguyên mô tả một con đường nối hai địa điểm và ;
Dòng tiếp theo chứa số nguyên là số phóng viên;
Dòng thứ trong dòng tiếp theo chứa hai số nguyên mô tả con đường phóng viên thứ đi.
Kết quả:
Ghi ra dòng, dòng thứ là báo cáo của phóng viên hoặc in ra nếu phóng viên đó không tìm được địa điểm thỏa mãn.
Ví dụ:
Dữ liệu:
6
1 1 1 2 2 2
1 2
1 3
2 4
2 5
3 6
3
4 2
4 5
4 6
Kết quả:
-1
2
1
Giải thích:
Các giá trị hỏi được của phòng viên đầu tiên theo thứ tự là: , không có giá trị nào xuất hiện quá nửa;
Các giá trị hỏi được của phòng viên thứ hai theo thứ tự là: , giá trị xuất hiện lần;
Các giá trị hỏi được của phòng viên thứ ba theo thứ tự là: , giá trị xuất hiện lần.
Ràng buộc:
Có số test ứng với số điểm của bài thỏa mãn điều kiện ;
số test khác ứng với số điểm của bài thỏa mãn điều kiện ;
số test khác ứng với số điểm của bài thỏa mãn điều kiện địa điểm chỉ có đường nối trực tiếp đến và ;
số test còn lại ứng với số điểm của bài không có điều kiện gì thêm.
