E. A Б хоёр ба өрөөнүүд

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

А Б хоёр програмчлалын тэмцээнд бэлдэж байлаа.

А Б хоёрын сурдаг их сургуулийн өрөөнүүд коридоруудаар холбогдсон байна. Их сургууль $n$ өрөөтэй ба $n - 1$ коридортой. Аль ч өрөөнөөс аль ч өрөөрүү коридоруудын тусламжтайгаар очиж чаддаг. Өрөөнүүд $1$-ээс $n$ хүртэл дугаарлагдсан байна.

Өдөр бүр А Б хоёр их сургуулийн нэг нэг өрөөнд сууж бодлого бодож бэлтгэл хийх ба бэлтгэлийн дараа нэг өрөөнд уулзан бодлогуудын талаар санал бодлоо ярилцдаг байна. А Б хоёрын уулзах өрөөнөөс нь бэлтгэл хийгдэх өрөөнүүд хүртэлх зай тэнцүү байх ёстой. Өрөө хоорондын зай гэдгээр тэдгээрийг холбох хамгийн богино замын дагуух ирмэгийн тоог хэлнэ.

Тэр хоёр өдөр бүр шинэ өрөөнд бэлтгэл хийдэг. Тэр хоёр $m$ өдрийн турш дээрх маягаар бэлтгэл хийж, уулзаж байх боломжтой хэдэн өрөө байгааг олно уу.

Оролт

Эхний мөрөнд их сургуулийн өрөөний тоо болох $n$ ($1 ≤ n ≤ 10^{5}$) байна.

Дараагийн $n - 1$ мөрөнд коридоруудыг тодорхойлно. $i$ ($1 ≤ i ≤ n-1$) дэхь мөрөнд $a_{i}$ ба $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$) гэсэн бүхэл тоонууд байх ба энэ нь $i$ дэхь коридор $a_{i}$ болон $b_{i}$ дугаарын өрөөнүүдийг холбохыг илэрхийлнэ.

Дараагийн мөрөнд хүсэлтийн тоо болох $m$ ($1 ≤ m ≤ 10^{5}$) байна.

Дараагийн $m$ мөрөнд хүсэлтүүдийг тодорхойлно. $j$ ($1 ≤ j ≤ m$) дэхь мөрөнд $x_{j}$ ба $y_{j}$ ($1 ≤ x_{j}, y_{j} ≤ n$) гэсэн бүхэл тоонууд байх ба энэ нь $j$ дэх өдөр А $x_{j}$ дугаарын өрөөнд, харин Б $y_{j}$ дугаарын өрөөнд бэлтгэл хийнэ гэсэн үг.

Гаралт

$m$ мөрөнд, $i$ ($1 ≤ i ≤ m$) дэх мөрөнд $i$ дэх өдөр А Б хоёр хэчнээн өрөөнд уулзаж бодлогоо ярилцах боломжтойг хэвлэнэ.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
4
1 2
1 3
2 4
1
2 3
Гаралт
1
Оролт
4
1 2
2 3
2 4
2
1 2
1 3
Гаралт
0
2

Тэмдэглэл

Эхний жишээнд $2$ болон $3$ дугаартай өрөөнөөс ижил зайд байх цор ганц өрөө нь $1$ дугаартай өрөө юм.

Сэтгэгдлүүдийг ачааллаж байна...