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: MEDIUM
Tags: Spanning trees

Graph algorithms

Graph traversal

Dynamic programming
Skill types: Dynamic programming

Starter code:

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


import sys
inf = float('inf')
mod = 1000000007

def get_array():
	return list(map(int, sys.stdin.readline().split()))

def get_ints():
	return map(int, sys.stdin.readline().split())

def input():
	return sys.stdin.readline()
N = 105
graph = [[] for _ in range(N)]
component = [0] * N
visited = [False] * N

def explore(node):
	global cnt
	visited[node] = True
	component[node] = cnt
	for (neighbour, color) in graph[node]:
		if visited[neighbour] == False:
			explore(neighbour)

def dfs(n):
	global cnt
	cnt = 0
	for i in range(1, n + 1):
		if visited[i] == False:
			cnt += 1
			explore(i)

def explore_o(node, c):
	global ans, s
	visited[node] = True
	for (neighbour, color) in graph[node]:
		if visited[neighbour] == False and color == c:
			if neighbour == v:
				s.add(color)
			explore_o(neighbour, c)

def dfs_o(u):
	global visited, ans, flag, s
	ans = 0
	s = set()
	for (neighbour, color) in graph[u]:
		visited = [False] * N
		visited[u] = True
		flag = 0
		if neighbour == v:
			s.add(color)
			continue
		explore_o(neighbour, color)
	return len(s)

def main():
	global n, m
	(n, m) = get_ints()
	for _ in range(m):
		(u, x, c) = get_ints()
		graph[u].append((x, c))
		graph[x].append((u, c))
	dfs(n)
	global v
	for tc in range(int(input())):
		(u, v) = get_ints()
		if component[u] != component[v]:
			print(0)
			continue
		print(dfs_o(u))
main()


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)


(v, e) = map(int, input().split())
graphs = [[set([i]) for i in range(1, v + 1)] for _ in range(101)]

def getSet(sets, vertex):
	for s in sets:
		if vertex in s:
			return s
for _ in range(e):
	(a, b, c) = map(int, input().split())
	sa = getSet(graphs[c], a)
	sb = getSet(graphs[c], b)
	if sa.isdisjoint(sb):
		sa |= sb
		graphs[c].remove(sb)
q = int(input())
for _ in range(q):
	(a, b) = map(int, input().split())
	c = 0
	for graph in graphs:
		sa = getSet(graph, a)
		sb = getSet(graph, b)
		if not sa.isdisjoint(sb):
			c += 1
	print(c)


from collections import defaultdict

def main():
	(n, m) = map(int, input().split())
	edges = defaultdict(lambda : defaultdict(list))
	for _ in range(m):
		(a, b, c) = 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) = map(int, input().split())
		x = 0
		for color in edges.values():
			chain.clear()
			dfs(a)
			if b in chain:
				x += 1
		res.append(str(x))
	print('\n'.join(res))
main()


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


(n, m) = map(int, input().split())
INF = 10 ** 18
d = [[[INF] * n for j in range(n)] for i in range(m)]
edges = [[[] for i in range(n)] for i in range(m)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	c -= 1
	edges[c][a].append(b)
	edges[c][b].append(a)
	d[c][a][b] = d[c][b][a] = 1
for color in range(m):
	for s in range(n):
		q = [s]
		visited = [False] * n
		visited[s] = True
		while q:
			node = q.pop(0)
			visited[node] = True
			for to in edges[color][node]:
				if visited[to]:
					continue
				d[color][s][to] = d[color][to][s] = 1
				q.append(to)
Q = int(input())
for _ in range(Q):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	ans = 0
	for color in range(m):
		if d[color][u][v] < INF:
			ans += 1
	print(ans)


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


from collections import defaultdict

def connectedComponents(root, visited, graph, c, comp):
	visited[root] = 1
	comp[root] = c
	for i in graph[root]:
		if visited[i] == 0:
			connectedComponents(i, visited, graph, c, comp)
	return
(n, m) = map(int, input().split())
graphs = [defaultdict(list) for i in range(m + 1)]
vert = defaultdict(set)
for _ in range(m):
	(u, v, c) = map(int, input().split())
	graphs[c][u].append(v)
	graphs[c][v].append(u)
	vert[c].add(v)
	vert[c].add(u)
components = [[0 for i in range(n + 1)] for i in range(m + 1)]
for i in range(1, m + 1):
	c = 0
	visited = [0 for i in range(n + 1)]
	for r in graphs[i].keys():
		if visited[r] == 0:
			c += 1
			connectedComponents(r, visited, graphs[i], c, components[i])
q = int(input())
for i in range(q):
	(u, v) = map(int, input().split())
	ans = 0
	for j in range(1, m + 1):
		if components[j][u] == components[j][v] and components[j][u] != 0:
			ans += 1
	print(ans)


class Node:

	def __init__(self, n):
		self.n = n
		self.neighs = {}

	def dfs_color(self, f, t, nodes, visited):
		visited.add(self.n)
		connected = set()
		for (neigh, colors_to_neigh) in self.neighs.items():
			if neigh == f or neigh in visited:
				continue
			colors = colors_to_neigh if neigh == t else nodes[neigh].dfs_color(self.n, t, nodes, visited)
			connected.update(colors.intersection(colors_to_neigh))
		visited.remove(self.n)
		return connected

	def dfs_colored_path(self, cc, nodes, visited):
		visited.add(self.n)
		for (neigh, colors_to_neigh) in self.neighs.items():
			if neigh in visited or cc not in colors_to_neigh:
				continue
			nodes[neigh].dfs_colored_path(cc, nodes, visited)
		return visited

	def search_with_color(self, t, nodes):
		colors_to_explore = set()
		colors = set()
		for (neigh, colors_to_neigh) in self.neighs.items():
			colors_to_explore.update(colors_to_neigh)
		for color in colors_to_explore:
			cities = self.dfs_colored_path(color, nodes, set())
			if t in cities:
				colors.add(color)
		return len(colors)
(n, m) = [int(n) for n in input().split()]
edges = []
while m:
	edge = [int(n) for n in input().split()]
	edges.append(edge)
	m -= 1
nodes = [Node(i) for i in range(n + 1)]
for (f, t, c) in edges:
	if t not in nodes[f].neighs:
		nodes[f].neighs[t] = set()
	nodes[f].neighs[t].add(c)
	(f, t) = (t, f)
	if t not in nodes[f].neighs:
		nodes[f].neighs[t] = set()
	nodes[f].neighs[t].add(c)
qs = int(input())
for q in range(qs):
	(f, t) = [int(n) for n in input().split()]
	print(nodes[f].search_with_color(t, nodes))


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


from collections import defaultdict
(n, m) = map(int, input().split())
d = [defaultdict(list) for i in range(1 + m)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	d[c][a].append(b)
	d[c][b].append(a)
q = int(input())
for _ in range(q):
	(u, v) = map(int, input().split())
	ct = 0
	for adj in d:
		vst = [0] * (n + 1)
		q = [u]
		while q:
			e = q.pop()
			if e == v:
				ct += 1
				break
			else:
				vst[e] = 1
				for j in adj[e]:
					if not vst[j]:
						q.append(j)
	print(ct)


class Solution:

	def __init__(self, n, m, edges):
		self.n = n
		self.m = m
		self.edges = [[[] for _ in range(m + 1)] for _ in range(n + 1)]
		for (_from, _to, _color) in edges:
			self.edges[_from][_color].append(_to)
			self.edges[_to][_color].append(_from)
		self.id = 0

	def initialize(self):
		self.discovered = [[0] * (self.n + 1) for i in range(self.m + 1)]

	def bfs(self, x0, color):
		self.id += 1
		stack = [x0]
		while stack:
			n = stack.pop()
			if not self.discovered[color][n]:
				self.discovered[color][n] = self.id
				for neigh in self.edges[n][color]:
					stack.append(neigh)

def solve(graph, colors, u, v):
	counter = 0
	for color in colors:
		if not graph.discovered[color][u] and (not graph.discovered[color][v]):
			graph.bfs(u, color)
		if graph.discovered[color][u] == graph.discovered[color][v]:
			counter += 1
	return counter

def main():
	(n, m) = map(int, input().split())
	edges = []
	colors = set()
	for _ in range(m):
		(a, b, c) = map(int, input().split())
		colors.add(c)
		edges.append((a, b, c))
	graph = Solution(n, m, edges)
	graph.initialize()
	q = int(input())
	for _ in range(q):
		(u, v) = map(int, input().split())
		print(solve(graph, colors, u, v))
main()


import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

def Sn():
	return sys.stdin.readline().strip()

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def dfs(gp, st, end, v, x):
	q = deque([st])
	while q:
		node = q.pop()
		v[node] = 1
		for i in gp[node]:
			if not v[i[0]] and i[1] == x:
				q.appendleft(i[0])
	return v[end]

def main():
	try:
		(n, m) = In()
		gp = defaultdict(list)
		d = defaultdict(set)
		for x in range(m):
			(a, b, c) = In()
			gp[a].append((b, c))
			gp[b].append((a, c))
			d[a].add(c)
			d[b].add(c)
		for i in range(I()):
			(st, end) = In()
			cnt = 0
			for x in d[st]:
				v = [0] * (n + 1)
				if dfs(gp, st, end, v, x):
					cnt += 1
			print(cnt)
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	main()


(n, m) = map(int, input().split())
(e, g) = ({}, {x: set() for x in range(1, n + 1)})
for i in range(m):
	(a, b, c) = map(int, input().split())
	e[a, b] = e[b, a] = e.get((a, b), set()) | {c}
	g[a].add(b)
	g[b].add(a)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	ans = 0
	for color in range(1, m + 1):
		vis = [0] * (n + 1)
		q = [a]
		while q:
			v = q.pop()
			if v == b:
				ans += 1
				break
			vis[v] = 1
			for i in g[v]:
				if not vis[i] and color in e[v, i]:
					q.append(i)
	print(ans)


f = lambda : input()
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)


from collections import defaultdict

def color_path(graph, n, m, u, v, c):
	stack = [u]
	visited = [False] * (n + 1)
	while len(stack) > 0:
		x = stack.pop()
		visited[x] = True
		for (y, cy) in graph[x]:
			if not visited[y] and cy == c:
				stack.append(y)
		if x == v:
			return 1
	return 0
(n, m) = map(int, input().split())
graph = defaultdict(list)
colors = set()
for _ in range(m):
	(a, b, c) = map(int, input().split())
	graph[a].append((b, c))
	graph[b].append((a, c))
	colors.add(c)
for _ in range(int(input())):
	(u, v) = map(int, input().split())
	total = 0
	for c in colors:
		total += color_path(graph, n, m, u, v, c)
	print(total)


def iterative_bfs(graph, start, path=[]):
	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(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])


import sys

class Dsu:

	def __init__(self):
		self.__sz = {}
		self.__parent = {}

	def parent(self, a):
		if a not in self.__parent or a == self.__parent[a]:
			return a
		else:
			self.__parent[a] = self.parent(self.__parent[a])
			return self.__parent[a]

	def connect(self, a, b):
		p1 = self.parent(a)
		p2 = self.parent(b)
		if p2 != p1:
			if p1 not in self.__sz:
				self.__sz[p1] = 1
			if p2 not in self.__sz:
				self.__sz[p2] = 1
			sz1 = self.__sz[p1]
			sz2 = self.__sz[p2]
			if sz1 >= sz2:
				self.__parent[p2] = p1
				self.__sz[p1] += self.__sz[p2]
			else:
				self.__parent[p1] = p2
				self.__sz[p2] += self.__sz[p1]

	def connected(self, a, b):
		return self.parent(a) == self.parent(b)
(n, m) = [int(i) for i in input().split(' ')]
g = {}
choice = {}
for j in range(m):
	(a, b, c) = [int(i) for i in input().split(' ')]
	if c not in g:
		g[c] = Dsu()
	g[c].connect(a, b)
	if a not in choice:
		choice[a] = []
	if b not in choice:
		choice[b] = []
	choice[a].append(c)
	choice[b].append(c)
q = int(input())
mem = {}
for j in range(q):
	(a, b) = [int(i) for i in input().split(' ')]
	if a not in choice or b not in choice:
		print('0')
		continue
	if a in mem and type(mem[a]) == dict and (b in mem[a]):
		s = mem[a][b]
	else:
		options = set.intersection(set(choice[a]), set(choice[b]))
		s = 0
		for c in options:
			s += int(g[c].connected(a, b))
		if a not in mem:
			mem[a] = {}
		if b not in mem:
			mem[b] = {}
		mem[a][b] = mem[b][a] = s
	print(s)


import copy
info = list(map(int, input().split()))
n = info[0]
m = info[1]
mat = [[[] for i in range(n)] for j in range(n)]
for i in range(m):
	info = list(map(int, input().split()))
	a = info[0]
	b = info[1]
	c = info[2]
	mat[a - 1][b - 1].append(c)
	mat[b - 1][a - 1].append(c)
q = int(input())
for i in range(q):
	info = list(map(int, input().split()))
	u = info[0] - 1
	v = info[1] - 1
	l = []
	for j in range(n):
		p = len(mat[u][j])
		for h in range(p):
			l.append(mat[u][j][h])
	l = list(set(l))
	p = len(l)
	c = 0
	for j in range(p):
		co = l[j]
		lis = [False] * n
		stk = []
		curr = u
		while True:
			found = False
			for h in range(n):
				if not lis[h] and co in mat[curr][h]:
					stk.append(curr)
					lis[h] = True
					curr = h
					found = True
					break
			if curr == v:
				c += 1
				break
			if not found:
				if len(stk) == 0:
					break
				curr = stk[-1]
				stk.pop(-1)
	print(c)


(n, m) = map(int, input().split())
d = {}
adj = [[] for i in range(1 + n)]
d = [[[-1 for k in range(101)] for j in range(1 + n)] for i in range(n + 1)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)
	d[a][b][c] = 1
	d[b][a][c] = 1
visited = [0] * (n + 1)

def dfs(u, target, c):
	if u == target:
		return True
	visited[u] = 1
	for v in adj[u]:
		if visited[v] == 0 and d[u][v][c] == 1:
			if dfs(v, target, c):
				return True
	return False
for _ in range(int(input())):
	(u, v) = map(int, input().split())
	res = 0
	for i in range(1, 101):
		visited = [0] * (n + 1)
		if dfs(u, v, i):
			res += 1
	print(res)


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]
				if u in parent:
					x += 1
			elif u in parent_history[c]:
				parent = parent_history[c]
				if v in parent:
					x += 1
			else:
				parent = {}
				parent = dfs_visit(v, graph[c], parent)
				if len(parent_history[c]) < len(parent):
					parent_history[c] = parent
				if u in parent:
					x += 1
		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
graph = build_graph()
for _ in range(int(input())):
	line = input().strip().split()
	print(no_of_paths(int(line[0]), int(line[1]), graph))


def gerarGrafo(cor):
	adjancencias = {}
	for aresta in arestas:
		if aresta[2] == cor:
			if adjancencias.get(aresta[0]) == None:
				adjancencias[aresta[0]] = []
			if adjancencias.get(aresta[1]) == None:
				adjancencias[aresta[1]] = []
			adjancencias[aresta[0]].append(aresta[1])
			adjancencias[aresta[1]].append(aresta[0])
	return adjancencias

def dfs(u, w, adjacencias):
	pilha = [u]
	visitados = {u: 1}
	existeCaminhoUV = False
	if adjacencias.get(u) == None or adjacencias.get(w) == None:
		return existeCaminhoUV
	while len(pilha) > 0:
		vertice = pilha.pop()
		for v in adjacencias[vertice]:
			if visitados.get(v) == None:
				visitados[v] = 1
				pilha.append(v)
	if visitados.get(w) != None:
		existeCaminhoUV = True
	return existeCaminhoUV
entrada = input().split()
n = int(entrada[0])
m = int(entrada[1])
cores = set()
arestas = []
i = 0
while i < m:
	aresta = input().split()
	cores.add(aresta[2])
	arestas.append(aresta)
	i += 1
q = int(input())
paresVertices = []
i = 0
while i < q:
	paresVertices.append(input().split())
	i += 1
res = [0] * q
for cor in cores:
	grafo = gerarGrafo(cor)
	i = 0
	for par in paresVertices:
		if dfs(par[0], par[1], grafo):
			res[i] += 1
		i += 1
for e in res:
	print(e)


import sys
import math
from collections import defaultdict
import itertools
MAXNUM = math.inf
MINNUM = -1 * math.inf

def getInt():
	return int(sys.stdin.readline().rstrip())

def getInts():
	return map(int, sys.stdin.readline().rstrip().split(' '))

def getString():
	return sys.stdin.readline().rstrip()

def printOutput(ans):
	sys.stdout.write()
	pass

def dfs(a, b, edgeList):
	total = 0
	cLook = set()
	for (nxt, col) in edgeList[a]:
		if col not in cLook:
			explored = dict()
			explored[a] = True
			explored[nxt] = True
			if dfs_helper(nxt, b, edgeList, col, explored) == 1:
				cLook.add(col)
				total += 1
	return total

def dfs_helper(cur, goal, edgeList, color, explored):
	if cur == goal:
		return 1
	for (nxt, col) in edgeList[cur]:
		if col == color and nxt not in explored:
			explored[nxt] = True
			if dfs_helper(nxt, goal, edgeList, color, explored) == 1:
				return 1
			del explored[nxt]
	return 0

def solve(n, m, edgeList, queries):
	for (a, b) in queries:
		print(dfs(a, b, edgeList))

def readinput():
	(n, m) = getInts()
	edgeList = defaultdict(list)
	for _ in range(m):
		(a, b, c) = getInts()
		edgeList[a].append((b, c))
		edgeList[b].append((a, c))
	queries = []
	q = getInt()
	for _ in range(q):
		queries.append(tuple(getInts()))
	solve(n, m, edgeList, queries)
readinput()


from collections import defaultdict

def dfs(node, b, graph, colour, vis):
	if node == b:
		return True
	vis[node] = True
	for i in graph[node]:
		if not vis[i[0]]:
			if i[1] == colour:
				if dfs(i[0], b, graph, i[1], vis):
					return True
	return False
(n, m) = map(int, input().split())
graph = defaultdict(list)
for i in range(m):
	(a, b, c) = map(int, input().split())
	graph[a].append([b, c])
	graph[b].append([a, c])
q = int(input())
visited = [False] * (n + 1)
for i in range(q):
	(a, b) = map(int, input().split())
	ans = 0
	for i in range(101):
		vis = visited[:]
		if dfs(a, b, graph, i, vis):
			ans += 1
	print(ans)


class Graph(object):

	def __init__(self, num_nodes):
		self.num_nodes = num_nodes
		self.adj_list = {}

	def __add_directional_edge(self, a, b, c):
		if a in self.adj_list:
			if b in self.adj_list[a]:
				if c not in self.adj_list[a][b]:
					self.adj_list[a][b].append(c)
			else:
				self.adj_list[a][b] = []
				self.adj_list[a][b].append(c)
		else:
			self.adj_list[a] = {}
			self.adj_list[a][b] = []
			self.adj_list[a][b].append(c)

	def add_edge(self, a, b, c):
		self.__add_directional_edge(a, b, c)
		self.__add_directional_edge(b, a, c)

	def print_graph(self):
		print(self.adj_list)

def tc():
	g = readGraph()
	for k in range(1, g.num_nodes + 1):
		for i in range(1, g.num_nodes + 1):
			for j in range(1, g.num_nodes + 1):
				l1 = g.adj_list.get(i, {}).get(k, [])
				l2 = g.adj_list.get(k, {}).get(j, [])
				for color in l1:
					if color in l2:
						g.add_edge(i, j, color)
	return g

def readGraph():
	(n, m) = map(int, input().split())
	g = Graph(n)
	for _ in range(m):
		(a, b, c) = map(int, input().split())
		g.add_edge(a, b, c)
	return g

def read_query():
	q = int(input())
	q_list = []
	for _ in range(q):
		(u, v) = map(int, input().split())
		q_list.append((u, v))
	return q_list

def solve_query(g, q_list):
	for (u, v) in q_list:
		if u in g.adj_list:
			if v in g.adj_list[u]:
				print(len(g.adj_list[u][v]))
			else:
				print('0')
		else:
			print('0')

def main():
	g = tc()
	q_list = read_query()
	solve_query(g, q_list)
main()


(n, m) = list(map(int, input().split(' ')))
Meow = []
for i in range(101):
	Meow.append([])
	for j in range(n + 1):
		Meow[i].append(j)

def root(N, C):
	while Meow[C][N] != N:
		Meow[C][N] = Meow[C][Meow[C][N]]
		N = Meow[C][N]
	return N

def union(A, B, C):
	p = root(A, C)
	q = root(B, C)
	Meow[C][p] = q
for i in range(m):
	(a, b, c) = list(map(int, input().split(' ')))
	union(a, b, c)
q = int(input())
for i in range(q):
	(a, b) = list(map(int, input().split(' ')))
	cnt = 0
	for i in range(1, 101):
		if root(a, i) == root(b, i):
			cnt += 1
	print(cnt)


(n, m) = map(int, input().split())
mx = [[0] * 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) = map(lambda s: int(s) - 1, input().split())
	mx[a][b] |= 1 << c
	mx[b][a] |= 1 << c
q = int(input())
for i in range(q):
	(u, v) = map(lambda s: int(s) - 1, 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, defaultdict

def dfs(node, c):
	for i in g[node]:
		if not visited[i[0]] and i[1] == c:
			visited[i[0]] = True
			dfs(i[0], i[1])
(n, m) = map(int, input().split())
g = defaultdict(list)
cols = deque()
for i in range(m):
	(u, v, c) = map(int, input().split())
	g[u].append([v, c])
	g[v].append([u, c])
	cols.append(c)
q = int(input())
ans = deque()
for i in range(q):
	(x, y) = map(int, input().split())
	cnt = 0
	for j in range(1, m + 1):
		visited = [False] * (n + 1)
		dfs(x, j)
		if visited[y] == True:
			cnt += 1
	ans.append(cnt)
for i in ans:
	print(i)


from collections import defaultdict
from sys import stdin, stdout
par = defaultdict(list)

def build(n):
	global par, size
	for c in range(101):
		par[c] = []
		for i in range(n):
			par[c].append(i)
	return par

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

def union(a, b, c):
	global par, scc, size
	p = find(c, a)
	q = find(c, b)
	if p == q:
		return
	par[c][q] = par[c][p]

def main():
	(n, m) = map(int, stdin.readline().strip().split(' '))
	par = build(n)
	max_c = 0
	for i in range(m):
		(a, b, c) = map(lambda i: int(i) - 1, stdin.readline().strip().split(' '))
		union(a, b, c)
		max_c = max(max_c, c)
	q = int(stdin.readline().strip())
	for i in range(q):
		(a, b) = map(lambda i: int(i) - 1, stdin.readline().strip().split(' '))
		count = 0
		for c in range(max_c + 1):
			p = find(c, a)
			q = find(c, b)
			if p == q:
				count += 1
		stdout.write('{}\n'.format(count))
main()


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)


from sys import stdin
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())

def dfs(x, y, z):
	if x == y:
		return True
	g[x] = 1
	for p in cl[x]:
		if p[1] == z and g[p[0]] == 0 and dfs(p[0], y, z):
			return True
	return False
(n, m) = R()
cl = [[] for i in range(n)]
for i in range(m):
	(a, b, c) = R()
	cl[a - 1].append([b - 1, c - 1])
	cl[b - 1].append([a - 1, c - 1])
q = I()
s = [0] * q
for i in range(q):
	(u, v) = R()
	for j in range(100):
		g = [0] * n
		if dfs(u - 1, v - 1, j):
			s[i] += 1
for i in s:
	print(i)


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


from collections import defaultdict

class DisjSet:

	def __init__(self, n):
		self.rank = [1] * n
		self.parent = [i for i in range(n)]

	def find(self, x):
		if self.parent[x] != x:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def Union(self, x, y):
		xset = self.find(x)
		yset = self.find(y)
		if xset == yset:
			return
		if self.rank[xset] < self.rank[yset]:
			self.parent[xset] = yset
		elif self.rank[xset] > self.rank[yset]:
			self.parent[yset] = xset
		else:
			self.parent[yset] = xset
			self.rank[xset] = self.rank[xset] + 1
L = []
(n, m) = map(int, input().split())
edges = []
for k in range(m):
	(a, b, c) = map(int, input().split())
	edges.append([a, b, c])
q = int(input())
queries = []
for l in range(q):
	(x, y) = map(int, input().split())
	queries.append([x, y])
count = [0 for i in range(q)]
for i in range(1, 101):
	g = DisjSet(101)
	for [u, v, c] in edges:
		if c == i:
			g.Union(u, v)
	for z in range(q):
		if g.find(queries[z][0]) == g.find(queries[z][1]):
			count[z] += 1
for m in range(q):
	print(count[m])


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
(n, m) = mp()
d = defaultdict(list)
for _ in range(m):
	(a, b, c) = mp()
	d[a, c].append(b)
	d[b, c].append(a)
Q = inp()
v = [0 for i in range(n + 1)]
for i in range(Q):
	(x, y) = mp()
	ans = 0
	for j in range(1, m + 1):
		q = deque()
		q.append((x, j))
		copy_visited = list(v)
		copy_visited[x] = 1
		while q:
			(a, b) = q.popleft()
			if a == y:
				ans += 1
				break
			for k in d[a, b]:
				if not copy_visited[k]:
					copy_visited[k] = 1
					q.append((k, b))
	print(ans)


scanf = lambda : map(int, input().split())
(n, m) = scanf()
f = [list(range(n + 1)) for _ in range(m + 2)]

def fd(a, c):
	if f[c][a] != a:
		f[c][a] = fd(f[c][a], c)
	return f[c][a]

def un(a, b, c):
	(ra, rb) = (fd(a, c), fd(b, c))
	if ra == rb:
		return
	f[c][ra] = rb

def swap(a, b):
	tmp = a
	a = b
	b = tmp
for (a, b, c) in [map(int, input().split()) for _ in range(m)]:
	un(a, b, c)
q = int(input())
for (x, y) in [map(int, input().split()) for _ in range(q)]:
	print(sum((1 for i in range(1, m + 1) if fd(x, i) == fd(y, i))))


class DisjointSet:

	def __init__(self, n):
		self.num_sets = n
		self.parents = list(range(n))
		self.ranks = [0] * n
		self.sizes = [1] * n

	def __str__(self):
		return '%s' % self.parents

	def __repr__(self):
		return '%s' % self.parents

	def find(self, j):
		while self.parents[j] != j:
			j = self.parents[j]
		return j

	def union(self, i, j):
		i = self.find(i)
		j = self.find(j)
		if i == j:
			return False
		rd = self.ranks[i] - self.ranks[j]
		if rd == 0:
			self.ranks[i] += 1
		elif rd < 0:
			(i, j) = (j, i)
		self.parents[j] = i
		self.sizes[i] += self.sizes[j]
		self.sizes[j] = 0
		self.num_sets -= 1
		return True

def main():
	(n, m) = list(map(int, input().split()))
	el = [list(map(int, input().split())) for _ in range(m)]
	q = int(input())
	vl = [list(map(int, input().split())) for _ in range(q)]
	dl = [DisjointSet(n) for _ in range(m)]
	for (a, b, c) in el:
		dl[c - 1].union(a - 1, b - 1)
	[print(sum([d.find(u - 1) == d.find(v - 1) for d in dl])) for (u, v) in vl]
main()


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


class Union:

	def __init__(self, size):
		self.ancestor = [i for i in range(size + 1)]

	def find(self, node):
		if self.ancestor[node] == node:
			return node
		self.ancestor[node] = self.find(self.ancestor[node])
		return self.ancestor[node]

	def merge(self, a, b):
		(a, b) = (self.find(a), self.find(b))
		self.ancestor[a] = b
(n, m) = map(int, input().split())
unions = [Union(n) for _ in range(m + 1)]
graph = [[] for _ in range(n + 1)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	graph[a].append((b, c))
	graph[b].append((a, c))
	unions[c].merge(a, b)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	ans = 0
	for i in range(1, m + 1):
		ans += unions[i].find(a) == unions[i].find(b)
	print(ans)


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) = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	g[a - 1].append((b - 1, c - 1))
	g[b - 1].append((a - 1, c - 1))

def dfs(x, c, t):
	if x == t:
		return True
	v[x] = 1
	for j in g[x]:
		if j[1] == c and v[j[0]] == 0:
			if dfs(j[0], c, t):
				return True
	return False
q = int(input())
o = [0] * q
v = []
for i in range(q):
	(f, y) = map(int, input().split())
	for c in range(100):
		v = [0] * n
		if dfs(f - 1, c, y - 1):
			o[i] += 1
print('\n'.join(list(map(str, o))))


from collections import defaultdict

def DFS(d, a, visited):
	visited[a] = 1
	if a in d:
		for i in d[a]:
			if visited[i] == 1:
				continue
			else:
				DFS(d, i, visited)
(n, m) = map(int, input().split())
l = [defaultdict(list) for i in range(m + 1)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	l[c][a].append(b)
	l[c][b].append(a)
q = int(input())
for i in range(q):
	(a, b) = map(int, input().split())
	r = 0
	for j in l:
		visited = [0 for i in range(n + 1)]
		DFS(j, a, visited)
		if visited[a] == 1 and visited[b] == 1:
			r = r + 1
	print(r)


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)


def dfs(x, y, color):
	visited = [False for i in range(n + 1)]
	visited[x] = True
	stack = [x]
	while stack:
		node = stack.pop()
		for (child, childcolor) in g[node]:
			if visited[child] == False and childcolor == color:
				visited[child] = True
				stack.append(child)
	if visited[y] == True:
		return True
	return False
(n, m) = map(int, input().split())
g = {i: [] for i in range(1, n + 1)}
s = set()
for i in range(m):
	(u, v, c) = map(int, input().split())
	s.add(c)
	g[u].append([v, c])
	g[v].append([u, c])
s = list(s)
ans = [[0 for i in range(n + 1)] for j in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, n + 1):
		for c in s:
			if i != j:
				if dfs(i, j, c):
					ans[i][j] += 1
q = int(input())
for i in range(q):
	(u, v) = map(int, input().split())
	print(ans[u][v])


def main():
	(n, m) = map(int, input().split())
	edges = {_: {} for _ in range(1, m + 1)}
	for _ in range(m):
		(a, b, c) = 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) = map(int, input().split())
		x = 0
		for dcolor in 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))
main()


import sys, os, io
import math, bisect, operator
(inf, mod) = (float('inf'), 10 ** 9 + 7)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
I = lambda : int(sys.stdin.buffer.readline())
Neo = lambda : list(map(int, sys.stdin.buffer.readline().split()))
(n, m) = Neo()
Color = defaultdict(set)
G = defaultdict(set)
C = set()

def addEdge(a, b):
	G[a].add(b)
	G[b].add(a)

def addColor(a, b, c):
	Color[a, b].add(c)
	Color[b, a].add(c)
	C.add(c)
for i in range(m):
	(a, b, c) = Neo()
	addColor(a, b, c)
	addEdge(a, b)
vis = [False] * (n + 1)
Ans = []

def fun(node, dest, vis, grp):
	if not grp:
		return
	if node == dest:
		for i in grp:
			Ans.append(i)
		return
	vis[node] = True
	for i in G.get(node, []):
		if not vis[i]:
			newvis = vis.copy()
			z = grp.intersection(Color[node, i])
			fun(i, dest, newvis, z)
for i in range(I()):
	(a, b) = Neo()
	vis = [False] * (n + 1)
	grp = C.copy()
	fun(a, b, vis, grp)
	print(len(set(Ans)))
	Ans = []


def find(num, color):
	while dsu[color][num] != num:
		num = dsu[color][num]
	return num
inp = lambda : map(int, input().split())
(n, m) = inp()
dsu = [[i for i in range(n + 1)] for _ in range(101)]
for i in range(m):
	(x, y, z) = inp()
	x1 = find(x, z)
	y1 = find(y, z)
	if x1 != y1:
		dsu[z][x1] = y1
q = int(input())
for i in range(q):
	(x, y) = inp()
	ans = 0
	for j in range(101):
		if find(x, j) == find(y, j):
			ans += 1
	print(ans)


def find(c, x):
	p = dsu[c]
	if x == p[x]:
		return x
	return find(c, p[x])

def union(c, x, y):
	x = find(c, x)
	y = find(c, y)
	if x == y:
		return
	p = dsu[c]
	p[x] = y
(n, m) = map(int, input().split())
dsu = [[i for i in range(n + 1)] for _ in range(m + 1)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	union(c, a, b)
q = int(input())
for _ in range(q):
	(a, b) = map(int, input().split())
	count = 0
	for c in range(1, m + 1):
		if find(c, a) == find(c, b):
			count += 1
	print(count)


def dfs(start, color):
	for i in g[start]:
		if not vis[i[0]] and i[1] == color:
			vis[i[0]] = True
			dfs(i[0], i[1])
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	g[a - 1].append((b - 1, c))
	g[b - 1].append((a - 1, c))
q = int(input())
res = [0] * q
for i in range(q):
	(u, v) = map(int, input().split())
	for j in range(1, m + 1):
		vis = [False] * n
		dfs(u - 1, j)
		if vis[v - 1]:
			res[i] += 1
for i in res:
	print(i)


from collections import defaultdict

def dfs(graph, start, end, visited, color):
	q = [start]
	while q:
		node = q.pop()
		visited[node] = True
		if node == end:
			break
		for v in graph[color][node]:
			if not visited[v]:
				q.append(v)

def has_path(graph, start, end, visited, color):
	for i in range(len(visited)):
		visited[i] = False
	dfs(graph, start, end, visited, color)
	return visited[end]
(n, m) = map(int, input().split())
graph = defaultdict(lambda : defaultdict(list))
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	graph[c][a].append(b)
	graph[c][b].append(a)
visited = [False] * n
q = int(input())
for _ in range(q):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	ans = 0
	for c in graph.keys():
		if has_path(graph, u, v, visited, c):
			ans += 1
	print(ans)


from collections import defaultdict

def dfs(i, col):
	bool[i - 1] = True
	for j in hash1[i]:
		if j[1] == col:
			if bool[j[0] - 1] == False:
				dfs(j[0], col)
(n, m) = map(int, input().split())
hash1 = defaultdict(list)
hash2 = defaultdict(set)
for i in range(m):
	(a, b, c) = map(int, input().split())
	hash1[a].append([b, c])
	hash2[a].add(c)
	hash1[b].append([a, c])
	hash2[b].add(c)
q = int(input())
ans = []
for i in range(q):
	(a, b) = map(int, input().split())
	count = 0
	for j in hash2[a]:
		bool = [False] * n
		dfs(a, j)
		if bool[b - 1] == True:
			count += 1
	ans.append(count)
print(*ans)


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]

def bfs(adj, s, k):
	vis = {i: False for i in adj}
	vis[s] = True
	qu = [s]
	while len(qu) != 0:
		e = qu.pop(0)
		if e == k:
			return True
		for i in adj[e]:
			if vis[i] != True:
				qu.append(i)
				vis[i] = True
	return False
(n, m) = value()
adj = {i: defaultdict(list) for i in range(1, m + 1)}
for i in range(m):
	(s, d, c) = value()
	adj[c][s].append(d)
	adj[c][d].append(s)
for i in range(Int()):
	(s, d) = value()
	ans = 0
	for i in range(1, m + 1):
		if s in adj[i].keys() and bfs(adj[i], s, d):
			ans += 1
	print(ans)


import sys
import math
import heapq
import bisect
from collections import Counter
from collections import defaultdict
from io import BytesIO, IOBase
import string

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None
		self.BUFSIZE = 8192

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_int():
	return int(input())

def get_ints():
	return list(map(int, input().split(' ')))

def get_int_grid(n):
	return [get_ints() for _ in range(n)]

def get_str():
	return input().split(' ')

def yes_no(b):
	if b:
		return 'YES'
	else:
		return 'NO'

def binary_search(good, left, right, delta=1, right_true=False):
	limits = [left, right]
	while limits[1] - limits[0] > delta:
		if delta == 1:
			mid = sum(limits) // 2
		else:
			mid = sum(limits) / 2
		if good(mid):
			limits[int(right_true)] = mid
		else:
			limits[int(~right_true)] = mid
	if good(limits[int(right_true)]):
		return limits[int(right_true)]
	else:
		return False

def prefix_sums(a, drop_zero=False):
	p = [0]
	for x in a:
		p.append(p[-1] + x)
	if drop_zero:
		return p[1:]
	else:
		return p

def prefix_mins(a, drop_zero=False):
	p = [float('inf')]
	for x in a:
		p.append(min(p[-1], x))
	if drop_zero:
		return p[1:]
	else:
		return p

class DSU:

	def __init__(self, nodes):
		self.p = [i for i in range(nodes)]
		self.r = [0 for i in range(nodes)]
		self.s = [1 for i in range(nodes)]

	def get(self, u):
		if u != self.p[u]:
			self.p[u] = self.get(self.p[u])
		return self.p[u]

	def union(self, u, v):
		u = self.get(u)
		v = self.get(v)
		if u != v:
			if self.r[u] > self.r[v]:
				(u, v) = (v, u)
			self.p[u] = v
			if self.r[u] == self.r[v]:
				self.r[v] += 1
			self.s[v] += self.s[u]

def solve_b():
	(n, m) = get_ints()
	dsus = [DSU(n) for _ in range(m)]
	for e in range(m):
		(a, b, c) = get_ints()
		dsus[c - 1].union(a - 1, b - 1)

	def respond(u, v):
		S = 0
		for color in range(m):
			if dsus[color].get(u - 1) == dsus[color].get(v - 1):
				S += 1
		return S
	q = get_int()
	for query in range(q):
		(u, v) = get_ints()
		print(respond(u, v))
	return
solve_b()


(n, m) = map(int, input().split())
graph = [[[-1] for x in range(n + 1)] for i in range(n + 1)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	if graph[a][b] != [-1]:
		graph[a][b].append(c)
	else:
		graph[a][b] = [c]

def bfs(start, end, color):
	(neighbors, visited) = ([start], set())
	while neighbors:
		(current, neighbors) = (neighbors, [])
		for each in current:
			for i in range(1, n + 1):
				if (color in graph[i][each] or color in graph[each][i]) and i not in visited:
					visited.add(i)
					if i == end:
						return True
					neighbors.append(i)
	return False
q = int(input())
for _ in range(q):
	(u, v) = map(int, input().split())
	(starting_colors, colors) = (set(), 0)
	for i in range(1, n + 1):
		if graph[i][u] != [-1]:
			starting_colors.update(graph[i][u])
		elif graph[u][i] != [-1]:
			starting_colors.update(graph[u][i])
	for each_color in starting_colors:
		if bfs(u, v, each_color):
			colors += 1
	print(colors)


def arr_inp(n):
	if n == 1:
		return [int(x) for x in stdin.readline().split()]
	elif n == 2:
		return [float(x) for x in stdin.readline().split()]
	else:
		return [str(x) for x in stdin.readline().split()]

class disjointset:

	def __init__(self, n):
		(self.rank, self.parent, self.n, self.nsets, self.edges) = (defaultdict(int), defaultdict(int), n, defaultdict(int), defaultdict(int))
		for i in range(1, n + 1):
			(self.parent[i], self.nsets[i]) = (i, 1)

	def find(self, x):
		if self.parent[x] == x:
			return x
		result = self.find(self.parent[x])
		self.parent[x] = result
		return result

	def union(self, x, y):
		(xpar, ypar) = (self.find(x), self.find(y))
		if xpar == ypar:
			self.edges[xpar] += 1
			return
		if self.rank[xpar] < self.rank[ypar]:
			self.parent[xpar] = ypar
			self.edges[ypar] += self.edges[xpar] + 1
			self.nsets[ypar] += self.nsets[xpar]
		elif self.rank[xpar] > self.rank[ypar]:
			self.parent[ypar] = xpar
			self.edges[xpar] += self.edges[ypar] + 1
			self.nsets[xpar] += self.nsets[ypar]
		else:
			self.parent[ypar] = xpar
			self.rank[xpar] += 1
			self.edges[xpar] += self.edges[ypar] + 1
			self.nsets[xpar] += self.nsets[ypar]
from sys import stdin
from collections import defaultdict
(n, m) = arr_inp(1)
color = [disjointset(n) for i in range(m)]
for i in range(m):
	(a, b, c) = arr_inp(1)
	color[c - 1].union(a, b)
for i in range(int(input())):
	(u, v) = arr_inp(1)
	ans = 0
	for j in range(m):
		if color[j].find(u) == color[j].find(v):
			ans += 1
	print(ans)


from collections import defaultdict

def dfs(adjlist, start, visited, nodes, color):
	if start in visited:
		return
	visited.add(start)
	for (v, c) in adjlist[start]:
		if c == color:
			nodes[v - 1] = nodes[start - 1]
			dfs(adjlist, v, visited, nodes, color)
(n, m) = map(int, input().split())
adjlist = defaultdict(list)
all_color = set()
for i in range(0, m):
	tmp = list(map(int, input().split()))
	adjlist[tmp[0]].append((tmp[1], tmp[2]))
	adjlist[tmp[1]].append((tmp[0], tmp[2]))
	all_color.add(tmp[2])
num_queries = int(input())
queries = []
for i in range(0, num_queries):
	queries.append(list(map(int, input().split())))
color_map = {}
for c in all_color:
	nodes = [i for i in range(1, n + 1)]
	for src in range(1, n + 1):
		visited = set()
		dfs(adjlist, src, visited, nodes, c)
		if len(visited) == n:
			break
	color_map[c] = nodes
for q in queries:
	count = 0
	for c in color_map.keys():
		if color_map[c][q[0] - 1] == color_map[c][q[1] - 1]:
			count += 1
	print(count)


(n, m) = map(int, input().split())
arr = [[] for i in range(n + 1)]
for i in range(1, m + 1):
	l = list(map(int, input().split()))
	arr[l[0]].append((l[1], l[2]))
	arr[l[1]].append((l[0], l[2]))

def dfs(a, b, k):
	if a == b:
		return True
	seen.append(a)
	for i in arr[a]:
		(x, c) = i
		if c == k and x not in seen:
			if dfs(x, b, k):
				return True
	return False
query = int(input())
count = 0
score = [0] * query
seen = []
for i in range(query):
	(a, b) = map(int, input().split())
	for k in range(1, 101):
		seen = []
		if dfs(a, b, k):
			count += 1
	score[i] = count
	count = 0
print('\n'.join(list(map(str, score))))


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


import math
import os
from io import BytesIO, IOBase
import sys
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict
(n, m) = map(int, input().split())
graphs = defaultdict(lambda : defaultdict(list))
for _ in range(m):
	(a, b, c) = map(int, input().split())
	graphs[c][a].append(b)
	graphs[c][b].append(a)
seen = set()

def dfs(curr, orig, color):
	if curr in seen:
		return
	seen.add(curr)
	for new in graphs[color][curr]:
		if new != orig:
			dfs(new, curr, color)
q = int(input())
for _ in range(q):
	(a, b) = map(int, input().split())
	found = 0
	for c in graphs.keys():
		seen.clear()
		dfs(a, -1, c)
		if b in seen:
			found += 1
	print(found)


import sys, os.path
from collections import *
from copy import *
import math
mod = 10 ** 9 + 7
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def dfs(x, y, z):
	vis[x] = 1
	if x == y:
		return
	for v in adj[x]:
		if vis[v[0]]:
			continue
		if v[1] == z:
			dfs(v[0], y, z)
adj = defaultdict(list)
(n, m) = map(int, input().split())
s = set()
for i in range(m):
	(a, b, c) = map(int, input().split())
	adj[a].append((b, c))
	adj[b].append((a, c))
	s.add(c)
q = int(input())
for i in range(q):
	(x, y) = map(int, input().split())
	count = 0
	for j in s:
		vis = [0 for i in range(n + 1)]
		dfs(x, y, j)
		if vis[y]:
			count += 1
	print(count)


def main():

	def dfs(index, color):
		visited[index] = True
		for p in adj[index]:
			if not visited[p[0]] and p[1] == color:
				dfs(p[0], color)
	(n, m) = map(int, input().split())
	adj = [[] for _ in range(n)]
	for _ in range(m):
		(a, b, c) = map(int, input().split())
		adj[a - 1].append((b - 1, c))
		adj[b - 1].append((a - 1, c))
	q = int(input())
	for _ in range(q):
		(a, b) = map(int, input().split())
		ans = 0
		for i in range(1, m + 1):
			visited = [False] * n
			dfs(a - 1, i)
			if visited[b - 1]:
				ans += 1
		print(ans)
main()


f = lambda : map(int, input().split())
(n, m) = f()
p = [list(range(n + 1)) for x in range(m + 1)]

def g(c, x):
	if x != p[c][x]:
		p[c][x] = g(c, p[c][x])
	return p[c][x]
for i in range(m):
	(a, b, c) = f()
	p[c][g(c, a)] = g(c, b)
for j in range(int(input())):
	(a, b) = f()
	print(sum((g(i, a) == g(i, b) for i in range(m + 1))))


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

def dfs(v, c, u, vis):
	ans = []
	vis[v] = True
	if v == u:
		return [c]
	for i in adj[v]:
		if vis[i[0]] or i[1] != c:
			continue
		ans += dfs(i[0], c, u, vis)
	return ans
q = int(input())
while q > 0:
	q -= 1
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	ans = []
	for i in adj[a]:
		vis = [False] * n
		vis[a] = True
		ans += dfs(i[0], i[1], b, vis)
	print(len(set(ans)))


class CodeforcesTask505BSolution:

	def __init__(self):
		self.result = ''
		self.n_m = []
		self.edges = []
		self.q = 0
		self.queries = []

	def read_input(self):
		self.n_m = [int(x) for x in input().split(' ')]
		for x in range(self.n_m[1]):
			self.edges.append([int(y) for y in input().split(' ')])
		self.q = int(input())
		for x in range(self.q):
			self.queries.append([int(y) for y in input().split(' ')])

	def process_task(self):
		graphs = [[[] for x in range(self.n_m[0])] for c in range(self.n_m[1])]
		for edge in self.edges:
			graphs[edge[2] - 1][edge[0] - 1].append(edge[1])
			graphs[edge[2] - 1][edge[1] - 1].append(edge[0])
		results = []
		for query in self.queries:
			to_visit = [(query[0], c) for c in range(self.n_m[1])]
			used = set()
			visited = [[False] * self.n_m[0] for x in range(self.n_m[1])]
			while to_visit:
				visiting = to_visit.pop(-1)
				if visiting[1] not in used and (not visited[visiting[1]][visiting[0] - 1]):
					visited[visiting[1]][visiting[0] - 1] = True
					if visiting[0] == query[1]:
						used.add(visiting[1])
					else:
						to_visit.extend([(x, visiting[1]) for x in graphs[visiting[1]][visiting[0] - 1]])
			colors = len(used)
			results.append(colors)
		self.result = '\n'.join([str(x) for x in results])

	def get_result(self):
		return self.result
Solution = CodeforcesTask505BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


(n, m) = map(int, input().split())
graphs = [[[] for _ in range(n)] for _ in range(m)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	graphs[c - 1][a - 1].append(b - 1)
	graphs[c - 1][b - 1].append(a - 1)
used = None

def dfs(vertex, color):
	used[vertex] = True
	for nei in graphs[color][vertex]:
		if not used[nei]:
			dfs(nei, color)
q = int(input())
for _ in range(q):
	(u, v) = map(int, input().split())
	c = 0
	for _color in range(m):
		used = [False] * n
		dfs(u - 1, _color)
		if used[v - 1]:
			c += 1
	print(c)


from collections import Counter as cntr
from math import inf

def cin():
	return map(int, input().split(' '))

def dfs(graph, src, dest, color):
	global count, visited
	if src == dest:
		count += 1
		return 0
	for v in range(n):
		if graph[src][v] and visited[v] == False and (color in graph[src][v]):
			l = graph[src][v]
			for j in l:
				if color == j:
					visited[v] = True
					dfs(graph, v, dest, color)
(n, m) = cin()
kita = [[0 for i in range(n)] for i in range(n)]
clrs = [[] for i in range(n)]
for i in range(m):
	(a, b, c) = cin()
	a -= 1
	b -= 1
	if kita[a][b] == 0:
		kita[a][b] = [c]
		kita[b][a] = [c]
	else:
		kita[a][b].append(c)
		kita[b][a].append(c)
	clrs[a].append(c)
	clrs[b].append(c)
q = int(input())
for i in range(q):
	count = 0
	(u, v) = cin()
	u -= 1
	v -= 1
	ll = set(clrs[u])
	for jj in ll:
		visited = [False for i in range(n)]
		visited[u] = True
		dfs(kita, u, v, jj)
	print(count)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
INF = 99999999999999999999999999999999

def outIn(x):
	print(x, flush=True)
	return input()

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		(n, m) = ria()
		d = {}
		for i in range(m):
			(a, b, c) = ria()
			if c not in d:
				d[c] = [[a, b]]
			else:
				d[c].append([a, b])

		def dfs(graph, start, visited):
			n = len(graph)
			comp = []
			stack = [start]
			t = 0
			while stack:
				start = stack[-1]
				if not visited[start]:
					comp.append(start)
					visited[start] = True
					for child in graph[start]:
						if not visited[child]:
							stack.append(child)
				else:
					stack.pop()
			return (comp, visited)
		fd = {}
		for i in range(1, m + 1):
			if i in d:
				visited = [False] * (n + 1)
				graph = [[] for i in range(n + 1)]
				vert = {}
				for (u, v) in d[i]:
					vert[u] = 1
					vert[v] = 1
					graph[u].append(v)
					graph[v].append(u)
				for j in vert:
					if not visited[j]:
						(comp, visited) = dfs(graph, j, visited)
						if i in fd:
							fd[i].append(comp)
						else:
							fd[i] = [comp]
		q = ri()
		for i in range(q):
			(u, v) = ria()
			count = 0
			for j in range(1, m + 1):
				f = 0
				if j in fd:
					for t in fd[j]:
						if u in t and v in t:
							f = 1
							break
				count += f
			print(count)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


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


import queue
(n, m) = map(int, input().strip().split())
adj = [[] for i in range(n + 1)]

def doable(s, t, c):
	global adj, n, m
	q = queue.Queue()
	visited = [False for i in range(n + 1)]
	q.put(s)
	visited[s] = True
	while not q.empty():
		u = q.get()
		for v in adj[u]:
			if v[1] == c and (not visited[v[0]]):
				q.put(v[0])
				visited[v[0]] = True
	return visited[t]
maxc = 0
for _ in range(m):
	(u, v, c) = map(int, input().strip().split())
	adj[u].append((v, c))
	adj[v].append((u, c))
	maxc = max(maxc, c)
q = int(input())
for _ in range(q):
	(u, v) = map(int, input().strip().split())
	ans = 0
	for color in range(1, maxc + 1):
		if doable(u, v, color):
			ans += 1
	print(ans)


class ufds:

	def __init__(self):
		self.rank = dict()
		self.value = dict()

	def union(self, a, b):
		(x, y) = (self.findSet(a), self.findSet(b))
		if self.rank[x] > self.rank[y]:
			self.value[y] = x
		else:
			self.value[x] = y
		if self.rank[x] == self.rank[y]:
			self.rank[y] += 1

	def findSet(self, x):
		if x != self.value[x]:
			self.value[x] = self.findSet(self.value[x])
		return self.value[x]

	def sameSet(self, a, b):
		return self.findSet(a) == self.findSet(b)

	def createKey(self, x):
		self.rank.update({x: 0})
		self.value.update({x: x})
a = list(map(int, input().split()))
size = a[0]
graph = dict()
for i in range(a[1]):
	b = list(map(int, input().split()))
	color = b[2]
	if color not in graph.keys():
		graph.update({color: ufds()})
		for i in range(size):
			graph[color].createKey(i + 1)
	graph[color].union(b[0], b[1])
for i in range(int(input())):
	b = list(map(int, input().split()))
	counter = 0
	for j in graph.keys():
		if graph[j].sameSet(b[0], b[1]):
			counter += 1
	print(counter)


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) = map(int, input().split())
g = [[[] for _ in range(ver_n)] for _ in range(edge_n)]
for _ in range(edge_n):
	(a, b, c) = map(lambda x: int(x) - 1, 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) = map(lambda x: int(x) - 1, input().split())
	for j in range(edge_n):
		if colored[j][u] == colored[j][v]:
			cnt += 1
	print(cnt)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict

def dfs(s, f):
	if s == v:
		return True
	vis[s] = 1
	for i in g[s]:
		if vis[i[0]] == 0 and i[1] == f:
			if dfs(i[0], f):
				return True
	return False
(n, m) = map(int, input().split())
g = [[] for i in range(n + 2)]
for i in range(m):
	(u, v, d) = map(int, input().split())
	g[u].append([v, d])
	g[v].append([u, d])
q = int(input())
for _ in range(q):
	(u, v) = map(int, input().split())
	cnt = 0
	for i in range(1, 101):
		vis = [0] * 101
		if dfs(u, i):
			cnt += 1
	print(cnt)


(n, m) = map(int, input().split())
graph = [[] for _ in range(105)]
for _ in range(m):
	(a, b, c) = map(int, input().split())
	graph[a].append([b, c])
	graph[b].append([a, c])

def dfs(source, destination, colour):
	if source == destination:
		return True
	visited[source] = True
	for node in graph[source]:
		if node[1] == colour and visited[node[0]] is False:
			if dfs(node[0], destination, colour):
				return True
	return False
for i in range(int(input())):
	ans = 0
	(f, y) = map(int, input().split())
	for colour in range(1, 101):
		visited = [False] * (n + 1)
		if dfs(f, y, colour):
			ans += 1
	print(ans)


from sys import stdin, stdout

def find(node, color):
	x = []
	while colors[color][node] > 0:
		x.append(node)
		node = colors[color][node]
	for i in x:
		colors[color][i] = node
	return node

def union(node1, node2, color):
	if node1 != node2:
		if colors[color][node1] > colors[color][node2]:
			(node1, node2) = (node2, node1)
		colors[color][node1] += colors[color][node2]
		colors[color][node2] = node1
(n, m) = map(int, stdin.readline().strip().split())
colors = [[-1 for i in range(n + 1)] for j in range(m + 1)]
for __ in range(m):
	(a, b, c) = map(int, stdin.readline().strip().split())
	union(find(b, c), find(a, c), c)
q = int(stdin.readline().strip())
outputs = []
for __ in range(q):
	count = 0
	(a, b) = map(int, stdin.readline().strip().split())
	for i in range(1, m + 1):
		if find(a, i) == find(b, i):
			count += 1
	outputs.append(count)
for output in outputs:
	stdout.write(f'{output}\n')


import sys
from collections import defaultdict
from functools import lru_cache
from collections import Counter

def mi(s):
	return map(int, s.strip().split())

def lmi(s):
	return list(mi(s))

def mf(f, s):
	return map(f, s)

def lmf(f, s):
	return list(mf(f, s))

def path(graph, u, v, color, visited):
	if u == v:
		return True
	elif u in visited:
		return False
	visited.add(u)
	for (child, c) in graph[u]:
		if color == c and path(graph, child, v, color, visited):
			return True
	return False

def main(graph, queries, colors):
	ans = []
	for (u, v) in queries:
		c = 0
		for color in colors:
			if path(graph, u, v, color, set()):
				c += 1
		ans.append(c)
	for n in ans:
		print(n)
queries = []
colors = set()
for (e, line) in enumerate(sys.stdin.readlines()):
	if e == 0:
		(n, ed) = mi(line)
		graph = defaultdict(list)
		for i in range(1, n + 1):
			graph[i]
		k = 0
	elif ed > 0:
		(a, b, c) = mi(line)
		graph[a].append((b, c))
		graph[b].append((a, c))
		colors.add(c)
		ed -= 1
	elif ed == 0:
		ed -= 1
		continue
	else:
		queries.append(lmi(line))
main(graph, queries, colors)


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)


from sys import stdin, stdout
input = stdin.readline

def main():
	(n, m) = map(int, input().split())
	sets = [list(range(n + 1)) for i in range(m)]
	sizes = [[1] * (n + 1) for i in range(m)]

	def get(a, ind):
		if sets[ind][a] != a:
			sets[ind][a] = get(sets[ind][a], ind)
		return sets[ind][a]

	def union(a, b, ind):
		a = get(a, ind)
		b = get(b, ind)
		if a == b:
			return
		if sizes[ind][a] > sizes[ind][b]:
			(a, b) = (b, a)
		sets[ind][a] = b
		sizes[ind][b] += sizes[ind][a]
	for i in range(m):
		(a, b, c) = map(int, input().split())
		a -= 1
		b -= 1
		c -= 1
		union(a, b, c)
	q = int(input())
	for i in range(q):
		ans = 0
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		for j in range(m):
			ans += int(get(u, j) == get(v, j))
		print(ans)
main()


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)


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)


from collections import defaultdict

def dfs(g, u, visited=None):
	if visited is None:
		visited = set()
	visited.add(u)
	for node in g[u]:
		if node not in visited:
			dfs(g, node, visited)
	return visited

def main():
	(n, m) = map(int, input().split())
	graphs = {}
	for _ in range(m):
		(a, b, c) = map(int, input().split())
		if c not in graphs:
			graphs[c] = defaultdict(list)
		graphs[c][a].append(b)
		graphs[c][b].append(a)
	num_queries = int(input())
	for _ in range(num_queries):
		(u, v) = map(int, input().split())
		ans = 0
		for g in graphs.values():
			if v in dfs(g, u):
				ans += 1
		print(ans)
main()