Codeforces Round #803 (Div. 2)
2 өдрийн дараа |
Codeforces Round #804 (Div. 2)
8 өдрийн дараа |
B. Ноён Китаюта-ын өнгөт граф
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Ноён Китаюта $n$ орой болон $m$ ирмэгээс тогтох чиглэлгүй граф худалдан авчээ. Графын оройнууд нь 1-ээс $n$ хүртэл дугаарлагдсан байв. Ирмэг бүрийн хувьд, тухайлбал $i$-дахь ирмэг, $c_{i}$ өнгөтэй бөгөөд, $a_{i}$ болон $b_{i}$ оройнуудыг холбоно.
Ноён Китаюта таныг дараах $q$ ширхэг асуултад хариулахыг хүсэж байгаа юм.
$i$-дахь асуултад, тэрээр танд 2 бүхэл тоо -- $u_{i}$ болон $v_{i}$-г өгнө.
Дараах нөхцөлүүдийг хангах өнгөнүүдийн тоог олно уу: тухайн өнгийн ирмэгүүд нь $u_{i}$ болон $v_{i}$ оройнуудыг шууд эсвэл шууд бусаар холбоно.
Оролт
Эхний мөрөнд харгалзан оройны тоо болон ирмэгийн тоог тэмдэглэх зайгаар тусгаарлагдсан 2 бүхэл тоо -- $n$ болон $m$ ($2 ≤ n ≤ 100, 1 ≤ m ≤ 100$) өгөгдөнө.
Дараагийн $m$ мөр болгонд зайгаар тусгаарлагдсан 3-н бүхэл тоо -- $a_{i}$, $b_{i}$ ($1 ≤ a_{i} < b_{i} ≤ n$) болон $c_{i}$ ($1 ≤ c_{i} ≤ m$) өгөгдөнө. 2 оройны хооронд олон тооны ирмэгүүд байж болохыг анхаарна уу. Гэхдээ, 2 оройны хооронд олон тооны ижил өнгийн ирмэгүүд байхгүй байна, өөрөөр хэлбэл, хэрэв $i ≠ j$, $(a_{i}, b_{i}, c_{i}) ≠ (a_{j}, b_{j}, c_{j})$ байх юм.
Дараагийн мөрөнд асуултын тоог тэмдэглэх бүхэл тоо -- $q$ ($1 ≤ q ≤ 100$) өгөгдөнө.
Үүний дараагийн $q$ мөр болгонд, зайгаар тусгаарлагдсан 2 бүхэл тоо -- $u_{i}$ болон $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$) өгөгдөнө. Мөн $u_{i} ≠ v_{i}$ байх юм.
Гаралт
Асуулт бүрийн хувьд хариултуудыг тусдаа мөрөнд хэвлэнэ үү.
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
4 5 1 2 1 1 2 2 2 3 1 2 3 3 2 4 3 3 1 2 3 4 1 4
Гаралт
2 1 0
Оролт
5 7 1 5 1 2 5 1 3 5 1 4 5 1 1 2 2 2 3 2 3 4 2 5 1 5 5 1 2 5 1 5 1 4
Гаралт
1 1 1 1 2
Тэмдэглэл
Эхний жишээг авч үзье.
Дээрх зураг нь эхний жишээг үзүүлнэ.
- $1$ болон $2$-дахь ирмэгүүд нь $1$ болон $2$ өнгөөр холбогдсон.
- $3$ болон $4$-дэх ирмэгүүд нь $3$ өнгөөр холбогдсон.
- $1$ болон $4$-дэх ирмэгүүд нь ямар ч дан өнгөөр холбогдоогүй.