C. Шуудангийн тамга

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

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

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

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

Нэгэн өдөр Боб дугтуйтай захиа хүлээн авчээ. Берландын шуудангийн ажилчид $«A»$ хотоос шууд $«B»$ хот руу илгээсэн захиаг $«A B»$ эсвэл $«B A»$ гэж тамгалдаг болохыг тэр мэддэг байв. Гэвч харамсалтай нь илгээгчийн хотоос хүлээн авагчийн хот руу шууд илгээнэ гэдэг ихэнхдээ боломжгүй байдаг тул захиа дундын хэд хэдэн хотоор дамжин илгээгддэг байна. Шуудангийн ажилчид зарим хотыг нэгээс олон удаа агуулсан маршрутаар захиаг хэзээ ч илгээдэггүй. Боб шуудангийн ажилчид захиаг маш нарийн, үнэн зөв тамгалдаг гэдэгт итгэлтэй байдаг.

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

Оролт

Эхний мөр нь дугтуйн дээрхи шуудангийн тамганы тоог харуулах $n$ ($1≤n≤10^{5}$) бүхэл тоог агуулна. Дараагийн $n$ мөрүүд тус бүр нь тамгыг тодорхойлох $2$ бүхэл тоог агуулна. Тамга тус бүр нь захиа илгээгдсэн хотуудын дугаараар тодорхойлогдоно. Хотын дугаар нь $1$-ээс $10^{9}$ хүртэлх бүхэл тоо байна. Бүх хотын дугаарууд нь ялгаатай байдаг. Захиа нэг хотоос нөгөө рүү илгээгдэх бүрт дугтуйн дээр нэг тамга дарагдана. Дарагдсан тамгууд нь боломжит маршруттай таарч байдаг.

Гаралт

Захианы боломжит $2$ хувилбарын аль нэгнийх нь хотуудын дугаарыг харуулах $n+1$ тоог хэвлээрэй.

Орчуулсан: Солонго

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

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