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.

Difficulty: interview

Starter code:

Solutions:
n, m = list(map(int, input().split()))
mx = [[0x00] * n for i in range(n)]
used = None

def dfs(cur, trg, color):
    if cur == trg:
        return True
    if not used[cur]:
        used[cur] = True
        for i in range(n):
            if mx[cur][i] & color:
                if dfs(i, trg, color):
                    return True
    return False

for i in range(m):
    a, b, c = [int(s) - 1 for s in input().split()]
    mx[a][b] |= 1 << c
    mx[b][a] |= 1 << c

q = int(input())
for i in range(q):
    u, v = [int(s) - 1 for s in input().split()]
    result = 0
    for j in range(m):
        used = [False] * n
        if dfs(u, v, 1 << j):
            result += 1
    print(result)


from collections import deque

def BFS(graph,a,b):
    
    q = deque()
    q.append(a)
    visited = [ False for _ in range(len(graph))]
    
    while len(q):
        v = q.pop()

        if visited[v]:
            continue

        for x in graph[v]:
            if not visited[x]:
                q.append(x)

        visited[v] = True

    return visited[b]


n, m = map(int, input().split())
color = {}
for i in range(m):
    v1, v2, c = map(int, input().split())

    if c not in color:
        color[c] = [ [] for _ in range(n+1) ]

    color[c][v1].append(v2)
    color[c][v2].append(v1)
        
q = int(input())
for _ in range(q):
    a, b = map(int, input().split())

    ans = 0
    for i in color:
        if BFS(color[i], a, b):
            ans += 1
    print(ans)

from sys import setrecursionlimit as setrec
setrec(10010)

def dfs(i, s, cnt):
    if colored[i][s] > 0: return
    colored[i][s] = cnt
    for t in g[i][s]:
        dfs(i, t, cnt)

ver_n, edge_n = list(map(int, input().split()))
g = [[[] for _ in range(ver_n)] for _ in range(edge_n)]
for _ in range(edge_n):
    a, b, c = [int(x)-1 for x in input().split()]
    g[c][a].append(b)
    g[c][b].append(a)

colored = [[0] * ver_n for _ in range(edge_n)]
for i in range(edge_n):
    cnt = 1
    for j in range(ver_n):
        dfs(i, j, cnt)
        cnt += 1

q = int(input())
for i in range(q):
    cnt = 0
    u, v = [int(x)-1 for x in input().split()]
    for j in range(edge_n):
        if colored[j][u] == colored[j][v]:
            cnt += 1
    print(cnt)
    
    


n,m = input().split(' ')
l = []
for x in range(int(m)):
    l.append(list(range(int(n))))
for x in range(int(m)):
    p = input().split(' ')
    newl = l[int(p[2])-1]
    a,i = max(newl[int(p[0])-1],newl[int(p[1])-1]),min(newl[int(p[0])-1],newl[int(p[1])-1])
    for y in range(len(newl)):
        if newl[y] == a:
            newl[y] = i
    l[int(p[2])-1] = newl
q = int(input())
put = []
for x in range(q):
    out = 0
    a,b = input().split(' ')
    for n in l:
        if n[int(a)-1] == n[int(b)-1]:
            out += 1
    put.append(out)
for x in put:
    print(x)


n,m = list(map(int, input().split()))
l = []
for i in range(m):
    a,b,c = list(map(int, input().split()))
    if len(l) <= c-1:
        for i in range(c-len(l)):
            l.append([])
    p = l[c-1]
    m = []
    for i in range(len(p)):
        if a in p[i] or b in p[i]:
            m.append(i)
    new = [a,b]
    for i in range(len(m)):
        new = new + p[m[i]]
    for i in range(len(m)):
        p.pop(m[i]-i)
    p.append(new)
    l[c-1] = p
q = int(input())
for i in range(q):
    counter = 0
    u,v = list(map(int, input().split()))
    for j in range(len(l)):
        yes = 0
        for k in range(len(l[j])):
            if yes == 0 and u in l[j][k] and v in l[j][k]:
                yes = 1
                counter += 1
    print(counter)


def main():
    n, m = list(map(int, input().split()))
    edges = {_: {} for _ in range(1, m + 1)}
    for _ in range(m):
        a, b, c = list(map(int, input().split()))
        d = edges[c]
        l = d.get(a)
        if l:
            l.append(b)
        else:
            d[a] = [b]
        l = d.get(b)
        if l:
            l.append(a)
        else:
            d[b] = [a]

    def dfs(t):
        unused[t] = False
        for y in dcolor.get(t, ()):
            if unused[y]:
                dfs(y)

    res = []
    n += 1
    unused = [True] * n
    for _ in range(int(input())):
        a, b = list(map(int, input().split()))
        x = 0
        for dcolor in list(edges.values()):
            for j in range(n):
                unused[j] = True
            dfs(a)
            if not unused[b]:
                x += 1
        res.append(str(x))
    print('\n'.join(res))


def __starting_point():
    main()

__starting_point()

def iterative_bfs(graph, start, path=[]):
  '''iterative breadth first search from start'''
  q=[start]
  while q:
    v=q.pop(0)
    if not v in path:
      path=path+[v]
      q=q+graph[v]
  return path

dx = {}
nodes, edges = map(int, input().split(' '))
for c in range(edges+1):
    graph = {}
    for i in range(nodes):
      graph[i] = []
    dx[c] = graph


for i in range(edges):
  a, b, c = map(int, input().split(' '))
  dx[c][a-1].append(b-1)
  dx[c][b-1].append(a-1)

for _ in range(int(input())):
    a, b = map(int, input().split(' '))
    t = 0
    for i in dx:
        graph = dx[i]
        
        if b-1 in iterative_bfs(graph, a-1):
            t += 1
    print(t)

def dfs_paths(graph, start, goal, path=list()):
    if not path:
        path.append(start)
    if start == goal:
        yield path
    for vertex in graph[start] - set(path):
        yield from dfs_paths(graph, vertex, goal, path=path + [vertex])

n, m = map(int, input().split())
graph = {}

for _ in range(m):
    a, b, c = map(int, input().split())

    if c not in graph:
        graph[c] = {}

    if a not in graph[c]:
        graph[c][a] = set()

    if b not in graph[c]:
        graph[c][b] = set()

    graph[c][a].add(b)
    graph[c][b].add(a)

q = int(input())

for _ in range(q):
    u, v = map(int, input().split())
    count = 0

    for k in graph:
        if u not in graph[k] or v not in graph[k]:
            continue
        if len(list(dfs_paths(graph[k], u, v, []))) > 0:
            count += 1

    print(count)

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()

def DFS(start, color):
    nonlocal isUsed
    isUsed[start] = True
    for i in graph[start]:
        if not isUsed[i[0]] and i[1] == color:
            DFS(i[0], color)

n, m = tuple(map(int, input().split()))

graph = [[] for i in range(n)]

for i in range(m):
    a, b, c = tuple(map(int, input().split()))
    graph[a - 1].append((b - 1, c))
    graph[b - 1].append((a - 1, c))

q = int(input())
answers = [0] * q
for i in range(q):
    u, v = tuple(map(int, input().split()))
    for j in range(1, m + 1):
        isUsed = [False] * n
        DFS(u - 1, j)
        if isUsed[v - 1]:
            answers[i] += 1

print("\n".join(map(str, answers)))


# 505B.py
# Mr. Kitayuta's Colorful Graph

#First try
# n,m = map(int, raw_input().split())
# g = [[[] for _ in range(n+1)] for _ in range(m+1)]
# for i in xrange(m):
#     a,b,c = map(int, raw_input().split())
#     g[c][a].append(b)

# q = int(raw_input())

# for i in xrange(q):
#     u,v = map(int, raw_input().split())
#     out = 0
#     for j in xrange(1, len(g)):
#         u_found = v_found = False
#         for k in xrange(1, n+1):
#             if g[j][k]:
#                if k == u:
#                      u_found = True
#                elif k == v:
#                      v_found = True

#                for l in g[j][k]:
#                     if l == u:
#                         u_found = True
#                     elif l == v:
#                         v_found = True
#             if v_found == True and u_found == True:
#                 break
#         if v_found == True and u_found == True:
#             out += 1

#     print out
        
#Editorial
#DFS

#file = open("505Btest")
f = lambda: input()
#f = lambda: file.readline()
ml = lambda: list(map(int, f().split()))

n,m = ml()
g = [[ []for x in range(n+1)] for x in range(m+1)]

for i in range(m):
    a,b,c = ml()
    g[c][a].append(b)
    g[c][b].append(a)

q = int(f())

def dfs(c, start, end):
    nonlocal g, n
    discovered = [False] *(n+1)
    s = []
    s.append(start)
    while s:
        v = s.pop()
        if not discovered[v]:
            discovered[v] = True
            for i in g[c][v]:
                if i == end:
                    return True
                s.append(i)

    return False

for i in range(q):
    u,v = ml()
    count = 0
    for j in range(1, m+1):
        if g[j]:
            if dfs(j, u, v):
                count += 1
    print(count)
            


def dfs(u1,v1,c):
	ret = False
	used[u1-1] = True
	for i,edge in enumerate(e):
		if edge[2] != c:
			continue
		t = None
		if u1 == edge[0]:
			t = edge[1]
		elif u1 == edge[1]:
			t = edge[0]
		if t and not used[t-1]:
			if t == v1:
				return True
			else:
				ret |= dfs(t,v1,c)
	return ret



n,m = map(int,input().split())
e = [list(map(int,input().split())) for i in range(m)]
used = [False for i in range(n)]
q = int(input())
a = []
for i in range(q):
	u,v = map(int,input().split())
	ans = 0
	for c in range(1,m+1):
		if dfs(u,v,c):
			ans += 1
		used = [False for i in range(n)]
	a += [ans]
for i in a:
	print(i)

from collections import defaultdict, deque

def bfs(g,s,c):
    visited = set()
    q = deque([s])
    while len(q) > 0:
        v = q.pop()
        visited.add(v)
        for adj,adj_c in g[v]:
            if adj_c == c and adj not in visited and adj not in q:
                q.append(adj)
    return visited
    
def con_components(g,c):
    visited = set()
    components = []
    for s in g.keys():
        if s not in visited:
            nodes = bfs(g,s,c)
            components.append(nodes)
            visited |= nodes
    return components

def main():
    n,m = map(int, input().split())
    g = defaultdict(list)
    colors = set()
    for _ in range(m):
        a,b,c = map(int, input().split())
        g[a].append((b,c))
        g[b].append((a,c))
        colors.add(c)
    components = {c:con_components(g,c) for c in colors}
    
    q = int(input())
    for _ in range(q):
        u,v = map(int, input().split())
        ct = 0
        for c in colors:
            for comp in components[c]:
                if u in comp and v in comp:
                    ct += 1
        print(ct)
    

def __starting_point():
    main()   
__starting_point()

def dfs(p, f, gr, used):
	if p == f:
		return 1
	if used[p]:
		return 0
	used[p] = 1
	for v in gr[p]:
		if dfs(v, f, gr, used):
			return 1
	return 0

def check(gr, u, v):
	used = [0] * len(gr)
	return dfs(u, v, gr, used)

n, m = (int(x) for x in input().split())
cgr = [[[] for j in range(n)] for _ in range(m)]
for i in range(m):
	a, b, c = (int(x) for x in input().split())
	c -= 1
	a -= 1
	b -= 1
	cgr[c][a].append(b)
	cgr[c][b].append(a)
q = int(input())
for i in range(q):
	u, v = (int(x) for x in input().split())
	ans = 0
	for gr in cgr:
		ans += check(gr, u - 1, v - 1)
	print(ans)


# 505B
from collections import defaultdict

__author__ = 'artyom'

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

graphs = []


def root(components, x, l=0):
  return (x, l) if components[x] == x else root(components, components[x], l + 1)


def connected_components(edges):
  components = [i for i in range(n + 1)]
  for u, v in edges:
    ru, lu = root(components, u)
    rv, lv = root(components, v)
    if ru != rv:
      if lu < lv:
        components[ru] = rv
      else:
        components[rv] = ru
  return components


for c, edges in all_edges.items():
  graphs.append(connected_components(edges))


def count_in_same_component(u, v):
  count = 0
  for graph in graphs:
    if root(graph, u)[0] == root(graph, v)[0]:
      count += 1
  return count


ans = ''
for __ in range(int(input())):
  u, v = read()
  ans += str(count_in_same_component(u, v)) + '\n'
print(ans)

def solve():
    def dfs(c):
        if c == v:
            return True

        r = False

        for i in range(1, n+1):
            if g[w][c][i] and i not in p:
                p[i] = c
                r |= dfs(i)

        return r

    n, m = list(map(int, input().split()))
    g = [[[False for j in range(n+1)] for i in range(n+1)] for _ in range(m+1)]

    for _ in range(m):
        u, v, w = list(map(int, input().split()))
        g[w][u][v] = True
        g[w][v][u] = True

    for _ in range(int(input())):
        u, v = list(map(int, input().split()))
        res = 0

        for w in range(1, m+1):
            p = dict()
            p[u] = -1
            res += dfs(u)

        print(res)

solve()


def get_connected_matrix(adjacency_matrix):
    n = len(adjacency_matrix)
    non_visited_vertices = set(i for i in range(n))
    cluster_numbers = [0] * n
    cluster_number = 1

    def traverse(u):
        non_visited_vertices.remove(u)
        cluster_numbers[u] = cluster_number
        for v in range(n):
            if v in non_visited_vertices:
                if adjacency_matrix[u][v]:
                    traverse(v)

    while non_visited_vertices:
        vertex = non_visited_vertices.pop()
        non_visited_vertices.add(vertex)
        traverse(vertex)
        cluster_number += 1

    connected_matrix = [[False] * n for _ in range(n)]

    for u in range(n):
        for v in range(n):
            if u == v:
                continue
            connected_matrix[u][v] = connected_matrix[v][u] = (cluster_numbers[u] == cluster_numbers[v])

    return connected_matrix


def main():
    n, m = [int(t) for t in input().split()]

    matrices = [[[False] * n for _ in range(n)] for _ in range(m)]

    for _ in range(m):
        a, b, c = [int(t) - 1 for t in input().split()]
        matrices[c][a][b] = True
        matrices[c][b][a] = True

    connected_matrices = [get_connected_matrix(matrix) for matrix in matrices]

    q = int(input())
    for _ in range(q):
        u, v = [int(t) - 1 for t in input().split()]
        total_connection = sum(1 for connected_matrix in connected_matrices if connected_matrix[u][v])
        print(total_connection)


def __starting_point():
    main()

__starting_point()

def dfs(x,c):
    vis[x] = 1
    for i in adj[c][x]:
        if not vis[i]:
            dfs(i,c)

def check(u,v,c):
    for i in range(1,n+1):
        vis[i] = False
    dfs(u,c)
    return vis[v]

n,m = map(int,input().split())

adj = []
for i in range(m+1):
    adj.append([])
    for j in range(n+1):
        adj[i].append([])
vis = [False]*(n+1)

for i in range(m):
    a,b,c = map(int,input().split())
    adj[c][a].append(b)
    adj[c][b].append(a)

q = int(input())
for i in range(q):
    u,v = map(int,input().split())
    ans = 0;
    for c in range(1,m+1):
        if check(u,v,c):
            ans+=1
    print(ans)

def dfs(place,target):
    vis[place]=True
    if target==place:total[0]+=1;return()
    anyAdj=0
    for i in j[place]:
        if not vis[i]:anyAdj=1;dfs(i,target)
    if anyAdj==0:return()

v,e=list(map(int,input().split()))
edges=[]
for i in range(e):edges.append(list(map(int,input().split())))
colors=[]
for i in edges:colors.append(i[2])
colors=list(set(colors))
colorAdjs=[]
for i in colors:
    colorAdjs.append([[] for w in range(v)])
    for j in edges:
        if j[2]==i:
            colorAdjs[-1][j[0]-1].append(j[1]-1)
            colorAdjs[-1][j[1]-1].append(j[0]-1)
q=int(input())
for i in range(q):
    total=[0]
    a,b=list(map(int,input().split()))
    a-=1;b-=1
    for j in colorAdjs:
        vis=[False]*v
        dfs(a,b)
    print(total[0])


n,m = [int(x) for x in input().split()]
edge = {}
for i in range (1,n+1):
	edge[i] = {}
	for j in range (1,m+1):
		edge[i][j] = []
for i in range (m):
	a,b,c = [int(x) for x in input().split()]
	edge[a][c].append(b)
	edge[b][c].append(a)
q = int(input())
for i in range (q):
	u,v = [int(x) for x in input().split()]
	count = 0
	for key in edge[u]:
		level = {u:0}
		frontier = [u]
		found = False
		while frontier and not found:
			next = []
			for uu in frontier:
				for vv in edge[uu][key]:
					if not(vv in level):
						if vv == v:
							found = True
						level[vv] = 0
						next.append(vv)
			frontier = next
		if(found):
			count += 1
	print (count)

from collections import defaultdict,deque,Counter,OrderedDict
def main():
    N = 105
    n,m = map(int,input().split())
    par = [ [j for j in range(N)] for i in range(N)]

    def find(a,c):
        if par[c][a] == a: return a
        par[c][a] = find(par[c][a],c)
        return par[c][a]

    def merge(a,b,c):
        a = find(a,c)
        b = find(b,c)
        par[c][b] = a

    for i in range(m):
        a,b,c = map(int,input().split())
        a,b = a-1,b-1
        merge(a,b,c)

    q = int(input())
    for i in range(q):
        a,b = map(int,input().split())
        a,b,ans = a-1,b-1,0
        for i in range(N):
            if find(a,i) == find(b,i):
                ans +=1
        print(ans)

def __starting_point():
    main()
__starting_point()

n, m = list(map(int,input().split()))
p = [ [ i for i in range(n) ] for j in range(m)]
def f(ci,xi):
  if xi==p[ci][xi]: return xi
  p[ci][xi] = f(ci,p[ci][xi])
  return p[ci][xi]
def uni(ci,xi,yi):
  p[ci][f(ci,xi)]=f(ci,yi)
for i in range(m):
  a, b, c = list(map(int,input().split()))
  uni(c-1,a-1,b-1)
for i in range(int(input())):
  a, b = list(map(int,input().split()))
  print(sum(1 if f(i,a-1) == f(i,b-1) else 0 for i in range(m)))


def build_graph():
    line1 = input().strip().split()
    n = int(line1[0])
    m = int(line1[1])
    graph = {}
    for _ in range(m):
        line = input().strip().split()
        u = int(line[0])
        v = int(line[1])
        c = int(line[2])
        if c not in graph:
            graph[c] = {j: [] for j in range(1, n+1)}
        graph[c][u].append(v)
        graph[c][v].append(u)
    return graph

def no_of_paths(u, v, graph):
    x = 0
    for c in graph:
        parent = {}
        parent = dfs_visit(v, graph[c], parent)
        if u in parent:
            x += 1
    return x

def dfs_visit(i, adj_list, parent):
    for j in adj_list[i]:
        if j not in parent:
            parent[j] = i
            dfs_visit(j, adj_list, parent)
    return parent


def __starting_point():
    graph = build_graph()
    for _ in range(int(input())):
        line = input().strip().split()
        print(no_of_paths(int(line[0]), int(line[1]), graph))
__starting_point()

def build_graph():
    line1 = input().strip().split()
    n = int(line1[0])
    m = int(line1[1])
    graph = {}
    for _ in range(m):
        line = input().strip().split()
        u = int(line[0])
        v = int(line[1])
        c = int(line[2])
        if c not in graph:
            graph[c] = {j: [] for j in range(1, n+1)}
        graph[c][u].append(v)
        graph[c][v].append(u)
    return graph

parent_history = {}

def no_of_paths(u, v, graph):
    x = 0
    for c in graph:
        if c in parent_history and v in parent_history[c]:
            parent = parent_history[c]
        else:
            parent = {}
            parent = dfs_visit(v, graph[c], parent)
            parent_history[c] = parent
        if u in parent:
            x += 1
    return x

def dfs_visit(i, adj_list, parent):
    for j in adj_list[i]:
        if j not in parent:
            parent[j] = i
            dfs_visit(j, adj_list, parent)
    return parent


def __starting_point():
    graph = build_graph()
    for _ in range(int(input())):
        line = input().strip().split()
        print(no_of_paths(int(line[0]), int(line[1]), graph))
__starting_point()

def build_graph():
    line1 = input().strip().split()
    n = int(line1[0])
    m = int(line1[1])
    graph = {}
    for _ in range(m):
        line = input().strip().split()
        u = int(line[0])
        v = int(line[1])
        c = int(line[2])
        if c not in graph:
            graph[c] = {j: [] for j in range(1, n+1)}
        graph[c][u].append(v)
        graph[c][v].append(u)
    return graph

parent_history = {}

def no_of_paths(u, v, graph):
    x = 0
    for c in graph:
        if c in parent_history:
            if v in parent_history[c]:
                parent = parent_history[c]
            else:
                parent = {}
                parent = dfs_visit(v, graph[c], parent)
                if len(parent_history[c]) < len(parent):
                    parent_history[c] = parent
        else:
            parent = {}
            parent = dfs_visit(v, graph[c], parent)
            parent_history[c] = parent
        if u in parent:
            x += 1
    return x

def dfs_visit(i, adj_list, parent):
    for j in adj_list[i]:
        if j not in parent:
            parent[j] = i
            dfs_visit(j, adj_list, parent)
    return parent


def __starting_point():
    graph = build_graph()
    for _ in range(int(input())):
        line = input().strip().split()
        print(no_of_paths(int(line[0]), int(line[1]), graph))
__starting_point()