D. Метро

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

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

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

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

Бүх Берланд хотуудад метронууд нь классик схемтэй байдаг ба энэ нь $n$ буудлыг $n$ холбоосоор холбосон байдаг. Ямартай ч классик схем нь аль ч буудлаас бусад буудалруу очиж чаддаг. Холбоосын аль ч чиглэлээр зорчиж болно. Бүх хос буудлуудын хувьд нэгээс ихгүй зам байна.

Берланд математикчид ямарч классик хэлбэрийн схем нь цагирган зам олддог гэж баталсан байна. Бас цагирган зам нь ганцхан байдаг. Өөрөөр хэлбэл классик схемд аль нэг буудлыг 1-ээс олон дайрахгүйгээр цикл олддог гэсэн үг юм.

Энэ нээлт нь нийгэмд маш их нөлөө үзүүлсэн бөгөөд хүмүүс буудлуудыг цагирган замд хүрэх зайгаар нь харьцуулж байв. Жишээ нь, нэг иргэн "Би цагирган замаас 3 холбоосын цаана амьдардаг" гэж хэлэхэд, өөр нэгэн "ямар азгүй юм бэ, би цагирган замаас 1 холбоосны цаана амьдардаг". Удалгүй интернэтэд цагирган замаас хэр хол амьдардгийг олж мэдэх гэсэн хүмүүс их болжээ.

Берландын засгийн газар энэхүү үймээнийг таслан зогсоож хяналт тавихаар болжээ. Таны даалгавар бол бүх буудлын хувьд цагирган зам хүртэл хэдэн холбоос дамжихыг олж мэдэх юм.

Оролт

Эхний мөрөнд $n$ ($3 ≤ n ≤ 3000$) бүхэл тоо, $n$ бол классик схемийн буудал болон холбоосын тоо. Дараагийн $n$ мөр холбоосуудын мэдээллийг агуулна. Мөр болгон $x_{i}, y_{i}$ ($1 ≤ x_{i}, y_{i} ≤ n$) бүхэл тоо байх ба $x_{i}$ буудлууд $y_{i}$ холбоосоор холбогддог гэсэн үг юм. Буудлууд 1-ээс $n$ хүртэл дурын байдлаар дугаарлагдана.Бүх $x_{i}, y_{i}$-н хувьд $x_{i} ≠ y_{i}$ байх ба бүх хос буудлуудын хувьд нэгээс ихгүй зам байна. Өгөгдсөн өгөгдөл заавал классик схем байна.

Гаралт

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

Орчуулсан: Б.Алтангэрэл

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

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