D. Толгодод авирах

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

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

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

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

Энэ бодлогод бяцхан Крисд хийх зүйл байхгүй. Харин толгодод авирагчдын тухай юм (мөн Крис тэдний нэг биш).

Шугам дээр байрласан $n$ толгод байх ба толгод тус бүр нэг төгсгөлийн цэг нь газар байх босоо шулуун хэлбэртэй байна. Толгодууд зүүнээс баруун тийш $1$-c $n$ хүртэл бүхэл тоонуудаар дугаарлагдсан. $i$-р толгод $x_{i}$ байрлалд босоо байрлах ба оройн өндөр нь $y_{i}$ байна. $a$ ба $b$ толгод бүрийн хувьд $b$ толгодын оройгоос $a$ толгодын орой харагдаж байвал тэдний оройнууд олсоор холбогдоно. Өөрөөр хоёр толгодын оройг холбосон хэсэг бусад толгодын хэсгүүдэд хүрэх эсвэл огтлолцоогүй байвал уг хоёр толгодын орой холбогдоно. Эдгээр олсуудыг ашиглан толгодод авирагчид толгодоос толгодын хооронд дамжиж чадна.

Авирагчдын $m$ баг байх ба баг бүр яг хоёр гишүүнтэй. $i$-р багийн эхний болон хоёрдугаар авирагчид харгалзан $a_{i}$-р болон $b_{i}$-р толгодуудын оройд байна. Тэд нэг толгодын орой дээр уулзахыг хүсч байна. Одоо хоёр аялагч бүр дараах үйл явцын дагуу хөдлөнө:

  1. хэрвээ авирагч бусад авирагчдын аль хэдийн байрласан эсвэл төгсгөлд нь ирж байгаа толгодын орой дээр байвал хуучин байсан авирагч уг толгоддоо үлдэнэ;
  2. бусад тохиолдолд авирагч өөрийн байгаа толгодын баруун талд байгаа олсоор хүрч болох мөн боломжит хамгийн баруун талын толгодыг авч түүнрүү авирах ба үйл явц цааш үргэлжилнэ (аялагч өөрийн байгаа толгодоос намхан оройтой толгодруу ч мөн авирч болно).

Авирагчдын баг бүрийн хувьд энэ хосын уулзах толгодын дугаарыг тодорхойл.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 10^{5}$) буюу толгодын тоо байна. Дараагийн $n$ мөрөнд толгодуудыг тодорхойлно. $i$-р мөр бүрт зайгаар тусгаарлагдсан хоёр бүхэл тоон утга $x_{i}$, $y_{i}$ ($1 ≤ x_{i} ≤ 10^{7}$; $1 ≤ y_{i} ≤ 10^{11}$) байх буюу $i$-р толгодын байрлал болон өндөр байна. Толгодууд $x_{i}$-н өсөх дарааллаар өгөгдөнө өөрөөр $i < j$-н хувьд $x_{i} < x_{j}$.

Оролтын дараагийн мөрөнд бүхэл тоон утга $m$ ($1 ≤ m ≤ 10^{5}$) байх буюу багуудын тоо байна. Дараагийн $m$ мөрөнд багуудыг тодорхойлно. $i$-р мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоон утга $a_{i}$, $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$) байх буюу $i$-р багийн авирагчдын байрлаж буй толгодуудын дугаар байна. $a_{i} = b_{i}$ байх боломжтой.

Гаралт

Нэг мөрөнд зайгаар тусгаарлагдсан $m$ бүхэл тоон утга байх ба энд $i$-р бүхэл тоо нь $i$-р багийн гишүүдийн уулзах толгодын дугаар байна.

Орчуулсан: Г.Мэндбаяр

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

Оролт
6
1 4
2 1
3 2
4 3
6 4
7 4
3
3 1
5 6
2 3
Гаралт
5 6 3 
Сэтгэгдлүүдийг ачааллаж байна...