Đồ thị nhiều màu

Điểm: 8,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Dart, Go, Groovy, Java, Javascript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Typescript, Zig

Cho đồ thị vô hướng có $n$ đỉnh và $m$ cạnh. Các đỉnh được đánh số từ $1$ đến $n$ . Mỗi cạnh $i$ có một màu $c_{i}$ , nối hai đỉnh $a_{i}$ và $b_{i}$ .

Hai đỉnh $u$ và $v$ được gọi là liên thông theo màu $c$ nếu chỉ dùng các cạnh có màu $c$ , ta đi được từ $u$ đến $v$ (trực tiếp hoặc gián tiếp).

Với mỗi truy vấn $(u, v)$ , hãy đếm số màu $c$ sao cho $u$ và $v$ liên thông theo màu $c$ .

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ .
$m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a_{i}$ , $b_{i}$ , $c_{i}$ — mô tả một cạnh nối $a_{i}$ với $b_{i}$ có màu $c_{i}$ .
Dòng tiếp theo chứa một số nguyên $q$ — số truy vấn.
$q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_{i}$ , $v_{i}$ .

Có thể tồn tại nhiều cạnh giữa cùng hai đỉnh, nhưng không có hai cạnh nào trùng cả ba giá trị $(a_{i}, b_{i}, c_{i})$ .

Dữ liệu ra

Với mỗi truy vấn, in ra số màu thoả mãn trên một dòng.

Ràng buộc

$2 \leq n \leq 10^{5}$
$1 \leq m \leq 10^{5}$
$1 \leq a_{i} < b_{i} \leq n$
$1 \leq c_{i} \leq m$
$1 \leq q \leq 10^{5}$
$1 \leq u_{i}, v_{i} \leq n$ và $u_{i} \neq v_{i}$

Ví dụ

Input	Output	Giải thích
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	Đỉnh $1$ và $2$ liên thông theo màu $1$ (cạnh $1$ – $2$ ) và màu $2$ (cạnh $1$ – $2$ ). Đỉnh $3$ và $4$ liên thông theo màu $3$ (qua đỉnh $2$ ). Đỉnh $1$ và $4$ không liên thông theo màu nào.
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	Màu $1$ là hình sao tâm $5$ , màu $2$ là đường thẳng $1$ – $2$ – $3$ – $4$ . Cặp $(1, 4)$ liên thông theo cả hai màu.

Bình luận

Không có bình luận tại thời điểm này.