E. Газрын зургийг нөхөн сэргээх

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

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

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

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

Археологчид нэн эртний улс болох Триландын талаар зарим нэг мэдээллийг олжээ. Бид Триланд нь хоорондоо $(n - 1)$ замаар холбогдсон $n$ ширхэг хотоос бүрдсэн гэдэгт итгэлтэй байж болох бөгөөд аль ч хотоос өөр нэг хот руу ганц л замаар очиж болно. Харамсалтай нь Триландын замыг нарийвчлан дүрсэлсэн мэдээлэл алдагдсан ба одоо археологчидын ашиглаж болох цорын ганц зүйл нь зэргэлдээ хотуудын мэдээлэл болоод байгаа юм.

Хэрэв нэг хотоос нөгөө хот хүртэл хамгийн ихдээ $2$ замаар дамжин очиж болдог бол тэдгээр хотуудыг зэргэлдээ хотууд гэнэ. Түүнчлэн ямар нэг хотыг өөртэй нь зэргэлдээ гэж үзнэ. Саяхны малталтаас археологчид $n$ ширхэг тэмдэглэл олсон бөгөөд тэмдэглэл бүр нь Триландын хот бүрийн зэргэлдээ хотуудын жагсаалтыг агуулж байгаа юм. Гэвч харамсалтай нь тэмдэглэл дээрх хотууд нь аль хотын зэргэлдээ хотууд болохыг тэмдэглээгүй байв.

Археологч нарт олдсон мэдээлэлтэй тохирч байхаар Триландын газрын зургийг ямар нэгэн хэлбэрээр сэргээн өгч туслана уу.

Оролт

Эхний мөрөнд Триландын хотуудын тоо болох бүхэл $n$ ($2 ≤ n ≤ 1000$) тоо өгөгдөнө.

Дараагийн $n$ мөрөнд мөр бүрд зэргэлдээ хотуудын талаархи олдсон тэмдэглэл өгөгдөх ба мөр бүрийн эхэнд тэмдэглэлд дурдагдсан хотуудын тоог илэрхийлэх $k$ ($1 ≤ k ≤ n$) тоо байна. Тэмдэглэл доторх бүх тоо ($k$ тоог тооцохгүй) ялгаатай байна. Мөн өгөгдсөн мэдээллийн дагуу дор хаяж нэг ширхэг боломжит газрын зураг олдоно.

Гаралт

Триландын замыг илэрхийлсэн $(n-1)$ ширхэг хос тоонуудыг хэвлэнэ. $i$-р мөр $a_{i}, b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $a_{i} ≠ b_{i}$) гэсэн $2$ бүхэл тоог заавал агуулсан байх ба эдгээрээр $a_{i}$ ба $b_{i}$ дугаартай хотуудын хооронд зам байгааг харуулж байгаа юм.

Таны хариулт дээр дурдсан зэргэлдээ хотуудын тодорхойлолтыг хангаж байх ёстой бөгөөд замуудыг хэвлэхдээ дараалал хамаарахгүй хэвлэж болох ба хоорондоо замаар холбогдсон хотуудыг хэвлэхдээ мөн адил дараалал хамаарахгүй хэвлэж болно. Хэрэв олон зөв хариулт байгаа бол нэгийг л хэвлэхэд болно.

Орчуулсан: Баатархүү

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

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