Đồ thị nhiều màu

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\le n\le {10}^5$
• $1\le m\le {10}^5$
• $1\le a_i<b_i\le n$
• $1\le c_i\le m$
• $1\le q\le {10}^5$
• $1\le u_i,v_i\le n$ và $u_i\ne v_i$

Ví dụ