D. Зөвхөн Берландын зам биш

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

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

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

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

Берландын засгийн газар хөрш орнуудтайгаа харилцаагаа сайжруулахаар шийдвэрлэв. Ингээд нэн тэргүүнд, Берланд болон хөрш орнуудын хотуудыг хоорондоо замаар холбогдсон байхаар шинэ замууд барихаар шийдэв.

Берландад болон хөрш орнуудад нь нийт $n$ тооны хот байх ба нийт яг $(n - 1)$ тооны хоёр урсгалтай замтай. Сүүлийн үед санхүүгийн хямралаас шалтгаалан Берландын засгийн газар мөнгөний хэрэгцээ, шаардлагатай тулгарсан учир шинэ зам барихын тулд зарим хуучин замыг хаах хэрэгтэй болов. Өдөр бүр нэг хуучин замаа хааж, тэр дор нь нэг шинэ зам барих боломжтой байв.

Хот тус бүрээс бусад бүх хот руу хүрэх боломжтой шинэ замууд барих (хуучнаа хааж) ажилд нийт хэдэн өдөр шаардагдахыг тооцоолж олно уу.

Оролт

Эхний мөрөнд $n$ ($2 ≤ n ≤ 1000$) гэсэн бүхэл тоо агуулагдах ба энэ нь Берландын болон хөрш орнуудын хотын тоог харуулна. Дараагийн $(n - 1)$ мөрүүд нь замын тодорхойлолтыг агуулна. Зам тус бүр нь өөр хоорондоо зайгаар тусгаарлагдсан $a_{i}$, $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}$) гэсэн хос тоогоор илэрхийлэгдэх ба энэ нь тухайн замаар холбогдож буй хоёр хотыг илэрхийлж байна. Хоёр хотын хооронд нэгээс илүү зам байх боломжгүй юм.

Гаралт

$t$ гэсэн тоог хэвлэ. Энэ нь хот тус бүрээс бусад хот руу хүрэх гарцыг нээсэн хоёр урсгалтай замыг барихад хамгийн багадаа зарцуулагдах өдрийн тоо байна. Дараа нь $t$ мөрөнд хуучин замуудыг хааж шинэ замууд барих төлөвлөгөөг хэвлэнэ. Мөр бүр нэг өдрийг $i$ $j$ $u$ $v$ гэсэн форматаар дүрслэх ба энэ нь $i$ болон $j$ хотуудын хоорондох зам хаалттай бөгөөд $u$ болон $v$ хотуудын хооронд шинэ зам баригдаж байгааг илэрхийлнэ. Хотуудыг $1$-ээс эхэлж дугаарлана. Хэрэв хэдэн хэдэн зөв хариу байвал нэгийг хэвлэнэ үү.

Орчуулсан: Энхгэрэл

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

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