human
I found an interesting problem on https://codeforces.com/problemset/problem/505/B:
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.

-----Input-----

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}.

-----Output-----

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

-----Examples-----
Input
4 5
1 2 1
1 2 2
2 3 1
2 3 3
2 4 3
3
1 2
3 4
1 4

Output
2
1
0

Input
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

Output
1
1
1
1
2


-----Note-----

Let's consider the first sample.  [Image]   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.

I tried it in Python, but could not do it. Can you solve it?

Write me a Python program to 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?
assistant
#Here is Python program to 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.

from collections import defaultdict

def main():
    n, m = list(map(int, input().split()))
    edges = defaultdict(lambda: defaultdict(list))
    for _ in range(m):
        a, b, c = list(map(int, input().split()))
        d = edges[c]
        d[a].append(b)
        d[b].append(a)

    def dfs(t):
        chain.add(t)
        dd = color.get(t, ())
        for y in dd:
            if y not in chain:
                dfs(y)

    res = []
    chain = set()
    for _ in range(int(input())):
        a, b = list(map(int, input().split()))
        x = 0
        for color in list(edges.values()):
            chain.clear()
            dfs(a)
            if b in chain:
                x += 1
        res.append(str(x))
    print('\n'.join(res))

def __starting_point():
    main()

__starting_point()