Đất nước màu mè
View as PDFĐất nước Bình Dương có ~n~ thành phố và ~m~ đường đi hai chiều giữa chúng. Các thành phố được đánh số từ ~1~ đến ~n~. Con đường thứ ~i~ có màu ~c_i~, kết nối thành phố ~a_i~ với thành phố ~b_i~.
Để giải quyết vấn nạn tắc đường, tổng thống Bình Dương đưa ra ~q~ câu hỏi.
Câu hỏi thứ ~i~ gồm hai số nguyên ~u_i~ và ~v_i~.
Tìm số lượng màu thỏa mãn: Với mỗi màu, chỉ dùng những con đường có màu này có thể đi từ thành phố ~u_i~ tới ~v_i~.
Input
Dòng đầu chứa hai số nguyên ~n~ và ~m~ (~2 \le n \le 10^5~, ~1 \le m \le 10^5~) — số thành phố và số con đường.
~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~a_i~, ~b_i~ và ~c_i~ (~1 \le a_i < b_i \le n~ và ~1 \le c_i \le m~).
Lưu ý các con đường là hai chiều, có thể có nhiều con đường giữa hai thành phố. Tuy nhiên, không có nhiều con đường cùng màu giữa hai thành phố, nói cách khác, nếu ~i \ne j~ thì ~(a_i, b_i, c_i) \ne (a_j, b_j, c_j)~.
Dòng tiếp theo chứa số nguyên ~q~ (~1 \le q \le 10^5~) — số lượng câu hỏi.
~q~ dòng cuối cùng, mỗi dòng chứa hai số nguyên ~u_i~ và ~v_i~ (~1 \le u_i, v_i \le n~ và ~u_i \ne v_i~).
Output
Với mỗi câu hỏi, in ra đáp án trên một dòng.
Sample Input 1
4 5
1 2 1
1 2 2
2 3 1
2 3 3
2 4 3
3
1 2
3 4
1 4
Sample Output 1
2
1
0
Sample Input 2
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
Sample Output 2
1
1
1
1
2
Notes
Ở ví dụ thứ nhất:
Có thể kết nối thành phố ~1~ với thành phố ~2~ chỉ dùng màu ~1~ hoặc chỉ dùng màu ~2~.
Có thể kết nối thành phố ~3~ với thành phố ~4~ chỉ dùng màu ~3~.
Không thể kết nối thành phố ~1~ với thành phố ~4~ nếu chỉ dùng một màu.
Comments
Tham khảo code tại đây: https://ideone.com/2jnspf
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.