F. Аалзнууд

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

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

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

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

Ээж нь Петяд тоглоомоо ялгаж цэгцлээд заримыг нь хаяхыг даалгасан тул Петя тоглоомуудаа цэгцэлж эхлэв. Ийнхүү бүтэн хайрцаг тоглоомон аалз олжээ. Эдгээр аалзнууддаа Петя маш дуртай учир хаяхыг хүссэнгүй.

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

Аалз гэдэг нь $k$ ширхэг шүртэй холбогдсон $k-1$ ширхэг утас юм. Утас бүр хоёр шүртэй холбогдох ба аалзыг бүрдүүлж байгаа ямар ч хос шүр шууд утсаар холбогдоно эсвэл бусад утас болон шүрнүүдээр дамжин холбогдсон байж болно.

Петя аалзнуудыг холбохдоо шууд хоёр шүрийг нааж нийлүүлэх тухай бодож байв. Утас бүрийн урт $1$ байна. Шүрний хэмжээг тооцохгүй байж болно. Доорх зурагнаас шүрнүүдээр яаж холбогдож болохыг харж болно. Түүнчлэн аалзнуудыг наагаад гарсан үр дүн нь бас аалз байх ёстой.

Петя бүх аалзаа хооронд нь нааж дуусаад үүссэн тоглоомын уртыг хэмжинэ. Хос шүрний хоорондох зай нь энэ хоёр шүрийг холбож байгаа утаснуудын нийлбэр урттай ижил байна. Үүссэн тоглоомын урт нь хамгийн хол хоёр шүрний хоорондох зай юм. Петя байж болох хамгийн урт аалзыг бүтээхийг хүсч байна.

Доорх зурагт хоёрдугаар жишээний хоёр аалзыг харуулсан байна. Бид эхний аалзны хоёрдугаар шүрийг хоёрдугаар аалзны нэгдүгээр шүртэй нааж чадна. Зурган дээр хамгийн урт дарааллыг үүсгэж байгаа аалзнуудын утсуудыг тодруулсан байна.

Оролт

Оролтын файлын эхний мөрөнд аалзнуудын тоог илэрхийлэх нэг бүхэл тоо $n$ ($1 ≤ n ≤ 100$) байна.

Дараагийн $n$ мөрөнд аалз бүрийн тодорхойлолтыг агуулна: $n_{i}$ ($2 ≤ n_{i} ≤ 100$)-бүхэл тоон утга нь шүрний тоо мөн $n_{i} - 1$ ширхэг утсаар холбогдсон хос шүрний дугааруудыг агуулна. Аалз бүрийг үүсгэж байгаа шүрнүүд $1$-ээс $n_{i}$ хүртэл дугаарлагдана.

Гаралт

Ганц ширхэг тоо хэвлэх ба энэ нь боломжит хамгийн урт аалзны урт юм.

Орчуулсан: Г.Мэндбаяр

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

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