A9682 | Mr. Kitayuta's Colorful Graph

Mr. Kitayuta has just bought an undirected graph consisting of $n$ vertices and $m$ edges. The vertices of the graph are numbered from 1 to $n$ . Each edge, namely edge $i$ , has a color $c_{i}$ , connecting vertex $a_{i}$ and $b_{i}$ .

Mr. Kitayuta wants you to process the following $q$ queries.

In the $i$ -th query, he gives you two integers — $u_{i}$ and $v_{i}$ .

Find the number of the colors that satisfy the following condition: the edges of that color connect vertex $u_{i}$ and vertex $v_{i}$ directly or indirectly.

The first line of the input contains space-separated two integers — $n$ and $m$ ( $2<=n<=100,1<=m<=100$ ), denoting the number of the vertices and the number of the edges, respectively.

The next $m$ lines contain space-separated three integers — $a_{i}$ , $b_{i}$ ( $1<=a_{i}<b_{i}<=n$ ) and $c_{i}$ ( $1<=c_{i}<=m$ ). Note that there can be multiple edges between two vertices. However, there are no multiple edges of the same color between two vertices, that is, if $i≠j$ , $(a_{i},b_{i},c_{i})≠(a_{j},b_{j},c_{j})$ .

The next line contains a integer — $q$ ( $1<=q<=100$ ), denoting the number of the queries.

Then follows $q$ lines, containing space-separated two integers — $u_{i}$ and $v_{i}$ ( $1<=u_{i},v_{i}<=n$ ). It is guaranteed that $u_{i}≠v_{i}$ .

For each query, print the answer in a separate line.