81E орчуулах · Codeforces.mn

# Хосууд
Поликарпусын ангид түүнийг оруулаад нийт $n$ сурагч байдаг. Хэдэн өдрийн өмнө бүх сурагчид "Миний хамгийн сайн найз" нэртэй эссе бичсэн. Сурагч бүр эссегээ өөрийн ангийн хамгийн сайн нэг найздаа зориулан бичсэн юм. Хэрвээ $a$ сурагчийн хамгийн сайн найз нь $b$ сурагч бол $b$ сурагчийн хамгийн сайн найз нь $a$ сурагч байх албагүй гэдгийг санаарай.

Одоо багш спорт програмчлалын түүхийн музейд ангийнхаа бүх хүүхдүүдийг дагуулан явж байна. Сурагчид домогт баатрууд болох tourist, Petr, tomek, SnapDragon нарын тухай сэтгэл хөдөлгөм түүхийг сонсохоор зэхэж байлаа.

Багш сурагчдыг өөрийн хамгийн найзтайгаа хос болсон байхаар хос хосоор нь хуваахаар шийджээ. Тэр бүх сурагчдыг хос хосоор нь хувааж чадахгүй байж болох юм. Гэхдээ энэ асуудал биш. Учир нь тэр ийм боломжит хосууд аль болох олон байлгахыг л зорьж байлаа. Хэрвээ боломжит хамгийн олон тооны хосыг сонгох олон хувилбар байгаа бол тэр аль болох олон хүү-охин хос гаргаж авахыг хүсдэг. Мэдээж хэрэг сурагч бүр нэг л хосод орж болно.

## Оролт
Эхний мөр нь ангийн сурагчдын нийт тоо болох $n$ ($2 ≤ n ≤ 10^{5}$) бүхэл тоог агуулна. Дараагийн $n$ мөрүүд нь сурагчдын талаарх мэдээллийг мөр мөрөөр агуулна. Мөр бүр нь $f\_{i}, s\_{i}$ ($1 ≤ f\_{i} ≤ n, f\_{i} ≠ i, 1 ≤ s\_{i} ≤ 2$) хоёр бүхэл тоог агуулах бөгөөд $f\_{i}$ нь $i$-р сурагчийн хамгийн сайн найзын дугаарыг, $s\_{i}$ нь $i$-р сурагчийн хүйсийг илэрхийлнэ ($s\_{i} = 1$ бол хүү, $s\_{i} = 2$ бол охин).

## Гаралт
Гаралтын эхний мөрөнд $t$, $e$ хоёр бүхэл тоог хэвлэх бөгөөд $t$ нь дээр тодорхойлсон хосуудын хамгийн их тоог, $e$ нь тэдгээр хосуудаас хүү-охин төрлийн хосуудын хамгийн их тоог илэрхийлнэ. Дараа нь $t$ мөрүүд хэвлэх бөгөөд мөр бүр нь $a\_{i}, b\_{i}$ ($1 ≤ a\_{i}, b\_{i} ≤ n$) хос бүхэл тоонуудыг агуулна. Эдгээр нь $i$-р хосын сурагчдын дугаарууд юм. Хосуудыг ямар ч дарааллаар хэвлэж болно.

Хэрвээ хэд хэдэн зөв шийд байгаа бол тэдгээрийн аль нэгийг хэвлэнэ.

## Тэмдэглэл
**Эхний** жишээг зургаар харуулав. Зураг дээр ромбоор хөвгүүдийг, квадратаар охидыг, сумаар түүний хамгийн сайн найзыг илэрхийлсэн. Мөн үргэлжилсэн тод сумтай зураасаар хариултанд байгаа хосуудыг илэрхийллээ.

![](http://espresso.codeforces.com/b9824efb53ecbb31ebd292a3d20e943f23e5d0a0.png)

-- Даариймаа

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

Оролт

Гаралт

2 2
5 3
4 2

Оролт

Гаралт

Оролт

Гаралт