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$-дэх ирмэгүүд нь ямар ч дан өнгөөр холбогдоогүй.
Сэтгэгдлүүдийг ачааллаж байна...