Codeforces Round #803 (Div. 2)
05:53:13 |
Codeforces Round #804 (Div. 2)
7 өдрийн дараа |
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$-р оройнууд ямар ч дан өнгөөр холбогдоогүй байна.