Mr. Kitayuta has just bought an undirected graph with 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 ≤ 105, 1 ≤ m ≤ 105), denoting the number of the vertices and the number of the edges, respectively.The next m lines contain space-separated three integers - ai, bi(1 ≤ ai bi ≤ n) and ci(1 ≤ ci ≤ 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, (ai, bi, ci) ≠ (aj, bj, cj).The next line contains a integer- q(1 ≤ q ≤ 105), denoting the number of the queries.Then follows q lines, containing space-separated two integers - ui and vi(1 ≤ ui, vi ≤ n). It is guaranteed that ui ≠ vi.
输出描述:
For each query, print the answer in a separate line.
示例1
输入
4 5<br />1 2 1<br />1 2 2<br />2 3 1<br />2 3 3<br />2 4 3<br />3<br />1 2<br />3 4<br />1 4<br />5 7<br />1 5 1<br />2 5 1<br />3 5 1<br />4 5 1<br />1 2 2<br />2 3 2<br />3 4 2<br />5<br />1 5<br />5 1<br />2 5<br />1 5<br />1 4<br />
输出
2<br />1<br />0<br />1<br />1<br />1<br />1<br />2<br />
备注:
Let's consider the first sample. The figure above shows the first sample. Vertex 1 and vertex 2 are connected by color 1 and 2. Vertex 3 and vertex 4 are connected by color 3. Vertex 1 and vertex 4 are not connected by any single color.
加载中...