#886. GUIDE - Chỉ đường

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

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 s , khách chỉ cần nhập vào số nguyên d – hang mình muốn tới, máy sẽ hiển thị số nguyên t – hang trực tiếp nối với s 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ố 5 nếu khách muốn tới hang 4 thì máy sẽ chỉ là cần đi tới hang 3 . 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 n là số đường đi nối trực tiếp nối hai hang và n cặp số a_i, b_i cho biết có đường đi nối trực tiếp hai hang a_i b_i\ (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i, i = 1 ÷ n) m truy vấn, mỗi truy vấn là một cặp số s d , trong đó s là hang nơi khách đang đứng, d 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 n\ (2 ≤ n ≤ 10^5) ;
  • Dòng thứ i trong n dòng sau chứa hai số nguyên a_i b_i ;
  • Dòng tiếp theo chứa số nguyên m\ (1 ≤ m ≤ 10^5) ;
  • Dòng thứ j trong m dòng sau chứa hai số nguyên s_j d_j\ (1 ≤ s_j, d_j ≤ n, s_j ≠ d_j) .

Kết quả:

  • Đưa ra m 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.

Ví dụ:

Dữ liệu:

5
1 2
1 3
1 4
3 5
3
5 2
1 4
4 3

Kết quả:

3
4
1