Hệ thống hang động ở một khu bảo tàng thiên nhiên của một tỉnh miền Trung rất nổi tiếng và thu hút một lượng đông đảo khách du lịch tới tham quan, khám phá cảnh đẹp huyền bí dưới lòng đất.
Để tránh cho khách du lịch khỏi đi lòng vòng trong một khu vực nào đó, ở một số hang người ta ngăn bớt lối ra, đảm bảo sao cho giữa hai hang bất kỳ trong chương trình “Khám phá thế giới của Hades” (Hades – chúa tể của cõi âm) chỉ có một đường đi duy nhất tới nhau. Ngoài ra, ở mỗi hang đều có đặt máy hướng dẫn. Ở tại hang , khách chỉ cần nhập vào số nguyên – hang mình muốn tới, máy sẽ hiển thị số nguyên – hang trực tiếp nối với và là nơi tiếp theo khách phải di chuyển tới. Ví dụ, với sơ đồ hang ở hình dưới đây, tại hang số nếu khách muốn tới hang thì máy sẽ chỉ là cần đi tới hang . Tới hang mới và tiếp tục tra cứu dần dần khách sẽ tới được nơi mình muốn đến.
Cho là số đường đi nối trực tiếp nối hai hang và cặp số cho biết có đường đi nối trực tiếp hai hang và và truy vấn, mỗi truy vấn là một cặp số và , trong đó là hang nơi khách đang đứng, nơi khách muốn đến. Hãy xác định số hiển thị trên màn hình ứng với mỗi truy vấn.
Dữ liệu:
Dòng đầu tiên chứa một số nguyên ;
Dòng thứ trong dòng sau chứa hai số nguyên và ;
Dòng tiếp theo chứa số nguyên ;
Dòng thứ trong dòng sau chứa hai số nguyên và .
Kết quả:
Đưa ra số nguyên, mỗi số trên một dòng là kết quả của các lần tra cứu.
