C. Мод будъя

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

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

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

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

Чамд $n$ оройтой мод ба хавтгайн аль ч 3-н цэг нь нэг шулуунд оршдоггүй $n$ цэг өгөгджээ.

Өгөгдсөн оройнуудын тусламжтайгаар хавтгай дээрх модыг буд.

Өөрөөр хэлбэл чи модны орой болгоныг хавтгай цэгүүдтэй харилцан нэгэн утгатай харгалзуулах ёстой юм. Хэрэв хоёр орой ирмэгээр холбогдсон бол тэр 2-т харгалзах хавтгай цэгүүд будагтай хэрчимээр холбогдсон байх ёстой. Мөн хөрш биш ирмэгүүдэд харгалзах хэрчимүүд огтлолцоогүй байх ёстой. Хөрш ирмэгт харгалзах хэрчимүүд яг 1 ерөнхий цэгтэй байх ёстой.

Оролт

Эхний мөрөнд $n$ ($1 ≤ n ≤ 1500$) гэсэн бүхэл тоо байна, энэ нь модны оройн тоо буюу хавтгай дээрх цэгийн тоо.

Дараагийн $n - 1$ мөр бүрт зайгаар тусгаарлагдсан $u_{i}$ ба $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$, $u_{i} ≠ v_{i}$) гэсэн 2 тоо байрлана -- $i$-дэх ирмэгээр холбогдсон оройн дугаар.

Дараагийн $n$ мөрөнд зайгаар тусгаарлагдсан $x_{i}$ ба $y_{i}$ ($ - 10^{9} ≤ x_{i}, y_{i} ≤ 10^{9}$) гэсэн 2 тоо байна, энэ нь $i$-дэх цэгийн кординат.

Өгөгдсөн бодлого бүр боломжтой гэж мэдэгдэж байгаа.

Гаралт

$1$-ээс $n$ хүртэлх ялгаатай $n$ тоог хэвлэхдээ $i$-дэх тоо нь $i$ дэх хавтгайн цэгт харгалзах модны оройн дугаар байхаар хэвлэ.

Олон хувилбар хариу байгаа бол аль нэгийг нь л хэвлэхэд болно.

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

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

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

Тэмдэглэл

Жишээндээрх боломжит хувилбарийг дүрсэлбэл:

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