D. Ноён Китаютагийн өнгө өнгийн граф

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

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

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

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

Ноён Китаюта $n$ орой, $m$ ирмэгтэй, чиглэлгүй граф худалдан авчээ. Графын оройнуудыг 1-ээс $n$ хүртэл дугаарласан ба $i$-р ирмэг $c_{i}$ гэсэн өнгөтэй бөгөөд $a_{i}$, $b_{i}$ оройг холбодог.

Ноён Китаюта дараах $q$ хүсэлтийг гүйцэлдүүлэхийг хүсчээ. $i$-р хүсэлтэнд $u_{i}$ ба $v_{i}$ гэсэн хоёр бүхэл тоо өгөгдөнө.

$u_{i}$ ба $v_{i}$ оройнуудыг (шууд болон шууд бусаар) зөвхөн тэр өнгийн ирмэгүүдээр холбож чадах өнгөнүүдийн тоог ол.

Оролт

Эхний мөрөнд харгалзан оройн тоо ба ирмэгийн тоог илэрхийлэх $n$ ба $m$ $(2 ≤ n ≤ 10^{5}, 1 ≤ m ≤ 10^{5})$ тоонууд зайгаар тусгаарлагдан өгөгдөнө.

Дараагийн $m$ мөр бүрт $a_{i}$, $b_{i}(1 ≤ a_{i} < b_{i} ≤ n)$ ба $c_{i}(1 ≤ c_{i} ≤ m)$ тоонууд зайгаар тусгаарлагдан өгөгдөнө. Хоёр орой олон ирмэгээр холбогдсон байж болохыг анхаараарай. Гэхдээ аль ч хоёр оройг ижил өнгийн хоёр ирмэгүүдээр холбоогүй байна. Өөрөөр хэлбэл $i ≠ j$-ийн хувьд $ (a_{i}, b_{i}, c_{i}) ≠ (a_{j}, b_{j}, c_{j})$ байна.

Дараагийн мөрөнд хүсэлтийн тоо болох $q$ $(1 ≤ q ≤ 10^{5})$ тоо өгөгдөнө.

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