D. MST доторх ирмэгүүд

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

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

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

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

Танд ямар ч гогцоо болон олон тооны ирмэггүй чиглэлгүй, жинтэй, холбоост граф өгөгдөв.

Графын холбогдож буй мод гэдэг нь өгөгдсөн графын бүх оройнуудыг агуулах холбоост, цикллэг дэд граф болохыг дахин сануулъя. Модны жин гэдэг нь өгөгдсөн модны ирмэгүүдийн жингүүдийн нийлбэрийг хэлнэ. Графын хамгийн бага холбогдож буй мод (minimum spanning tree MST) гэдэг нь боломжит хамгийн бага жин бүхий графын холбогдож буй модыг хэлнэ. Ямар ч холбоост графын хувьд хамгийн бага холбогдож буй мод нь заавал оршин байх боловч ерөнхий тохиолдолд графын хамгийн бага холбогдож буй мод нь цор ганц биш байна.

Таны даалгавар бол өгөгдсөн графын ирмэг бүрийн хувьд дараах зүйлсийг тодорхойлох юм: уг ирмэг нь ямар ч MST-д багтсан эсвэл дор хаяж нэг MST-д багтсан эсвэл ямар ч MST-д багтаагүй болохыг тодорхойлно.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($2 ≤ n ≤ 10^{5}$, ) өгөгдөх ба эдгээр нь харгалзан графын ирмэгийн тоо болон ирмэгийн тоог илэрхийлнэ. Дараа нь $m$ мөрийн мөр болгонд 3 бүхэл тоо өгөгдөх ба эдгээр нь графын ирмэг "$a_{i}$ $b_{i}$ $w_{i}$" ($1 ≤ a_{i}, b_{i} ≤ n, 1 ≤ w_{i} ≤ 10^{6}, a_{i} ≠ b_{i}$)-г илэрхийлэх юм. Энд $a_{i}$ болон $b_{i}$ нь $i$-дахь ирмэгээр холбогдох оройнуудын дугаарууд бөгөөд $w_{i}$ нь уг ирмэгийн жин байна. Уг граф нь холбоост байх ба гогцоонууд болон олон тооны ирмэг агуулаагүй байна.

Гаралт

Бүх ирмэгүүдийн хариултуудыг $m$ мөрөнд хэвлэнэ. Хэрэв $i$-дахь ирмэг нь ямар ч MST-д багтсан байвал "any"; хэрэв $i$-дахь ирмэг нь дор хаяж нэг MST-д багтсан байвал "at least one"; хэрэв $i$-дахь ирмэг нь ямар ч MST-д багтаагүй байвал "none" гэж хэвлэнэ үү. Хариултуудыг ирмэгүүд нь оролтод өгөгдсөн дарааллаар хэвлэнэ үү.

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

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

Оролт
4 5
1 2 101
1 3 100
2 3 2
2 4 2
3 4 1
Гаралт
none
any
at least one
at least one
any
Оролт
3 3
1 2 1
2 3 1
1 3 2
Гаралт
any
any
none
Оролт
3 3
1 2 1
2 3 1
1 3 1
Гаралт
at least one
at least one
at least one

Тэмдэглэл

2-дахь жишээнд MSТ нь өгөгдсөн графын хувьд цорын ганц байх юм: энэ нь эхний 2 ирмэгийг агуулна.

3-дахь жишээнд өгөгдсөн графын хувьд ямар ч 2 ирмэг нь MST үүсгэх юм. Энэ нь ирмэг бүр нь дор хаяж нэг MST-д багтсан байна гэсэн үг юм.

Сэтгэгдлүүдийг ачааллаж байна...