D. Mr. Kitayuta's Colorful Graph

problem_index: D

time_limit: 4 seconds

memory_limit: 256 megabytes

note:
Let's consider the first sample.
![image](images/cf_506_D/1.png)   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.

solutions: ["(n, m) = map(int, input().split())\narr = [[] for i in range(n + 1)]\nfor i in range(1, m + 1):\n\tl = list(map(int, input().split()))\n\tarr[l[0]].append((l[1], l[2]))\n\tarr[l[1]].append((l[0], l[2]))\n\ndef dfs(a, b, k):\n\tif a == b:\n\t\treturn True\n\tseen.append(a)\n\tfor i in arr[a]:\n\t\t(x, c) = i\n\t\tif c == k and x not in seen:\n\t\t\tif dfs(x, b, k):\n\t\t\t\treturn True\n\treturn False\nquery = int(input())\ncount = 0\nscore = [0] * query\nseen = []\nfor i in range(query):\n\t(a, b) = map(int, input().split())\n\tfor k in range(1, 101):\n\t\tseen = []\n\t\tif dfs(a, b, k):\n\t\t\tcount += 1\n\tscore[i] = count\n\tcount = 0\nprint('\\n'.join(list(map(str, score))))\n", "import os.path\nfrom math import gcd, floor, ceil\nfrom collections import *\nimport sys\nmod = 1000000007\nINF = float('inf')\n\ndef st():\n\treturn list(sys.stdin.readline().strip())\n\ndef li():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef mp():\n\treturn map(int, sys.stdin.readline().split())\n\ndef inp():\n\treturn int(sys.stdin.readline())\n\ndef pr(n):\n\treturn sys.stdout.write(str(n) + '\\n')\n\ndef prl(n):\n\treturn sys.stdout.write(str(n) + ' ')\nif os.path.exists('input.txt'):\n\tsys.stdin = open('input.txt', 'r')\n\tsys.stdout = open('output.txt', 'w')\n(n, m) = mp()\nd = defaultdict(list)\nfor _ in range(m):\n\t(a, b, c) = mp()\n\td[a, c].append(b)\n\td[b, c].append(a)\nQ = inp()\nv = [0 for i in range(n + 1)]\nfor i in range(Q):\n\t(x, y) = mp()\n\tans = 0\n\tfor j in range(1, m + 1):\n\t\tq = deque()\n\t\tq.append((x, j))\n\t\tcopy_visited = list(v)\n\t\tcopy_visited[x] = 1\n\t\twhile q:\n\t\t\t(a, b) = q.popleft()\n\t\t\tif a == y:\n\t\t\t\tans += 1\n\t\t\t\tbreak\n\t\t\tfor k in d[a, b]:\n\t\t\t\tif not copy_visited[k]:\n\t\t\t\t\tcopy_visited[k] = 1\n\t\t\t\t\tq.append((k, b))\n\tprint(ans)\n", "(n, m) = list(map(int, input().split()))\narr = [[i for i in range(n)] for j in range(m)]\n\ndef find(c, x):\n\tif x == arr[c][x]:\n\t\treturn x\n\tarr[c][x] = find(c, arr[c][x])\n\treturn arr[c][x]\nfor i in range(m):\n\t(a, b, c) = list(map(int, input().split()))\n\ta -= 1\n\tb -= 1\n\tc -= 1\n\tarr[c][find(c, a)] = find(c, b)\nfor i in range(int(input())):\n\t(a, b) = list(map(int, input().split()))\n\ta -= 1\n\tb -= 1\n\tres = sum((1 if find(i, a) == find(i, b) else 0 for i in range(m)))\n\tprint(res)\n", "from collections import Counter as cntr\nfrom math import inf\n\ndef cin():\n\treturn map(int, input().split(' '))\n\ndef dfs(graph, src, dest, color):\n\tglobal count, visited\n\tif src == dest:\n\t\tcount += 1\n\t\treturn 0\n\tfor v in range(n):\n\t\tif graph[src][v] and visited[v] == False and (color in graph[src][v]):\n\t\t\tl = graph[src][v]\n\t\t\tfor j in l:\n\t\t\t\tif color == j:\n\t\t\t\t\tvisited[v] = True\n\t\t\t\t\tdfs(graph, v, dest, color)\n(n, m) = cin()\nkita = [[0 for i in range(n)] for i in range(n)]\nclrs = [[] for i in range(n)]\nfor i in range(m):\n\t(a, b, c) = cin()\n\ta -= 1\n\tb -= 1\n\tif kita[a][b] == 0:\n\t\tkita[a][b] = [c]\n\t\tkita[b][a] = [c]\n\telse:\n\t\tkita[a][b].append(c)\n\t\tkita[b][a].append(c)\n\tclrs[a].append(c)\n\tclrs[b].append(c)\nq = int(input())\nfor i in range(q):\n\tcount = 0\n\t(u, v) = cin()\n\tu -= 1\n\tv -= 1\n\tll = set(clrs[u])\n\tfor jj in ll:\n\t\tvisited = [False for i in range(n)]\n\t\tvisited[u] = True\n\t\tdfs(kita, u, v, jj)\n\tprint(count)\n", "def create_adj(edge):\n\tedges = {}\n\tfor u in edge:\n\t\tif u[0] in edges.keys():\n\t\t\tedges[u[0]].append(u[1])\n\t\telse:\n\t\t\tedges[u[0]] = [u[1]]\n\treturn edges\n\ndef explore(adj, v, visited):\n\tvisited[v] = True\n\tfor i in adj[v]:\n\t\tif visited[i] == False:\n\t\t\texplore(adj, i, visited)\n\ndef find(adj, u, v):\n\tglobal c\n\tif u not in adj.keys() or v not in adj.keys():\n\t\treturn\n\tvisited = {}\n\tfor r in adj.keys():\n\t\tvisited[r] = False\n\texplore(adj, u, visited)\n\tif visited[v] == True:\n\t\tc = c + 1\n\treturn c\n(n, m) = map(int, input().split())\nht = {}\nfor i in range(m):\n\t(a, b, c) = map(int, input().split())\n\tif c in ht.keys():\n\t\tht[c].append([a, b])\n\t\tht[c].append([b, a])\n\telse:\n\t\tht[c] = [[a, b], [b, a]]\nq = int(input())\nc = 0\nfor j in range(q):\n\tc = 0\n\t(u, v) = map(int, input().split())\n\tfor y in ht.keys():\n\t\tadj = create_adj(ht[y])\n\t\tfind(adj, u, v)\n\tprint(c)\n", "from collections import defaultdict\n\ndef dfs(i, col):\n\tbool[i - 1] = True\n\tfor j in hash1[i]:\n\t\tif j[1] == col:\n\t\t\tif bool[j[0] - 1] == False:\n\t\t\t\tdfs(j[0], col)\n(n, m) = map(int, input().split())\nhash1 = defaultdict(list)\nhash2 = defaultdict(set)\nfor i in range(m):\n\t(a, b, c) = map(int, input().split())\n\thash1[a].append([b, c])\n\thash2[a].add(c)\n\thash1[b].append([a, c])\n\thash2[b].add(c)\nq = int(input())\nans = []\nfor i in range(q):\n\t(a, b) = map(int, input().split())\n\tcount = 0\n\tfor j in hash2[a]:\n\t\tbool = [False] * n\n\t\tdfs(a, j)\n\t\tif bool[b - 1] == True:\n\t\t\tcount += 1\n\tans.append(count)\nprint(*ans)\n", "f = lambda : input()\nml = lambda : list(map(int, f().split()))\n(n, m) = ml()\ng = [[[] for x in range(n + 1)] for x in range(m + 1)]\nfor i in range(m):\n\t(a, b, c) = ml()\n\tg[c][a].append(b)\n\tg[c][b].append(a)\nq = int(f())\n\ndef dfs(c, start, end):\n\tglobal g, n\n\tdiscovered = [False] * (n + 1)\n\ts = []\n\ts.append(start)\n\twhile s:\n\t\tv = s.pop()\n\t\tif not discovered[v]:\n\t\t\tdiscovered[v] = True\n\t\t\tfor i in g[c][v]:\n\t\t\t\tif i == end:\n\t\t\t\t\treturn True\n\t\t\t\ts.append(i)\n\treturn False\nfor i in range(q):\n\t(u, v) = ml()\n\tcount = 0\n\tfor j in range(1, m + 1):\n\t\tif g[j]:\n\t\t\tif dfs(j, u, v):\n\t\t\t\tcount += 1\n\tprint(count)\n", "def dfs_paths(graph, start, goal, path=list()):\n\tif not path:\n\t\tpath.append(start)\n\tif start == goal:\n\t\tyield path\n\tfor vertex in graph[start] - set(path):\n\t\tyield from dfs_paths(graph, vertex, goal, path=path + [vertex])\n(n, m) = map(int, input().split())\ngraph = {}\nfor _ in range(m):\n\t(a, b, c) = map(int, input().split())\n\tif c not in graph:\n\t\tgraph[c] = {}\n\tif a not in graph[c]:\n\t\tgraph[c][a] = set()\n\tif b not in graph[c]:\n\t\tgraph[c][b] = set()\n\tgraph[c][a].add(b)\n\tgraph[c][b].add(a)\nq = int(input())\nfor _ in range(q):\n\t(u, v) = map(int, input().split())\n\tcount = 0\n\tfor k in graph:\n\t\tif u not in graph[k] or v not in graph[k]:\n\t\t\tcontinue\n\t\tif len(list(dfs_paths(graph[k], u, v, []))) > 0:\n\t\t\tcount += 1\n\tprint(count)\n", "(n, m) = map(int, input().split())\nmx = [[0] * n for i in range(n)]\nused = None\n\ndef dfs(cur, trg, color):\n\tif cur == trg:\n\t\treturn True\n\tif not used[cur]:\n\t\tused[cur] = True\n\t\tfor i in range(n):\n\t\t\tif mx[cur][i] & color:\n\t\t\t\tif dfs(i, trg, color):\n\t\t\t\t\treturn True\n\treturn False\nfor i in range(m):\n\t(a, b, c) = map(lambda s: int(s) - 1, input().split())\n\tmx[a][b] |= 1 << c\n\tmx[b][a] |= 1 << c\nq = int(input())\nfor i in range(q):\n\t(u, v) = map(lambda s: int(s) - 1, input().split())\n\tresult = 0\n\tfor j in range(m):\n\t\tused = [False] * n\n\t\tif dfs(u, v, 1 << j):\n\t\t\tresult += 1\n\tprint(result)\n", "from collections import defaultdict, deque\n\ndef bfs(g, s, c):\n\tvisited = set()\n\tq = deque([s])\n\twhile len(q) > 0:\n\t\tv = q.pop()\n\t\tvisited.add(v)\n\t\tfor (adj, adj_c) in g[v]:\n\t\t\tif adj_c == c and adj not in visited and (adj not in q):\n\t\t\t\tq.append(adj)\n\treturn visited\n\ndef con_components(g, c):\n\tvisited = set()\n\tcomponents = []\n\tfor s in g.keys():\n\t\tif s not in visited:\n\t\t\tnodes = bfs(g, s, c)\n\t\t\tcomponents.append(nodes)\n\t\t\tvisited |= nodes\n\treturn components\n\ndef main():\n\t(n, m) = map(int, input().split())\n\tg = defaultdict(list)\n\tcolors = set()\n\tfor _ in range(m):\n\t\t(a, b, c) = map(int, input().split())\n\t\tg[a].append((b, c))\n\t\tg[b].append((a, c))\n\t\tcolors.add(c)\n\tcomponents = {c: con_components(g, c) for c in colors}\n\tq = int(input())\n\tfor _ in range(q):\n\t\t(u, v) = map(int, input().split())\n\t\tct = 0\n\t\tfor c in colors:\n\t\t\tfor comp in components[c]:\n\t\t\t\tif u in comp and v in comp:\n\t\t\t\t\tct += 1\n\t\tprint(ct)\nmain()\n", "(n, m) = map(int, input().split())\ng = [[] for _ in range(n)]\nfor _ in range(m):\n\t(a, b, c) = map(int, input().split())\n\tg[a - 1].append((b - 1, c - 1))\n\tg[b - 1].append((a - 1, c - 1))\n\ndef dfs(x, c, t):\n\tif x == t:\n\t\treturn True\n\tv[x] = 1\n\tfor j in g[x]:\n\t\tif j[1] == c and v[j[0]] == 0:\n\t\t\tif dfs(j[0], c, t):\n\t\t\t\treturn True\n\treturn False\nq = int(input())\no = [0] * q\nv = []\nfor i in range(q):\n\t(f, y) = map(int, input().split())\n\tfor c in range(100):\n\t\tv = [0] * n\n\t\tif dfs(f - 1, c, y - 1):\n\t\t\to[i] += 1\nprint('\\n'.join(list(map(str, o))))\n", "import sys\ninf = float('inf')\nsys.setrecursionlimit(1000000)\nfrom math import ceil, floor, log, sqrt, factorial, pow, pi, gcd\nabc = 'abcdefghijklmnopqrstuvwxyz'\nabd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}\n(mod, MOD) = (1000000007, 998244353)\nvow = ['a', 'e', 'i', 'o', 'u']\n(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])\n\nclass UnionFind:\n\n\tdef __init__(self, n):\n\t\tself.parent = list(range(n))\n\n\tdef find(self, a):\n\t\tacopy = a\n\t\twhile a != self.parent[a]:\n\t\t\ta = self.parent[a]\n\t\twhile acopy != a:\n\t\t\t(self.parent[acopy], acopy) = (a, self.parent[acopy])\n\t\treturn a\n\n\tdef union(self, a, b):\n\t\tself.parent[self.find(b)] = self.find(a)\n\ndef get_array():\n\treturn list(map(int, sys.stdin.readline().strip().split()))\n\ndef get_ints():\n\treturn map(int, sys.stdin.readline().strip().split())\n\ndef input():\n\treturn sys.stdin.readline().strip()\n(n, m) = get_ints()\nArr = [0] * 105\nfor i in range(105):\n\tArr[i] = UnionFind(105)\nfor i in range(m):\n\t(x, y, z) = get_ints()\n\tArr[z].union(x, y)\nq = int(input())\nwhile q > 0:\n\t(x, y) = get_ints()\n\tcount = 0\n\tfor i in range(105):\n\t\tif Arr[i].find(x) == Arr[i].find(y):\n\t\t\tcount += 1\n\tprint(count)\n\tq -= 1\n", "import os\nimport sys\nfrom math import *\nfrom collections import *\nfrom bisect import *\nfrom io import BytesIO, IOBase\n\ndef vsInput():\n\tsys.stdin = open('input.txt', 'r')\n\tsys.stdout = open('output.txt', 'w')\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n\ndef value():\n\treturn tuple(map(int, input().split()))\n\ndef array():\n\treturn [int(i) for i in input().split()]\n\ndef Int():\n\treturn int(input())\n\ndef Str():\n\treturn input()\n\ndef arrayS():\n\treturn [i for i in input().split()]\n\ndef bfs(adj, s, k):\n\tvis = {i: False for i in adj}\n\tvis[s] = True\n\tqu = [s]\n\twhile len(qu) != 0:\n\t\te = qu.pop(0)\n\t\tif e == k:\n\t\t\treturn True\n\t\tfor i in adj[e]:\n\t\t\tif vis[i] != True:\n\t\t\t\tqu.append(i)\n\t\t\t\tvis[i] = True\n\treturn False\n(n, m) = value()\nadj = {i: defaultdict(list) for i in range(1, m + 1)}\nfor i in range(m):\n\t(s, d, c) = value()\n\tadj[c][s].append(d)\n\tadj[c][d].append(s)\nfor i in range(Int()):\n\t(s, d) = value()\n\tans = 0\n\tfor i in range(1, m + 1):\n\t\tif s in adj[i].keys() and bfs(adj[i], s, d):\n\t\t\tans += 1\n\tprint(ans)\n", "(n, m) = list(map(int, input().split()))\np = [[i for i in range(n)] for j in range(m)]\n\ndef f(ci, xi):\n\tif xi == p[ci][xi]:\n\t\treturn xi\n\tp[ci][xi] = f(ci, p[ci][xi])\n\treturn p[ci][xi]\n\ndef uni(ci, xi, yi):\n\tp[ci][f(ci, xi)] = f(ci, yi)\nfor i in range(m):\n\t(a, b, c) = list(map(int, input().split()))\n\tuni(c - 1, a - 1, b - 1)\nfor i in range(int(input())):\n\t(a, b) = list(map(int, input().split()))\n\tprint(sum((1 if f(i, a - 1) == f(i, b - 1) else 0 for i in range(m))))\n", "from collections import defaultdict\n\ndef DFS(d, a, visited):\n\tvisited[a] = 1\n\tif a in d:\n\t\tfor i in d[a]:\n\t\t\tif visited[i] == 1:\n\t\t\t\tcontinue\n\t\t\telse:\n\t\t\t\tDFS(d, i, visited)\n(n, m) = map(int, input().split())\nl = [defaultdict(list) for i in range(m + 1)]\nfor i in range(m):\n\t(a, b, c) = map(int, input().split())\n\tl[c][a].append(b)\n\tl[c][b].append(a)\nq = int(input())\nfor i in range(q):\n\t(a, b) = map(int, input().split())\n\tr = 0\n\tfor j in l:\n\t\tvisited = [0 for i in range(n + 1)]\n\t\tDFS(j, a, visited)\n\t\tif visited[a] == 1 and visited[b] == 1:\n\t\t\tr = r + 1\n\tprint(r)\n", "def main():\n\t(n, m) = map(int, input().split())\n\tedges = {_: {} for _ in range(1, m + 1)}\n\tfor _ in range(m):\n\t\t(a, b, c) = map(int, input().split())\n\t\td = edges[c]\n\t\tl = d.get(a)\n\t\tif l:\n\t\t\tl.append(b)\n\t\telse:\n\t\t\td[a] = [b]\n\t\tl = d.get(b)\n\t\tif l:\n\t\t\tl.append(a)\n\t\telse:\n\t\t\td[b] = [a]\n\n\tdef dfs(t):\n\t\tunused[t] = False\n\t\tfor y in dcolor.get(t, ()):\n\t\t\tif unused[y]:\n\t\t\t\tdfs(y)\n\tres = []\n\tn += 1\n\tunused = [True] * n\n\tfor _ in range(int(input())):\n\t\t(a, b) = map(int, input().split())\n\t\tx = 0\n\t\tfor dcolor in edges.values():\n\t\t\tfor j in range(n):\n\t\t\t\tunused[j] = True\n\t\t\tdfs(a)\n\t\t\tif not unused[b]:\n\t\t\t\tx += 1\n\t\tres.append(str(x))\n\tprint('\\n'.join(res))\nmain()\n", "def arr_inp(n):\n\tif n == 1:\n\t\treturn [int(x) for x in stdin.readline().split()]\n\telif n == 2:\n\t\treturn [float(x) for x in stdin.readline().split()]\n\telse:\n\t\treturn [str(x) for x in stdin.readline().split()]\n\nclass disjointset:\n\n\tdef __init__(self, n):\n\t\t(self.rank, self.parent, self.n, self.nsets, self.edges) = (defaultdict(int), defaultdict(int), n, defaultdict(int), defaultdict(int))\n\t\tfor i in range(1, n + 1):\n\t\t\t(self.parent[i], self.nsets[i]) = (i, 1)\n\n\tdef find(self, x):\n\t\tif self.parent[x] == x:\n\t\t\treturn x\n\t\tresult = self.find(self.parent[x])\n\t\tself.parent[x] = result\n\t\treturn result\n\n\tdef union(self, x, y):\n\t\t(xpar, ypar) = (self.find(x), self.find(y))\n\t\tif xpar == ypar:\n\t\t\tself.edges[xpar] += 1\n\t\t\treturn\n\t\tif self.rank[xpar] < self.rank[ypar]:\n\t\t\tself.parent[xpar] = ypar\n\t\t\tself.edges[ypar] += self.edges[xpar] + 1\n\t\t\tself.nsets[ypar] += self.nsets[xpar]\n\t\telif self.rank[xpar] > self.rank[ypar]:\n\t\t\tself.parent[ypar] = xpar\n\t\t\tself.edges[xpar] += self.edges[ypar] + 1\n\t\t\tself.nsets[xpar] += self.nsets[ypar]\n\t\telse:\n\t\t\tself.parent[ypar] = xpar\n\t\t\tself.rank[xpar] += 1\n\t\t\tself.edges[xpar] += self.edges[ypar] + 1\n\t\t\tself.nsets[xpar] += self.nsets[ypar]\nfrom sys import stdin\nfrom collections import defaultdict\n(n, m) = arr_inp(1)\ncolor = [disjointset(n) for i in range(m)]\nfor i in range(m):\n\t(a, b, c) = arr_inp(1)\n\tcolor[c - 1].union(a, b)\nfor i in range(int(input())):\n\t(u, v) = arr_inp(1)\n\tans = 0\n\tfor j in range(m):\n\t\tif color[j].find(u) == color[j].find(v):\n\t\t\tans += 1\n\tprint(ans)\n", "import sys, os.path\nfrom collections import *\nfrom copy import *\nimport math\nmod = 10 ** 9 + 7\nif os.path.exists('input.txt'):\n\tsys.stdin = open('input.txt', 'r')\n\tsys.stdout = open('output.txt', 'w')\n\ndef dfs(x, y, z):\n\tvis[x] = 1\n\tif x == y:\n\t\treturn\n\tfor v in adj[x]:\n\t\tif vis[v[0]]:\n\t\t\tcontinue\n\t\tif v[1] == z:\n\t\t\tdfs(v[0], y, z)\nadj = defaultdict(list)\n(n, m) = map(int, input().split())\ns = set()\nfor i in range(m):\n\t(a, b, c) = map(int, input().split())\n\tadj[a].append((b, c))\n\tadj[b].append((a, c))\n\ts.add(c)\nq = int(input())\nfor i in range(q):\n\t(x, y) = map(int, input().split())\n\tcount = 0\n\tfor j in s:\n\t\tvis = [0 for i in range(n + 1)]\n\t\tdfs(x, y, j)\n\t\tif vis[y]:\n\t\t\tcount += 1\n\tprint(count)\n", "def build_graph():\n\tline1 = input().strip().split()\n\tn = int(line1[0])\n\tm = int(line1[1])\n\tgraph = {}\n\tfor _ in range(m):\n\t\tline = input().strip().split()\n\t\tu = int(line[0])\n\t\tv = int(line[1])\n\t\tc = int(line[2])\n\t\tif c not in graph:\n\t\t\tgraph[c] = {j: [] for j in range(1, n + 1)}\n\t\tgraph[c][u].append(v)\n\t\tgraph[c][v].append(u)\n\treturn graph\nparent_history = {}\n\ndef no_of_paths(u, v, graph):\n\tx = 0\n\tfor c in graph:\n\t\tif c in parent_history and v in parent_history[c]:\n\t\t\tparent = parent_history[c]\n\t\telse:\n\t\t\tparent = {}\n\t\t\tparent = dfs_visit(v, graph[c], parent)\n\t\t\tparent_history[c] = parent\n\t\tif u in parent:\n\t\t\tx += 1\n\treturn x\n\ndef dfs_visit(i, adj_list, parent):\n\tfor j in adj_list[i]:\n\t\tif j not in parent:\n\t\t\tparent[j] = i\n\t\t\tdfs_visit(j, adj_list, parent)\n\treturn parent\ngraph = build_graph()\nfor _ in range(int(input())):\n\tline = input().strip().split()\n\tprint(no_of_paths(int(line[0]), int(line[1]), graph))\n", "from collections import defaultdict\n\ndef dfs(graph, start, end, visited, color):\n\tq = [start]\n\twhile q:\n\t\tnode = q.pop()\n\t\tvisited[node] = True\n\t\tif node == end:\n\t\t\tbreak\n\t\tfor v in graph[color][node]:\n\t\t\tif not visited[v]:\n\t\t\t\tq.append(v)\n\ndef has_path(graph, start, end, visited, color):\n\tfor i in range(len(visited)):\n\t\tvisited[i] = False\n\tdfs(graph, start, end, visited, color)\n\treturn visited[end]\n(n, m) = map(int, input().split())\ngraph = defaultdict(lambda : defaultdict(list))\nfor _ in range(m):\n\t(a, b, c) = map(int, input().split())\n\ta -= 1\n\tb -= 1\n\tgraph[c][a].append(b)\n\tgraph[c][b].append(a)\nvisited = [False] * n\nq = int(input())\nfor _ in range(q):\n\t(u, v) = map(int, input().split())\n\tu -= 1\n\tv -= 1\n\tans = 0\n\tfor c in graph.keys():\n\t\tif has_path(graph, u, v, visited, c):\n\t\t\tans += 1\n\tprint(ans)\n", "from collections import defaultdict\n(n, m) = map(int, input().split())\nd = [defaultdict(list) for i in range(1 + m)]\nfor i in range(m):\n\t(a, b, c) = map(int, input().split())\n\td[c][a].append(b)\n\td[c][b].append(a)\nq = int(input())\nfor _ in range(q):\n\t(u, v) = map(int, input().split())\n\tct = 0\n\tfor adj in d:\n\t\tvst = [0] * (n + 1)\n\t\tq = [u]\n\t\twhile q:\n\t\t\te = q.pop()\n\t\t\tif e == v:\n\t\t\t\tct += 1\n\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\tvst[e] = 1\n\t\t\t\tfor j in adj[e]:\n\t\t\t\t\tif not vst[j]:\n\t\t\t\t\t\tq.append(j)\n\tprint(ct)\n", "def dfs(x, y, color):\n\tvisited = [False for i in range(n + 1)]\n\tvisited[x] = True\n\tstack = [x]\n\twhile stack:\n\t\tnode = stack.pop()\n\t\tfor (child, childcolor) in g[node]:\n\t\t\tif visited[child] == False and childcolor == color:\n\t\t\t\tvisited[child] = True\n\t\t\t\tstack.append(child)\n\tif visited[y] == True:\n\t\treturn True\n\treturn False\n(n, m) = map(int, input().split())\ng = {i: [] for i in range(1, n + 1)}\ns = set()\nfor i in range(m):\n\t(u, v, c) = map(int, input().split())\n\ts.add(c)\n\tg[u].append([v, c])\n\tg[v].append([u, c])\ns = list(s)\nans = [[0 for i in range(n + 1)] for j in range(n + 1)]\nfor i in range(1, n + 1):\n\tfor j in range(1, n + 1):\n\t\tfor c in s:\n\t\t\tif i != j:\n\t\t\t\tif dfs(i, j, c):\n\t\t\t\t\tans[i][j] += 1\nq = int(input())\nfor i in range(q):\n\t(u, v) = map(int, input().split())\n\tprint(ans[u][v])\n", "from collections import defaultdict\nfrom sys import stdin, stdout\npar = defaultdict(list)\n\ndef build(n):\n\tglobal par, size\n\tfor c in range(101):\n\t\tpar[c] = []\n\t\tfor i in range(n):\n\t\t\tpar[c].append(i)\n\treturn par\n\ndef find(c, i):\n\tglobal par\n\tif par[c][i] == i:\n\t\treturn i\n\tpar[c][i] = find(c, par[c][i])\n\treturn par[c][i]\n\ndef union(a, b, c):\n\tglobal par, scc, size\n\tp = find(c, a)\n\tq = find(c, b)\n\tif p == q:\n\t\treturn\n\tpar[c][q] = par[c][p]\n\ndef main():\n\t(n, m) = map(int, stdin.readline().strip().split(' '))\n\tpar = build(n)\n\tmax_c = 0\n\tfor i in range(m):\n\t\t(a, b, c) = map(lambda i: int(i) - 1, stdin.readline().strip().split(' '))\n\t\tunion(a, b, c)\n\t\tmax_c = max(max_c, c)\n\tq = int(stdin.readline().strip())\n\tfor i in range(q):\n\t\t(a, b) = map(lambda i: int(i) - 1, stdin.readline().strip().split(' '))\n\t\tcount = 0\n\t\tfor c in range(max_c + 1):\n\t\t\tp = find(c, a)\n\t\t\tq = find(c, b)\n\t\t\tif p == q:\n\t\t\t\tcount += 1\n\t\tstdout.write('{}\\n'.format(count))\nmain()\n", "from collections import defaultdict\n\ndef dfs(node, b, graph, colour, vis):\n\tif node == b:\n\t\treturn True\n\tvis[node] = True\n\tfor i in graph[node]:\n\t\tif not vis[i[0]]:\n\t\t\tif i[1] == colour:\n\t\t\t\tif dfs(i[0], b, graph, i[1], vis):\n\t\t\t\t\treturn True\n\treturn False\n(n, m) = map(int, input().split())\ngraph = defaultdict(list)\nfor i in range(m):\n\t(a, b, c) = map(int, input().split())\n\tgraph[a].append([b, c])\n\tgraph[b].append([a, c])\nq = int(input())\nvisited = [False] * (n + 1)\nfor i in range(q):\n\t(a, b) = map(int, input().split())\n\tans = 0\n\tfor i in range(101):\n\t\tvis = visited[:]\n\t\tif dfs(a, b, graph, i, vis):\n\t\t\tans += 1\n\tprint(ans)\n", "class Node:\n\n\tdef __init__(self, n):\n\t\tself.n = n\n\t\tself.neighs = {}\n\n\tdef dfs_color(self, f, t, nodes, visited):\n\t\tvisited.add(self.n)\n\t\tconnected = set()\n\t\tfor (neigh, colors_to_neigh) in self.neighs.items():\n\t\t\tif neigh == f or neigh in visited:\n\t\t\t\tcontinue\n\t\t\tcolors = colors_to_neigh if neigh == t else nodes[neigh].dfs_color(self.n, t, nodes, visited)\n\t\t\tconnected.update(colors.intersection(colors_to_neigh))\n\t\tvisited.remove(self.n)\n\t\treturn connected\n\n\tdef dfs_colored_path(self, cc, nodes, visited):\n\t\tvisited.add(self.n)\n\t\tfor (neigh, colors_to_neigh) in self.neighs.items():\n\t\t\tif neigh in visited or cc not in colors_to_neigh:\n\t\t\t\tcontinue\n\t\t\tnodes[neigh].dfs_colored_path(cc, nodes, visited)\n\t\treturn visited\n\n\tdef search_with_color(self, t, nodes):\n\t\tcolors_to_explore = set()\n\t\tcolors = set()\n\t\tfor (neigh, colors_to_neigh) in self.neighs.items():\n\t\t\tcolors_to_explore.update(colors_to_neigh)\n\t\tfor color in colors_to_explore:\n\t\t\tcities = self.dfs_colored_path(color, nodes, set())\n\t\t\tif t in cities:\n\t\t\t\tcolors.add(color)\n\t\treturn len(colors)\n(n, m) = [int(n) for n in input().split()]\nedges = []\nwhile m:\n\tedge = [int(n) for n in input().split()]\n\tedges.append(edge)\n\tm -= 1\nnodes = [Node(i) for i in range(n + 1)]\nfor (f, t, c) in edges:\n\tif t not in nodes[f].neighs:\n\t\tnodes[f].neighs[t] = set()\n\tnodes[f].neighs[t].add(c)\n\t(f, t) = (t, f)\n\tif t not in nodes[f].neighs:\n\t\tnodes[f].neighs[t] = set()\n\tnodes[f].neighs[t].add(c)\nqs = int(input())\nfor q in range(qs):\n\t(f, t) = [int(n) for n in input().split()]\n\tprint(nodes[f].search_with_color(t, nodes))\n", "import math, sys\nfrom collections import defaultdict, deque\nimport bisect as bi\n\ndef yes():\n\tprint('YES')\n\ndef no():\n\tprint('NO')\n\ndef I():\n\treturn int(sys.stdin.readline())\n\ndef In():\n\treturn map(int, sys.stdin.readline().split())\n\ndef Sn():\n\treturn sys.stdin.readline().strip()\n\ndef dict(a):\n\td = {}\n\tfor x in a:\n\t\tif d.get(x, -1) != -1:\n\t\t\td[x] += 1\n\t\telse:\n\t\t\td[x] = 1\n\treturn d\n\ndef find_gt(a, x):\n\ti = bi.bisect_left(a, x)\n\tif i != len(a):\n\t\treturn i\n\telse:\n\t\treturn -1\n\ndef dfs(gp, st, end, v, x):\n\tq = deque([st])\n\twhile q:\n\t\tnode = q.pop()\n\t\tv[node] = 1\n\t\tfor i in gp[node]:\n\t\t\tif not v[i[0]] and i[1] == x:\n\t\t\t\tq.appendleft(i[0])\n\treturn v[end]\n\ndef main():\n\ttry:\n\t\t(n, m) = In()\n\t\tgp = defaultdict(list)\n\t\td = defaultdict(set)\n\t\tfor x in range(m):\n\t\t\t(a, b, c) = In()\n\t\t\tgp[a].append((b, c))\n\t\t\tgp[b].append((a, c))\n\t\t\td[a].add(c)\n\t\t\td[b].add(c)\n\t\tfor i in range(I()):\n\t\t\t(st, end) = In()\n\t\t\tcnt = 0\n\t\t\tfor x in d[st]:\n\t\t\t\tv = [0] * (n + 1)\n\t\t\t\tif dfs(gp, st, end, v, x):\n\t\t\t\t\tcnt += 1\n\t\t\tprint(cnt)\n\texcept:\n\t\tpass\nM = 998244353\nP = 1000000007\nfor _ in range(1):\n\tmain()\n", "import sys, os, io\nimport math, bisect, operator\n(inf, mod) = (float('inf'), 10 ** 9 + 7)\nfrom itertools import groupby, accumulate\nfrom heapq import heapify, heappop, heappush\nfrom collections import deque, Counter, defaultdict\nI = lambda : int(sys.stdin.buffer.readline())\nNeo = lambda : list(map(int, sys.stdin.buffer.readline().split()))\n(n, m) = Neo()\nColor = defaultdict(set)\nG = defaultdict(set)\nC = set()\n\ndef addEdge(a, b):\n\tG[a].add(b)\n\tG[b].add(a)\n\ndef addColor(a, b, c):\n\tColor[a, b].add(c)\n\tColor[b, a].add(c)\n\tC.add(c)\nfor i in range(m):\n\t(a, b, c) = Neo()\n\taddColor(a, b, c)\n\taddEdge(a, b)\nvis = [False] * (n + 1)\nAns = []\n\ndef fun(node, dest, vis, grp):\n\tif not grp:\n\t\treturn\n\tif node == dest:\n\t\tfor i in grp:\n\t\t\tAns.append(i)\n\t\treturn\n\tvis[node] = True\n\tfor i in G.get(node, []):\n\t\tif not vis[i]:\n\t\t\tnewvis = vis.copy()\n\t\t\tz = grp.intersection(Color[node, i])\n\t\t\tfun(i, dest, newvis, z)\nfor i in range(I()):\n\t(a, b) = Neo()\n\tvis = [False] * (n + 1)\n\tgrp = C.copy()\n\tfun(a, b, vis, grp)\n\tprint(len(set(Ans)))\n\tAns = []\n", "import queue\n(n, m) = map(int, input().strip().split())\nadj = [[] for i in range(n + 1)]\n\ndef doable(s, t, c):\n\tglobal adj, n, m\n\tq = queue.Queue()\n\tvisited = [False for i in range(n + 1)]\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tu = q.get()\n\t\tfor v in adj[u]:\n\t\t\tif v[1] == c and (not visited[v[0]]):\n\t\t\t\tq.put(v[0])\n\t\t\t\tvisited[v[0]] = True\n\treturn visited[t]\nmaxc = 0\nfor _ in range(m):\n\t(u, v, c) = map(int, input().strip().split())\n\tadj[u].append((v, c))\n\tadj[v].append((u, c))\n\tmaxc = max(maxc, c)\nq = int(input())\nfor _ in range(q):\n\t(u, v) = map(int, input().strip().split())\n\tans = 0\n\tfor color in range(1, maxc + 1):\n\t\tif doable(u, v, color):\n\t\t\tans += 1\n\tprint(ans)\n", "def get_connected_matrix(adjacency_matrix):\n\tn = len(adjacency_matrix)\n\tnon_visited_vertices = set((i for i in range(n)))\n\tcluster_numbers = [0] * n\n\tcluster_number = 1\n\n\tdef traverse(u):\n\t\tnon_visited_vertices.remove(u)\n\t\tcluster_numbers[u] = cluster_number\n\t\tfor v in range(n):\n\t\t\tif v in non_visited_vertices:\n\t\t\t\tif adjacency_matrix[u][v]:\n\t\t\t\t\ttraverse(v)\n\twhile non_visited_vertices:\n\t\tvertex = non_visited_vertices.pop()\n\t\tnon_visited_vertices.add(vertex)\n\t\ttraverse(vertex)\n\t\tcluster_number += 1\n\tconnected_matrix = [[False] * n for _ in range(n)]\n\tfor u in range(n):\n\t\tfor v in range(n):\n\t\t\tif u == v:\n\t\t\t\tcontinue\n\t\t\tconnected_matrix[u][v] = connected_matrix[v][u] = cluster_numbers[u] == cluster_numbers[v]\n\treturn connected_matrix\n\ndef main():\n\t(n, m) = [int(t) for t in input().split()]\n\tmatrices = [[[False] * n for _ in range(n)] for _ in range(m)]\n\tfor _ in range(m):\n\t\t(a, b, c) = [int(t) - 1 for t in input().split()]\n\t\tmatrices[c][a][b] = True\n\t\tmatrices[c][b][a] = True\n\tconnected_matrices = [get_connected_matrix(matrix) for matrix in matrices]\n\tq = int(input())\n\tfor _ in range(q):\n\t\t(u, v) = [int(t) - 1 for t in input().split()]\n\t\ttotal_connection = sum((1 for connected_matrix in connected_matrices if connected_matrix[u][v]))\n\t\tprint(total_connection)\nmain()\n", "(n, m) = map(int, input().strip().split())\ngr = [[[] for i in range(n)] for i in range(m)]\nfor i in range(m):\n\t(a, b, c) = map(int, input().strip().split())\n\tgr[c - 1][a - 1].append(b)\n\tgr[c - 1][b - 1].append(a)\nq = int(input())\nfor j in range(q):\n\t(x, y) = map(int, input().strip().split())\n\tans = 0\n\tfor i in range(m):\n\t\tst = [x]\n\t\tpar = {x: 1}\n\t\tflag = 0\n\t\twhile st:\n\t\t\tu = st.pop()\n\t\t\tif u == y:\n\t\t\t\tflag = 1\n\t\t\t\tbreak\n\t\t\tfor v in gr[i][u - 1]:\n\t\t\t\tif v not in par:\n\t\t\t\t\tst.append(v)\n\t\t\t\t\tpar[v] = 1\n\t\tif flag == 1:\n\t\t\tans += 1\n\tprint(ans)\n", "def main():\n\n\tdef dfs(index, color):\n\t\tvisited[index] = True\n\t\tfor p in adj[index]:\n\t\t\tif not visited[p[0]] and p[1] == color:\n\t\t\t\tdfs(p[0], color)\n\t(n, m) = map(int, input().split())\n\tadj = [[] for _ in range(n)]\n\tfor _ in range(m):\n\t\t(a, b, c) = map(int, input().split())\n\t\tadj[a - 1].append((b - 1, c))\n\t\tadj[b - 1].append((a - 1, c))\n\tq = int(input())\n\tfor _ in range(q):\n\t\t(a, b) = map(int, input().split())\n\t\tans = 0\n\t\tfor i in range(1, m + 1):\n\t\t\tvisited = [False] * n\n\t\t\tdfs(a - 1, i)\n\t\t\tif visited[b - 1]:\n\t\t\t\tans += 1\n\t\tprint(ans)\nmain()\n", "def verify(node, x, color):\n\tvisited[node] = True\n\tif node == x:\n\t\treturn True\n\tfor (i, c) in graph[node]:\n\t\tif c == color and (not visited[i]):\n\t\t\tif verify(i, x, color):\n\t\t\t\treturn True\n\treturn False\n(n, m) = map(int, input().split())\ngraph = [[] for i in range(n + 1)]\nfor i in range(m):\n\t(a, b, c) = map(int, input().split())\n\tgraph[a].append((b, c))\n\tgraph[b].append((a, c))\nfor i in range(int(input())):\n\t(u, v) = map(int, input().split())\n\tcont = 0\n\tfor j in range(1, 101):\n\t\tvisited = [0] * (n + 1)\n\t\tif verify(u, v, j):\n\t\t\tcont += 1\n\tprint(cont)\n", "(n, m) = [int(x) for x in input().split()]\nedge = {}\nfor i in range(1, n + 1):\n\tedge[i] = {}\n\tfor j in range(1, m + 1):\n\t\tedge[i][j] = []\nfor i in range(m):\n\t(a, b, c) = [int(x) for x in input().split()]\n\tedge[a][c].append(b)\n\tedge[b][c].append(a)\nq = int(input())\nfor i in range(q):\n\t(u, v) = [int(x) for x in input().split()]\n\tcount = 0\n\tfor key in edge[u]:\n\t\tlevel = {u: 0}\n\t\tfrontier = [u]\n\t\tfound = False\n\t\twhile frontier and (not found):\n\t\t\tnext = []\n\t\t\tfor uu in frontier:\n\t\t\t\tfor vv in edge[uu][key]:\n\t\t\t\t\tif not vv in level:\n\t\t\t\t\t\tif vv == v:\n\t\t\t\t\t\t\tfound = True\n\t\t\t\t\t\tlevel[vv] = 0\n\t\t\t\t\t\tnext.append(vv)\n\t\t\tfrontier = next\n\t\tif found:\n\t\t\tcount += 1\n\tprint(count)\n", "from collections import defaultdict, deque, Counter, OrderedDict\n\ndef main():\n\tN = 105\n\t(n, m) = map(int, input().split())\n\tpar = [[j for j in range(N)] for i in range(N)]\n\n\tdef find(a, c):\n\t\tif par[c][a] == a:\n\t\t\treturn a\n\t\tpar[c][a] = find(par[c][a], c)\n\t\treturn par[c][a]\n\n\tdef merge(a, b, c):\n\t\ta = find(a, c)\n\t\tb = find(b, c)\n\t\tpar[c][b] = a\n\tfor i in range(m):\n\t\t(a, b, c) = map(int, input().split())\n\t\t(a, b) = (a - 1, b - 1)\n\t\tmerge(a, b, c)\n\tq = int(input())\n\tfor i in range(q):\n\t\t(a, b) = map(int, input().split())\n\t\t(a, b, ans) = (a - 1, b - 1, 0)\n\t\tfor i in range(N):\n\t\t\tif find(a, i) == find(b, i):\n\t\t\t\tans += 1\n\t\tprint(ans)\nmain()\n", "(n, m) = list(map(int, input().split()))\nl = []\nfor i in range(m):\n\tl.append(list(range(n)))\nfor i in range(m):\n\tx = list(map(int, input().split()))\n\tl2 = l[x[2] - 1]\n\tg = max(l2[x[0] - 1], l2[x[1] - 1])\n\th = min(l2[x[0] - 1], l2[x[1] - 1])\n\tfor j in range(len(l2)):\n\t\tif l2[j] == g:\n\t\t\tl2[j] = h\n\t\tl[x[2] - 1] = l2\nz = int(input())\nl3 = []\nfor i in range(z):\n\ts = 0\n\t(a, b) = list(map(int, input().split()))\n\tfor n in l:\n\t\tif n[a - 1] == n[b - 1]:\n\t\t\ts += 1\n\tl3.append(s)\nfor i in l3:\n\tprint(i)\n", "from collections import defaultdict, deque\n\ndef dfs(node, c):\n\tif not visited[node]:\n\t\tvisited[node] = True\n\t\tfor j in g[node]:\n\t\t\tif not visited[j[0]] and j[1] == c:\n\t\t\t\tdfs(j[0], j[1])\n(n, m) = map(int, input().split())\ng = defaultdict(list)\nfor i in range(m):\n\t(u, v, c) = map(int, input().split())\n\tg[u].append([v, c])\n\tg[v].append([u, c])\nq = int(input())\nans = deque()\nfor k in range(q):\n\t(x, y) = map(int, input().split())\n\tcnt = 0\n\tfor j in range(1, m + 1):\n\t\tvisited = [False] * (n + 1)\n\t\tdfs(x, j)\n\t\tif visited[y] == True:\n\t\t\tcnt += 1\n\tans.append(cnt)\nfor j in ans:\n\tprint(j)\n", "from collections import defaultdict\n\ndef connectedComponents(root, visited, graph, c, comp):\n\tvisited[root] = 1\n\tcomp[root] = c\n\tfor i in graph[root]:\n\t\tif visited[i] == 0:\n\t\t\tconnectedComponents(i, visited, graph, c, comp)\n\treturn\n(n, m) = map(int, input().split())\ngraphs = [defaultdict(list) for i in range(m + 1)]\nvert = defaultdict(set)\nfor _ in range(m):\n\t(u, v, c) = map(int, input().split())\n\tgraphs[c][u].append(v)\n\tgraphs[c][v].append(u)\n\tvert[c].add(v)\n\tvert[c].add(u)\ncomponents = [[0 for i in range(n + 1)] for i in range(m + 1)]\nfor i in range(1, m + 1):\n\tc = 0\n\tvisited = [0 for i in range(n + 1)]\n\tfor r in graphs[i].keys():\n\t\tif visited[r] == 0:\n\t\t\tc += 1\n\t\t\tconnectedComponents(r, visited, graphs[i], c, components[i])\nq = int(input())\nfor i in range(q):\n\t(u, v) = map(int, input().split())\n\tans = 0\n\tfor j in range(1, m + 1):\n\t\tif components[j][u] == components[j][v] and components[j][u] != 0:\n\t\t\tans += 1\n\tprint(ans)\n", "entrada = list(map(int, input().split()))\na = [[] for x in range(entrada[0] + 1)]\nfor i in range(entrada[1]):\n\tentrada2 = list(map(int, input().split()))\n\tcont1 = entrada2[0]\n\tcont2 = entrada2[1]\n\tcont3 = entrada2[2]\n\ta[cont1].append((cont2, cont3))\n\ta[cont2].append((cont1, cont3))\n\ndef defans(cont1, cont2, cont3):\n\tb[cont1] = True\n\tif cont1 == cont2:\n\t\treturn 1\n\tfor (i, j) in a[cont1]:\n\t\tif j == cont3:\n\t\t\tif b[i] == False:\n\t\t\t\tif defans(i, cont2, cont3):\n\t\t\t\t\treturn 1\n\treturn 0\nq = int(input())\nk = 0\nfor i in range(q):\n\tentrada3 = list(map(int, input().split()))\n\tsoma = 0\n\tfor k in range(100):\n\t\tb = [0] * (entrada[0] + 1)\n\t\tsoma += defans(entrada3[0], entrada3[1], k + 1)\n\t\tk += 1\n\tprint(soma)\n", "from collections import defaultdict\n\ndef dfs(adjlist, start, visited, nodes, color):\n\tif start in visited:\n\t\treturn\n\tvisited.add(start)\n\tfor (v, c) in adjlist[start]:\n\t\tif c == color:\n\t\t\tnodes[v - 1] = nodes[start - 1]\n\t\t\tdfs(adjlist, v, visited, nodes, color)\n(n, m) = map(int, input().split())\nadjlist = defaultdict(list)\nall_color = set()\nfor i in range(0, m):\n\ttmp = list(map(int, input().split()))\n\tadjlist[tmp[0]].append((tmp[1], tmp[2]))\n\tadjlist[tmp[1]].append((tmp[0], tmp[2]))\n\tall_color.add(tmp[2])\nnum_queries = int(input())\nqueries = []\nfor i in range(0, num_queries):\n\tqueries.append(list(map(int, input().split())))\ncolor_map = {}\nfor c in all_color:\n\tnodes = [i for i in range(1, n + 1)]\n\tfor src in range(1, n + 1):\n\t\tvisited = set()\n\t\tdfs(adjlist, src, visited, nodes, c)\n\t\tif len(visited) == n:\n\t\t\tbreak\n\tcolor_map[c] = nodes\nfor q in queries:\n\tcount = 0\n\tfor c in color_map.keys():\n\t\tif color_map[c][q[0] - 1] == color_map[c][q[1] - 1]:\n\t\t\tcount += 1\n\tprint(count)\n", "(n, m) = input().split(' ')\nl = []\nfor x in range(int(m)):\n\tl.append(list(range(int(n))))\nfor x in range(int(m)):\n\tp = input().split(' ')\n\tnewl = l[int(p[2]) - 1]\n\t(a, i) = (max(newl[int(p[0]) - 1], newl[int(p[1]) - 1]), min(newl[int(p[0]) - 1], newl[int(p[1]) - 1]))\n\tfor y in range(len(newl)):\n\t\tif newl[y] == a:\n\t\t\tnewl[y] = i\n\tl[int(p[2]) - 1] = newl\nq = int(input())\nput = []\nfor x in range(q):\n\tout = 0\n\t(a, b) = input().split(' ')\n\tfor n in l:\n\t\tif n[int(a) - 1] == n[int(b) - 1]:\n\t\t\tout += 1\n\tput.append(out)\nfor x in put:\n\tprint(x)\n", "def gerarGrafo(cor):\n\tadjancencias = {}\n\tfor aresta in arestas:\n\t\tif aresta[2] == cor:\n\t\t\tif adjancencias.get(aresta[0]) == None:\n\t\t\t\tadjancencias[aresta[0]] = []\n\t\t\tif adjancencias.get(aresta[1]) == None:\n\t\t\t\tadjancencias[aresta[1]] = []\n\t\t\tadjancencias[aresta[0]].append(aresta[1])\n\t\t\tadjancencias[aresta[1]].append(aresta[0])\n\treturn adjancencias\n\ndef dfs(u, w, adjacencias):\n\tpilha = [u]\n\tvisitados = {u: 1}\n\texisteCaminhoUV = False\n\tif adjacencias.get(u) == None or adjacencias.get(w) == None:\n\t\treturn existeCaminhoUV\n\twhile len(pilha) > 0:\n\t\tvertice = pilha.pop()\n\t\tfor v in adjacencias[vertice]:\n\t\t\tif visitados.get(v) == None:\n\t\t\t\tvisitados[v] = 1\n\t\t\t\tpilha.append(v)\n\tif visitados.get(w) != None:\n\t\texisteCaminhoUV = True\n\treturn existeCaminhoUV\nentrada = input().split()\nn = int(entrada[0])\nm = int(entrada[1])\ncores = set()\narestas = []\ni = 0\nwhile i < m:\n\taresta = input().split()\n\tcores.add(aresta[2])\n\tarestas.append(aresta)\n\ti += 1\nq = int(input())\nparesVertices = []\ni = 0\nwhile i < q:\n\tparesVertices.append(input().split())\n\ti += 1\nres = [0] * q\nfor cor in cores:\n\tgrafo = gerarGrafo(cor)\n\ti = 0\n\tfor par in paresVertices:\n\t\tif dfs(par[0], par[1], grafo):\n\t\t\tres[i] += 1\n\t\ti += 1\nfor e in res:\n\tprint(e)\n", "def dfs(p, f, gr, used):\n\tif p == f:\n\t\treturn 1\n\tif used[p]:\n\t\treturn 0\n\tused[p] = 1\n\tfor v in gr[p]:\n\t\tif dfs(v, f, gr, used):\n\t\t\treturn 1\n\treturn 0\n\ndef check(gr, u, v):\n\tused = [0] * len(gr)\n\treturn dfs(u, v, gr, used)\n(n, m) = (int(x) for x in input().split())\ncgr = [[[] for j in range(n)] for _ in range(m)]\nfor i in range(m):\n\t(a, b, c) = (int(x) for x in input().split())\n\tc -= 1\n\ta -= 1\n\tb -= 1\n\tcgr[c][a].append(b)\n\tcgr[c][b].append(a)\nq = int(input())\nfor i in range(q):\n\t(u, v) = (int(x) for x in input().split())\n\tans = 0\n\tfor gr in cgr:\n\t\tans += check(gr, u - 1, v - 1)\n\tprint(ans)\n", "(n, m) = map(int, input().split())\n(e, g) = ({}, {x: set() for x in range(1, n + 1)})\nfor i in range(m):\n\t(a, b, c) = map(int, input().split())\n\te[a, b] = e[b, a] = e.get((a, b), set()) | {c}\n\tg[a].add(b)\n\tg[b].add(a)\nfor _ in range(int(input())):\n\t(a, b) = map(int, input().split())\n\tans = 0\n\tfor color in range(1, m + 1):\n\t\tvis = [0] * (n + 1)\n\t\tq = [a]\n\t\twhile q:\n\t\t\tv = q.pop()\n\t\t\tif v == b:\n\t\t\t\tans += 1\n\t\t\t\tbreak\n\t\t\tvis[v] = 1\n\t\t\tfor i in g[v]:\n\t\t\t\tif not vis[i] and color in e[v, i]:\n\t\t\t\t\tq.append(i)\n\tprint(ans)\n", "(n, m) = map(int, input().split())\ngraph = [[[-1] for x in range(n + 1)] for i in range(n + 1)]\nfor _ in range(m):\n\t(a, b, c) = map(int, input().split())\n\tif graph[a][b] != [-1]:\n\t\tgraph[a][b].append(c)\n\telse:\n\t\tgraph[a][b] = [c]\n\ndef bfs(start, end, color):\n\t(neighbors, visited) = ([start], set())\n\twhile neighbors:\n\t\t(current, neighbors) = (neighbors, [])\n\t\tfor each in current:\n\t\t\tfor i in range(1, n + 1):\n\t\t\t\tif (color in graph[i][each] or color in graph[each][i]) and i not in visited:\n\t\t\t\t\tvisited.add(i)\n\t\t\t\t\tif i == end:\n\t\t\t\t\t\treturn True\n\t\t\t\t\tneighbors.append(i)\n\treturn False\nq = int(input())\nfor _ in range(q):\n\t(u, v) = map(int, input().split())\n\t(starting_colors, colors) = (set(), 0)\n\tfor i in range(1, n + 1):\n\t\tif graph[i][u] != [-1]:\n\t\t\tstarting_colors.update(graph[i][u])\n\t\telif graph[u][i] != [-1]:\n\t\t\tstarting_colors.update(graph[u][i])\n\tfor each_color in starting_colors:\n\t\tif bfs(u, v, each_color):\n\t\t\tcolors += 1\n\tprint(colors)\n", "(n, m) = list(map(int, input().split()))\nvalor = n + 1\narr = [[] for x in range(valor)]\nfor i in range(m):\n\t(val1, val2, val3) = map(int, input().split())\n\tarr[val1].append((val2, val3))\n\tarr[val2].append((val1, val3))\nq = int(input())\n\ndef contador(val1, val2, val3):\n\tarr2[val1] = True\n\tif val1 == val2:\n\t\treturn 1\n\tfor (i, j) in arr[val1]:\n\t\tif j == val3:\n\t\t\tif arr2[i] == False:\n\t\t\t\tif contador(i, val2, val3):\n\t\t\t\t\treturn 1\n\treturn 0\nfor i in range(q):\n\t(u, v) = list(map(int, input().split()))\n\tcont = 0\n\tfor j in range(100):\n\t\tarr2 = [0] * (n + 1)\n\t\tcont += contador(u, v, j + 1)\n\tprint(cont)\n", "f = lambda : map(int, input().split())\n(n, m) = f()\np = [list(range(n + 1)) for x in range(m + 1)]\n\ndef g(c, x):\n\tif x != p[c][x]:\n\t\tp[c][x] = g(c, p[c][x])\n\treturn p[c][x]\nfor i in range(m):\n\t(a, b, c) = f()\n\tp[c][g(c, a)] = g(c, b)\nfor j in range(int(input())):\n\t(a, b) = f()\n\tprint(sum((g(i, a) == g(i, b) for i in range(m + 1))))\n", "def dfs(place, target):\n\tvis[place] = True\n\tif target == place:\n\t\ttotal[0] += 1\n\t\treturn ()\n\tanyAdj = 0\n\tfor i in j[place]:\n\t\tif not vis[i]:\n\t\t\tanyAdj = 1\n\t\t\tdfs(i, target)\n\tif anyAdj == 0:\n\t\treturn ()\n(v, e) = map(int, input().split())\nedges = []\nfor i in range(e):\n\tedges.append(list(map(int, input().split())))\ncolors = []\nfor i in edges:\n\tcolors.append(i[2])\ncolors = list(set(colors))\ncolorAdjs = []\nfor i in colors:\n\tcolorAdjs.append([[] for w in range(v)])\n\tfor j in edges:\n\t\tif j[2] == i:\n\t\t\tcolorAdjs[-1][j[0] - 1].append(j[1] - 1)\n\t\t\tcolorAdjs[-1][j[1] - 1].append(j[0] - 1)\nq = int(input())\nfor i in range(q):\n\ttotal = [0]\n\t(a, b) = map(int, input().split())\n\ta -= 1\n\tb -= 1\n\tfor j in colorAdjs:\n\t\tvis = [False] * v\n\t\tdfs(a, b)\n\tprint(total[0])\n", "def dfs(start, color):\n\tfor i in g[start]:\n\t\tif not vis[i[0]] and i[1] == color:\n\t\t\tvis[i[0]] = True\n\t\t\tdfs(i[0], i[1])\n(n, m) = map(int, input().split())\ng = [[] for i in range(n)]\nfor i in range(m):\n\t(a, b, c) = map(int, input().split())\n\tg[a - 1].append((b - 1, c))\n\tg[b - 1].append((a - 1, c))\nq = int(input())\nres = [0] * q\nfor i in range(q):\n\t(u, v) = map(int, input().split())\n\tfor j in range(1, m + 1):\n\t\tvis = [False] * n\n\t\tdfs(u - 1, j)\n\t\tif vis[v - 1]:\n\t\t\tres[i] += 1\nfor i in res:\n\tprint(i)\n", "(n, m) = map(int, input().split())\ngraphs = [[[] for _ in range(n)] for _ in range(m)]\nfor _ in range(m):\n\t(a, b, c) = map(int, input().split())\n\tgraphs[c - 1][a - 1].append(b - 1)\n\tgraphs[c - 1][b - 1].append(a - 1)\nused = None\n\ndef dfs(vertex, color):\n\tused[vertex] = True\n\tfor nei in graphs[color][vertex]:\n\t\tif not used[nei]:\n\t\t\tdfs(nei, color)\nq = int(input())\nfor _ in range(q):\n\t(u, v) = map(int, input().split())\n\tc = 0\n\tfor _color in range(m):\n\t\tused = [False] * n\n\t\tdfs(u - 1, _color)\n\t\tif used[v - 1]:\n\t\t\tc += 1\n\tprint(c)\n", "def dfs(u1, v1, c):\n\tret = False\n\tused[u1 - 1] = True\n\tfor (i, edge) in enumerate(e):\n\t\tif edge[2] != c:\n\t\t\tcontinue\n\t\tt = None\n\t\tif u1 == edge[0]:\n\t\t\tt = edge[1]\n\t\telif u1 == edge[1]:\n\t\t\tt = edge[0]\n\t\tif t and (not used[t - 1]):\n\t\t\tif t == v1:\n\t\t\t\treturn True\n\t\t\telse:\n\t\t\t\tret |= dfs(t, v1, c)\n\treturn ret\n(n, m) = map(int, input().split())\ne = [list(map(int, input().split())) for i in range(m)]\nused = [False for i in range(n)]\nq = int(input())\na = []\nfor i in range(q):\n\t(u, v) = map(int, input().split())\n\tans = 0\n\tfor c in range(1, m + 1):\n\t\tif dfs(u, v, c):\n\t\t\tans += 1\n\t\tused = [False for i in range(n)]\n\ta += [ans]\nfor i in a:\n\tprint(i)\n", "from sys import setrecursionlimit as setrec\nsetrec(10010)\n\ndef dfs(i, s, cnt):\n\tif colored[i][s] > 0:\n\t\treturn\n\tcolored[i][s] = cnt\n\tfor t in g[i][s]:\n\t\tdfs(i, t, cnt)\n(ver_n, edge_n) = map(int, input().split())\ng = [[[] for _ in range(ver_n)] for _ in range(edge_n)]\nfor _ in range(edge_n):\n\t(a, b, c) = map(lambda x: int(x) - 1, input().split())\n\tg[c][a].append(b)\n\tg[c][b].append(a)\ncolored = [[0] * ver_n for _ in range(edge_n)]\nfor i in range(edge_n):\n\tcnt = 1\n\tfor j in range(ver_n):\n\t\tdfs(i, j, cnt)\n\t\tcnt += 1\nq = int(input())\nfor i in range(q):\n\tcnt = 0\n\t(u, v) = map(lambda x: int(x) - 1, input().split())\n\tfor j in range(edge_n):\n\t\tif colored[j][u] == colored[j][v]:\n\t\t\tcnt += 1\n\tprint(cnt)\n", "class DisjointSet:\n\n\tdef __init__(self, n):\n\t\tself.num_sets = n\n\t\tself.parents = list(range(n))\n\t\tself.ranks = [0] * n\n\t\tself.sizes = [1] * n\n\n\tdef __str__(self):\n\t\treturn '%s' % self.parents\n\n\tdef __repr__(self):\n\t\treturn '%s' % self.parents\n\n\tdef find(self, j):\n\t\twhile self.parents[j] != j:\n\t\t\tj = self.parents[j]\n\t\treturn j\n\n\tdef union(self, i, j):\n\t\ti = self.find(i)\n\t\tj = self.find(j)\n\t\tif i == j:\n\t\t\treturn False\n\t\trd = self.ranks[i] - self.ranks[j]\n\t\tif rd == 0:\n\t\t\tself.ranks[i] += 1\n\t\telif rd < 0:\n\t\t\t(i, j) = (j, i)\n\t\tself.parents[j] = i\n\t\tself.sizes[i] += self.sizes[j]\n\t\tself.sizes[j] = 0\n\t\tself.num_sets -= 1\n\t\treturn True\n\ndef main():\n\t(n, m) = list(map(int, input().split()))\n\tel = [list(map(int, input().split())) for _ in range(m)]\n\tq = int(input())\n\tvl = [list(map(int, input().split())) for _ in range(q)]\n\tdl = [DisjointSet(n) for _ in range(m)]\n\tfor (a, b, c) in el:\n\t\tdl[c - 1].union(a - 1, b - 1)\n\t[print(sum([d.find(u - 1) == d.find(v - 1) for d in dl])) for (u, v) in vl]\nmain()\n", "(n, m) = map(int, input().split())\ngraph = [[] for _ in range(105)]\nfor _ in range(m):\n\t(a, b, c) = map(int, input().split())\n\tgraph[a].append([b, c])\n\tgraph[b].append([a, c])\n\ndef dfs(source, destination, colour):\n\tif source == destination:\n\t\treturn True\n\tvisited[source] = True\n\tfor node in graph[source]:\n\t\tif node[1] == colour and visited[node[0]] is False:\n\t\t\tif dfs(node[0], destination, colour):\n\t\t\t\treturn True\n\treturn False\nfor i in range(int(input())):\n\tans = 0\n\t(f, y) = map(int, input().split())\n\tfor colour in range(1, 101):\n\t\tvisited = [False] * (n + 1)\n\t\tif dfs(f, y, colour):\n\t\t\tans += 1\n\tprint(ans)\n", "used = []\n\ndef dfs(p, t, c):\n\tif p == t:\n\t\treturn True\n\tif used[p]:\n\t\treturn False\n\tused[p] = True\n\tfor ch in adj[p]:\n\t\tif ch[1] == c and (not used[ch[0]]) and dfs(ch[0], t, ch[1]):\n\t\t\treturn True\n\treturn False\n(n, m) = map(int, input().split())\nadj = []\nfor i in range(n + 1):\n\tadj.append([])\n\tused.append(False)\nfor i in range(m):\n\t(a, b, c) = map(int, input().split())\n\tadj[a].append([b, c])\n\tadj[b].append([a, c])\nq = int(input())\nfor i in range(q):\n\t(u, v) = map(int, input().split())\n\tctr = 0\n\tfor j in range(m + 1):\n\t\tif dfs(u, v, j + 1):\n\t\t\tctr += 1\n\t\tfor k in range(n + 1):\n\t\t\tused[k] = False\n\tprint(ctr)\n", "import sys\ninf = float('inf')\nmod = 1000000007\n\ndef get_array():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef get_ints():\n\treturn map(int, sys.stdin.readline().split())\n\ndef input():\n\treturn sys.stdin.readline()\nN = 105\ngraph = [[] for _ in range(N)]\ncomponent = [0] * N\nvisited = [False] * N\n\ndef explore(node):\n\tglobal cnt\n\tvisited[node] = True\n\tcomponent[node] = cnt\n\tfor (neighbour, color) in graph[node]:\n\t\tif visited[neighbour] == False:\n\t\t\texplore(neighbour)\n\ndef dfs(n):\n\tglobal cnt\n\tcnt = 0\n\tfor i in range(1, n + 1):\n\t\tif visited[i] == False:\n\t\t\tcnt += 1\n\t\t\texplore(i)\n\ndef explore_o(node, c):\n\tglobal ans, s\n\tvisited[node] = True\n\tfor (neighbour, color) in graph[node]:\n\t\tif visited[neighbour] == False and color == c:\n\t\t\tif neighbour == v:\n\t\t\t\ts.add(color)\n\t\t\texplore_o(neighbour, c)\n\ndef dfs_o(u):\n\tglobal visited, ans, flag, s\n\tans = 0\n\ts = set()\n\tfor (neighbour, color) in graph[u]:\n\t\tvisited = [False] * N\n\t\tvisited[u] = True\n\t\tflag = 0\n\t\tif neighbour == v:\n\t\t\ts.add(color)\n\t\t\tcontinue\n\t\texplore_o(neighbour, color)\n\treturn len(s)\n\ndef main():\n\tglobal n, m\n\t(n, m) = get_ints()\n\tfor _ in range(m):\n\t\t(u, x, c) = get_ints()\n\t\tgraph[u].append((x, c))\n\t\tgraph[x].append((u, c))\n\tdfs(n)\n\tglobal v\n\tfor tc in range(int(input())):\n\t\t(u, v) = get_ints()\n\t\tif component[u] != component[v]:\n\t\t\tprint(0)\n\t\t\tcontinue\n\t\tprint(dfs_o(u))\nmain()\n", "(n, m) = map(int, input().split())\nd = {}\nadj = [[] for i in range(1 + n)]\nd = [[[-1 for k in range(101)] for j in range(1 + n)] for i in range(n + 1)]\nfor i in range(m):\n\t(a, b, c) = map(int, input().split())\n\tadj[a].append(b)\n\tadj[b].append(a)\n\td[a][b][c] = 1\n\td[b][a][c] = 1\nvisited = [0] * (n + 1)\n\ndef dfs(u, target, c):\n\tif u == target:\n\t\treturn True\n\tvisited[u] = 1\n\tfor v in adj[u]:\n\t\tif visited[v] == 0 and d[u][v][c] == 1:\n\t\t\tif dfs(v, target, c):\n\t\t\t\treturn True\n\treturn False\nfor _ in range(int(input())):\n\t(u, v) = map(int, input().split())\n\tres = 0\n\tfor i in range(1, 101):\n\t\tvisited = [0] * (n + 1)\n\t\tif dfs(u, v, i):\n\t\t\tres += 1\n\tprint(res)\n", "from collections import defaultdict\n\ndef dfs(g, u, visited=None):\n\tif visited is None:\n\t\tvisited = set()\n\tvisited.add(u)\n\tfor node in g[u]:\n\t\tif node not in visited:\n\t\t\tdfs(g, node, visited)\n\treturn visited\n\ndef main():\n\t(n, m) = map(int, input().split())\n\tgraphs = {}\n\tfor _ in range(m):\n\t\t(a, b, c) = map(int, input().split())\n\t\tif c not in graphs:\n\t\t\tgraphs[c] = defaultdict(list)\n\t\tgraphs[c][a].append(b)\n\t\tgraphs[c][b].append(a)\n\tnum_queries = int(input())\n\tfor _ in range(num_queries):\n\t\t(u, v) = map(int, input().split())\n\t\tans = 0\n\t\tfor g in graphs.values():\n\t\t\tif v in dfs(g, u):\n\t\t\t\tans += 1\n\t\tprint(ans)\nmain()\n", "from sys import stdin\ninput = stdin.readline\nR = lambda : map(int, input().split())\nI = lambda : int(input())\n\ndef dfs(x, y, z):\n\tif x == y:\n\t\treturn True\n\tg[x] = 1\n\tfor p in cl[x]:\n\t\tif p[1] == z and g[p[0]] == 0 and dfs(p[0], y, z):\n\t\t\treturn True\n\treturn False\n(n, m) = R()\ncl = [[] for i in range(n)]\nfor i in range(m):\n\t(a, b, c) = R()\n\tcl[a - 1].append([b - 1, c - 1])\n\tcl[b - 1].append([a - 1, c - 1])\nq = I()\ns = [0] * q\nfor i in range(q):\n\t(u, v) = R()\n\tfor j in range(100):\n\t\tg = [0] * n\n\t\tif dfs(u - 1, v - 1, j):\n\t\t\ts[i] += 1\nfor i in s:\n\tprint(i)\n", "import sys\nfrom collections import defaultdict\nfrom functools import lru_cache\nfrom collections import Counter\n\ndef mi(s):\n\treturn map(int, s.strip().split())\n\ndef lmi(s):\n\treturn list(mi(s))\n\ndef mf(f, s):\n\treturn map(f, s)\n\ndef lmf(f, s):\n\treturn list(mf(f, s))\n\ndef path(graph, u, v, color, visited):\n\tif u == v:\n\t\treturn True\n\telif u in visited:\n\t\treturn False\n\tvisited.add(u)\n\tfor (child, c) in graph[u]:\n\t\tif color == c and path(graph, child, v, color, visited):\n\t\t\treturn True\n\treturn False\n\ndef main(graph, queries, colors):\n\tans = []\n\tfor (u, v) in queries:\n\t\tc = 0\n\t\tfor color in colors:\n\t\t\tif path(graph, u, v, color, set()):\n\t\t\t\tc += 1\n\t\tans.append(c)\n\tfor n in ans:\n\t\tprint(n)\nqueries = []\ncolors = set()\nfor (e, line) in enumerate(sys.stdin.readlines()):\n\tif e == 0:\n\t\t(n, ed) = mi(line)\n\t\tgraph = defaultdict(list)\n\t\tfor i in range(1, n + 1):\n\t\t\tgraph[i]\n\t\tk = 0\n\telif ed > 0:\n\t\t(a, b, c) = mi(line)\n\t\tgraph[a].append((b, c))\n\t\tgraph[b].append((a, c))\n\t\tcolors.add(c)\n\t\ted -= 1\n\telif ed == 0:\n\t\ted -= 1\n\t\tcontinue\n\telse:\n\t\tqueries.append(lmi(line))\nmain(graph, queries, colors)\n", "def iterative_bfs(graph, start, path=[]):\n\tq = [start]\n\twhile q:\n\t\tv = q.pop(0)\n\t\tif not v in path:\n\t\t\tpath = path + [v]\n\t\t\tq = q + graph[v]\n\treturn path\ndx = {}\n(nodes, edges) = map(int, input().split(' '))\nfor c in range(edges + 1):\n\tgraph = {}\n\tfor i in range(nodes):\n\t\tgraph[i] = []\n\tdx[c] = graph\nfor i in range(edges):\n\t(a, b, c) = map(int, input().split(' '))\n\tdx[c][a - 1].append(b - 1)\n\tdx[c][b - 1].append(a - 1)\nfor _ in range(int(input())):\n\t(a, b) = map(int, input().split(' '))\n\tt = 0\n\tfor i in dx:\n\t\tgraph = dx[i]\n\t\tif b - 1 in iterative_bfs(graph, a - 1):\n\t\t\tt += 1\n\tprint(t)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nfrom collections import defaultdict\n\ndef dfs(s, f):\n\tif s == v:\n\t\treturn True\n\tvis[s] = 1\n\tfor i in g[s]:\n\t\tif vis[i[0]] == 0 and i[1] == f:\n\t\t\tif dfs(i[0], f):\n\t\t\t\treturn True\n\treturn False\n(n, m) = map(int, input().split())\ng = [[] for i in range(n + 2)]\nfor i in range(m):\n\t(u, v, d) = map(int, input().split())\n\tg[u].append([v, d])\n\tg[v].append([u, d])\nq = int(input())\nfor _ in range(q):\n\t(u, v) = map(int, input().split())\n\tcnt = 0\n\tfor i in range(1, 101):\n\t\tvis = [0] * 101\n\t\tif dfs(u, i):\n\t\t\tcnt += 1\n\tprint(cnt)\n", "def find(c, x):\n\tp = dsu[c]\n\tif x == p[x]:\n\t\treturn x\n\treturn find(c, p[x])\n\ndef union(c, x, y):\n\tx = find(c, x)\n\ty = find(c, y)\n\tif x == y:\n\t\treturn\n\tp = dsu[c]\n\tp[x] = y\n(n, m) = map(int, input().split())\ndsu = [[i for i in range(n + 1)] for _ in range(m + 1)]\nfor _ in range(m):\n\t(a, b, c) = map(int, input().split())\n\tunion(c, a, b)\nq = int(input())\nfor _ in range(q):\n\t(a, b) = map(int, input().split())\n\tcount = 0\n\tfor c in range(1, m + 1):\n\t\tif find(c, a) == find(c, b):\n\t\t\tcount += 1\n\tprint(count)\n", "import copy\ninfo = list(map(int, input().split()))\nn = info[0]\nm = info[1]\nmat = [[[] for i in range(n)] for j in range(n)]\nfor i in range(m):\n\tinfo = list(map(int, input().split()))\n\ta = info[0]\n\tb = info[1]\n\tc = info[2]\n\tmat[a - 1][b - 1].append(c)\n\tmat[b - 1][a - 1].append(c)\nq = int(input())\nfor i in range(q):\n\tinfo = list(map(int, input().split()))\n\tu = info[0] - 1\n\tv = info[1] - 1\n\tl = []\n\tfor j in range(n):\n\t\tp = len(mat[u][j])\n\t\tfor h in range(p):\n\t\t\tl.append(mat[u][j][h])\n\tl = list(set(l))\n\tp = len(l)\n\tc = 0\n\tfor j in range(p):\n\t\tco = l[j]\n\t\tlis = [False] * n\n\t\tstk = []\n\t\tcurr = u\n\t\twhile True:\n\t\t\tfound = False\n\t\t\tfor h in range(n):\n\t\t\t\tif not lis[h] and co in mat[curr][h]:\n\t\t\t\t\tstk.append(curr)\n\t\t\t\t\tlis[h] = True\n\t\t\t\t\tcurr = h\n\t\t\t\t\tfound = True\n\t\t\t\t\tbreak\n\t\t\tif curr == v:\n\t\t\t\tc += 1\n\t\t\t\tbreak\n\t\t\tif not found:\n\t\t\t\tif len(stk) == 0:\n\t\t\t\t\tbreak\n\t\t\t\tcurr = stk[-1]\n\t\t\t\tstk.pop(-1)\n\tprint(c)\n", "import sys, os, io\n\ndef rs():\n\treturn sys.stdin.readline().rstrip()\n\ndef ri():\n\treturn int(sys.stdin.readline())\n\ndef ria():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef ws(s):\n\tsys.stdout.write(s + '\\n')\n\ndef wi(n):\n\tsys.stdout.write(str(n) + '\\n')\n\ndef wia(a):\n\tsys.stdout.write(' '.join([str(x) for x in a]) + '\\n')\nimport math, datetime, functools, itertools, operator, bisect, fractions, statistics\nfrom collections import deque, defaultdict, OrderedDict, Counter\nfrom fractions import Fraction\nfrom decimal import Decimal\nfrom sys import stdout\nfrom heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest\nINF = 99999999999999999999999999999999\n\ndef outIn(x):\n\tprint(x, flush=True)\n\treturn input()\n\ndef main():\n\tmod = 1000000007\n\tstarttime = datetime.datetime.now()\n\tif os.path.exists('input.txt'):\n\t\tsys.stdin = open('input.txt', 'r')\n\t\tsys.stdout = open('output.txt', 'w')\n\ttc = 1\n\tfor _ in range(tc):\n\t\t(n, m) = ria()\n\t\td = {}\n\t\tfor i in range(m):\n\t\t\t(a, b, c) = ria()\n\t\t\tif c not in d:\n\t\t\t\td[c] = [[a, b]]\n\t\t\telse:\n\t\t\t\td[c].append([a, b])\n\n\t\tdef dfs(graph, start, visited):\n\t\t\tn = len(graph)\n\t\t\tcomp = []\n\t\t\tstack = [start]\n\t\t\tt = 0\n\t\t\twhile stack:\n\t\t\t\tstart = stack[-1]\n\t\t\t\tif not visited[start]:\n\t\t\t\t\tcomp.append(start)\n\t\t\t\t\tvisited[start] = True\n\t\t\t\t\tfor child in graph[start]:\n\t\t\t\t\t\tif not visited[child]:\n\t\t\t\t\t\t\tstack.append(child)\n\t\t\t\telse:\n\t\t\t\t\tstack.pop()\n\t\t\treturn (comp, visited)\n\t\tfd = {}\n\t\tfor i in range(1, m + 1):\n\t\t\tif i in d:\n\t\t\t\tvisited = [False] * (n + 1)\n\t\t\t\tgraph = [[] for i in range(n + 1)]\n\t\t\t\tvert = {}\n\t\t\t\tfor (u, v) in d[i]:\n\t\t\t\t\tvert[u] = 1\n\t\t\t\t\tvert[v] = 1\n\t\t\t\t\tgraph[u].append(v)\n\t\t\t\t\tgraph[v].append(u)\n\t\t\t\tfor j in vert:\n\t\t\t\t\tif not visited[j]:\n\t\t\t\t\t\t(comp, visited) = dfs(graph, j, visited)\n\t\t\t\t\t\tif i in fd:\n\t\t\t\t\t\t\tfd[i].append(comp)\n\t\t\t\t\t\telse:\n\t\t\t\t\t\t\tfd[i] = [comp]\n\t\tq = ri()\n\t\tfor i in range(q):\n\t\t\t(u, v) = ria()\n\t\t\tcount = 0\n\t\t\tfor j in range(1, m + 1):\n\t\t\t\tf = 0\n\t\t\t\tif j in fd:\n\t\t\t\t\tfor t in fd[j]:\n\t\t\t\t\t\tif u in t and v in t:\n\t\t\t\t\t\t\tf = 1\n\t\t\t\t\t\t\tbreak\n\t\t\t\tcount += f\n\t\t\tprint(count)\n\tendtime = datetime.datetime.now()\n\ttime = (endtime - starttime).total_seconds() * 1000\n\tif os.path.exists('input.txt'):\n\t\tprint('Time:', time, 'ms')\n\nclass FastReader(io.IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, fd, chunk_size=1024 * 8):\n\t\tself._fd = fd\n\t\tself._chunk_size = chunk_size\n\t\tself.buffer = io.BytesIO()\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self, size=-1):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\nclass FastWriter(io.IOBase):\n\n\tdef __init__(self, fd):\n\t\tself._fd = fd\n\t\tself.buffer = io.BytesIO()\n\t\tself.write = self.buffer.write\n\n\tdef flush(self):\n\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass FastStdin(io.IOBase):\n\n\tdef __init__(self, fd=0):\n\t\tself.buffer = FastReader(fd)\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n\nclass FastStdout(io.IOBase):\n\n\tdef __init__(self, fd=1):\n\t\tself.buffer = FastWriter(fd)\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.flush = self.buffer.flush\nsys.stdin = FastStdin()\nsys.stdout = FastStdout()\nmain()\n", "def dfs(x, c):\n\tvis[x] = 1\n\tfor i in adj[c][x]:\n\t\tif not vis[i]:\n\t\t\tdfs(i, c)\n\ndef check(u, v, c):\n\tfor i in range(1, n + 1):\n\t\tvis[i] = False\n\tdfs(u, c)\n\treturn vis[v]\n(n, m) = map(int, input().split())\nadj = []\nfor i in range(m + 1):\n\tadj.append([])\n\tfor j in range(n + 1):\n\t\tadj[i].append([])\nvis = [False] * (n + 1)\nfor i in range(m):\n\t(a, b, c) = map(int, input().split())\n\tadj[c][a].append(b)\n\tadj[c][b].append(a)\nq = int(input())\nfor i in range(q):\n\t(u, v) = map(int, input().split())\n\tans = 0\n\tfor c in range(1, m + 1):\n\t\tif check(u, v, c):\n\t\t\tans += 1\n\tprint(ans)\n", "class CodeforcesTask505BSolution:\n\n\tdef __init__(self):\n\t\tself.result = ''\n\t\tself.n_m = []\n\t\tself.edges = []\n\t\tself.q = 0\n\t\tself.queries = []\n\n\tdef read_input(self):\n\t\tself.n_m = [int(x) for x in input().split(' ')]\n\t\tfor x in range(self.n_m[1]):\n\t\t\tself.edges.append([int(y) for y in input().split(' ')])\n\t\tself.q = int(input())\n\t\tfor x in range(self.q):\n\t\t\tself.queries.append([int(y) for y in input().split(' ')])\n\n\tdef process_task(self):\n\t\tgraphs = [[[] for x in range(self.n_m[0])] for c in range(self.n_m[1])]\n\t\tfor edge in self.edges:\n\t\t\tgraphs[edge[2] - 1][edge[0] - 1].append(edge[1])\n\t\t\tgraphs[edge[2] - 1][edge[1] - 1].append(edge[0])\n\t\tresults = []\n\t\tfor query in self.queries:\n\t\t\tto_visit = [(query[0], c) for c in range(self.n_m[1])]\n\t\t\tused = set()\n\t\t\tvisited = [[False] * self.n_m[0] for x in range(self.n_m[1])]\n\t\t\twhile to_visit:\n\t\t\t\tvisiting = to_visit.pop(-1)\n\t\t\t\tif visiting[1] not in used and (not visited[visiting[1]][visiting[0] - 1]):\n\t\t\t\t\tvisited[visiting[1]][visiting[0] - 1] = True\n\t\t\t\t\tif visiting[0] == query[1]:\n\t\t\t\t\t\tused.add(visiting[1])\n\t\t\t\t\telse:\n\t\t\t\t\t\tto_visit.extend([(x, visiting[1]) for x in graphs[visiting[1]][visiting[0] - 1]])\n\t\t\tcolors = len(used)\n\t\t\tresults.append(colors)\n\t\tself.result = '\\n'.join([str(x) for x in results])\n\n\tdef get_result(self):\n\t\treturn self.result\nSolution = CodeforcesTask505BSolution()\nSolution.read_input()\nSolution.process_task()\nprint(Solution.get_result())\n", "def solve():\n\n\tdef dfs(c):\n\t\tif c == v:\n\t\t\treturn True\n\t\tr = False\n\t\tfor i in range(1, n + 1):\n\t\t\tif g[w][c][i] and i not in p:\n\t\t\t\tp[i] = c\n\t\t\t\tr |= dfs(i)\n\t\treturn r\n\t(n, m) = map(int, input().split())\n\tg = [[[False for j in range(n + 1)] for i in range(n + 1)] for _ in range(m + 1)]\n\tfor _ in range(m):\n\t\t(u, v, w) = map(int, input().split())\n\t\tg[w][u][v] = True\n\t\tg[w][v][u] = True\n\tfor _ in range(int(input())):\n\t\t(u, v) = map(int, input().split())\n\t\tres = 0\n\t\tfor w in range(1, m + 1):\n\t\t\tp = dict()\n\t\t\tp[u] = -1\n\t\t\tres += dfs(u)\n\t\tprint(res)\nsolve()\n", "from sys import stdin, stdout\ninput = stdin.readline\n\ndef main():\n\t(n, m) = map(int, input().split())\n\tsets = [list(range(n + 1)) for i in range(m)]\n\tsizes = [[1] * (n + 1) for i in range(m)]\n\n\tdef get(a, ind):\n\t\tif sets[ind][a] != a:\n\t\t\tsets[ind][a] = get(sets[ind][a], ind)\n\t\treturn sets[ind][a]\n\n\tdef union(a, b, ind):\n\t\ta = get(a, ind)\n\t\tb = get(b, ind)\n\t\tif a == b:\n\t\t\treturn\n\t\tif sizes[ind][a] > sizes[ind][b]:\n\t\t\t(a, b) = (b, a)\n\t\tsets[ind][a] = b\n\t\tsizes[ind][b] += sizes[ind][a]\n\tfor i in range(m):\n\t\t(a, b, c) = map(int, input().split())\n\t\ta -= 1\n\t\tb -= 1\n\t\tc -= 1\n\t\tunion(a, b, c)\n\tq = int(input())\n\tfor i in range(q):\n\t\tans = 0\n\t\t(u, v) = map(int, input().split())\n\t\tu -= 1\n\t\tv -= 1\n\t\tfor j in range(m):\n\t\t\tans += int(get(u, j) == get(v, j))\n\t\tprint(ans)\nmain()\n", "(n, m) = map(int, input().split())\nINF = 10 ** 18\nd = [[[INF] * n for j in range(n)] for i in range(m)]\nedges = [[[] for i in range(n)] for i in range(m)]\nfor _ in range(m):\n\t(a, b, c) = map(int, input().split())\n\ta -= 1\n\tb -= 1\n\tc -= 1\n\tedges[c][a].append(b)\n\tedges[c][b].append(a)\n\td[c][a][b] = d[c][b][a] = 1\nfor color in range(m):\n\tfor s in range(n):\n\t\tq = [s]\n\t\tvisited = [False] * n\n\t\tvisited[s] = True\n\t\twhile q:\n\t\t\tnode = q.pop(0)\n\t\t\tvisited[node] = True\n\t\t\tfor to in edges[color][node]:\n\t\t\t\tif visited[to]:\n\t\t\t\t\tcontinue\n\t\t\t\td[color][s][to] = d[color][to][s] = 1\n\t\t\t\tq.append(to)\nQ = int(input())\nfor _ in range(Q):\n\t(u, v) = map(int, input().split())\n\tu -= 1\n\tv -= 1\n\tans = 0\n\tfor color in range(m):\n\t\tif d[color][u][v] < INF:\n\t\t\tans += 1\n\tprint(ans)\n", "(v, e) = map(int, input().split())\ngraphs = [[set([i]) for i in range(1, v + 1)] for _ in range(101)]\n\ndef getSet(sets, vertex):\n\tfor s in sets:\n\t\tif vertex in s:\n\t\t\treturn s\nfor _ in range(e):\n\t(a, b, c) = map(int, input().split())\n\tsa = getSet(graphs[c], a)\n\tsb = getSet(graphs[c], b)\n\tif sa.isdisjoint(sb):\n\t\tsa |= sb\n\t\tgraphs[c].remove(sb)\nq = int(input())\nfor _ in range(q):\n\t(a, b) = map(int, input().split())\n\tc = 0\n\tfor graph in graphs:\n\t\tsa = getSet(graph, a)\n\t\tsb = getSet(graph, b)\n\t\tif not sa.isdisjoint(sb):\n\t\t\tc += 1\n\tprint(c)\n", "import sys\nimport math\nfrom collections import defaultdict\nimport itertools\nMAXNUM = math.inf\nMINNUM = -1 * math.inf\n\ndef getInt():\n\treturn int(sys.stdin.readline().rstrip())\n\ndef getInts():\n\treturn map(int, sys.stdin.readline().rstrip().split(' '))\n\ndef getString():\n\treturn sys.stdin.readline().rstrip()\n\ndef printOutput(ans):\n\tsys.stdout.write()\n\tpass\n\ndef dfs(a, b, edgeList):\n\ttotal = 0\n\tcLook = set()\n\tfor (nxt, col) in edgeList[a]:\n\t\tif col not in cLook:\n\t\t\texplored = dict()\n\t\t\texplored[a] = True\n\t\t\texplored[nxt] = True\n\t\t\tif dfs_helper(nxt, b, edgeList, col, explored) == 1:\n\t\t\t\tcLook.add(col)\n\t\t\t\ttotal += 1\n\treturn total\n\ndef dfs_helper(cur, goal, edgeList, color, explored):\n\tif cur == goal:\n\t\treturn 1\n\tfor (nxt, col) in edgeList[cur]:\n\t\tif col == color and nxt not in explored:\n\t\t\texplored[nxt] = True\n\t\t\tif dfs_helper(nxt, goal, edgeList, color, explored) == 1:\n\t\t\t\treturn 1\n\t\t\tdel explored[nxt]\n\treturn 0\n\ndef solve(n, m, edgeList, queries):\n\tfor (a, b) in queries:\n\t\tprint(dfs(a, b, edgeList))\n\ndef readinput():\n\t(n, m) = getInts()\n\tedgeList = defaultdict(list)\n\tfor _ in range(m):\n\t\t(a, b, c) = getInts()\n\t\tedgeList[a].append((b, c))\n\t\tedgeList[b].append((a, c))\n\tqueries = []\n\tq = getInt()\n\tfor _ in range(q):\n\t\tqueries.append(tuple(getInts()))\n\tsolve(n, m, edgeList, queries)\nreadinput()\n", "from sys import stdin, stdout\n\ndef find(node, color):\n\tx = []\n\twhile colors[color][node] > 0:\n\t\tx.append(node)\n\t\tnode = colors[color][node]\n\tfor i in x:\n\t\tcolors[color][i] = node\n\treturn node\n\ndef union(node1, node2, color):\n\tif node1 != node2:\n\t\tif colors[color][node1] > colors[color][node2]:\n\t\t\t(node1, node2) = (node2, node1)\n\t\tcolors[color][node1] += colors[color][node2]\n\t\tcolors[color][node2] = node1\n(n, m) = map(int, stdin.readline().strip().split())\ncolors = [[-1 for i in range(n + 1)] for j in range(m + 1)]\nfor __ in range(m):\n\t(a, b, c) = map(int, stdin.readline().strip().split())\n\tunion(find(b, c), find(a, c), c)\nq = int(stdin.readline().strip())\noutputs = []\nfor __ in range(q):\n\tcount = 0\n\t(a, b) = map(int, stdin.readline().strip().split())\n\tfor i in range(1, m + 1):\n\t\tif find(a, i) == find(b, i):\n\t\t\tcount += 1\n\toutputs.append(count)\nfor output in outputs:\n\tstdout.write(f'{output}\\n')\n", "import math\nimport os\nfrom io import BytesIO, IOBase\nimport sys\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nfrom collections import defaultdict\n(n, m) = map(int, input().split())\ngraphs = defaultdict(lambda : defaultdict(list))\nfor _ in range(m):\n\t(a, b, c) = map(int, input().split())\n\tgraphs[c][a].append(b)\n\tgraphs[c][b].append(a)\nseen = set()\n\ndef dfs(curr, orig, color):\n\tif curr in seen:\n\t\treturn\n\tseen.add(curr)\n\tfor new in graphs[color][curr]:\n\t\tif new != orig:\n\t\t\tdfs(new, curr, color)\nq = int(input())\nfor _ in range(q):\n\t(a, b) = map(int, input().split())\n\tfound = 0\n\tfor c in graphs.keys():\n\t\tseen.clear()\n\t\tdfs(a, -1, c)\n\t\tif b in seen:\n\t\t\tfound += 1\n\tprint(found)\n", "from collections import defaultdict\n\nclass DisjSet:\n\n\tdef __init__(self, n):\n\t\tself.rank = [1] * n\n\t\tself.parent = [i for i in range(n)]\n\n\tdef find(self, x):\n\t\tif self.parent[x] != x:\n\t\t\tself.parent[x] = self.find(self.parent[x])\n\t\treturn self.parent[x]\n\n\tdef Union(self, x, y):\n\t\txset = self.find(x)\n\t\tyset = self.find(y)\n\t\tif xset == yset:\n\t\t\treturn\n\t\tif self.rank[xset] < self.rank[yset]:\n\t\t\tself.parent[xset] = yset\n\t\telif self.rank[xset] > self.rank[yset]:\n\t\t\tself.parent[yset] = xset\n\t\telse:\n\t\t\tself.parent[yset] = xset\n\t\t\tself.rank[xset] = self.rank[xset] + 1\nL = []\n(n, m) = map(int, input().split())\nedges = []\nfor k in range(m):\n\t(a, b, c) = map(int, input().split())\n\tedges.append([a, b, c])\nq = int(input())\nqueries = []\nfor l in range(q):\n\t(x, y) = map(int, input().split())\n\tqueries.append([x, y])\ncount = [0 for i in range(q)]\nfor i in range(1, 101):\n\tg = DisjSet(101)\n\tfor [u, v, c] in edges:\n\t\tif c == i:\n\t\t\tg.Union(u, v)\n\tfor z in range(q):\n\t\tif g.find(queries[z][0]) == g.find(queries[z][1]):\n\t\t\tcount[z] += 1\nfor m in range(q):\n\tprint(count[m])\n", "class Solution:\n\n\tdef __init__(self, n, m, edges):\n\t\tself.n = n\n\t\tself.m = m\n\t\tself.edges = [[[] for _ in range(m + 1)] for _ in range(n + 1)]\n\t\tfor (_from, _to, _color) in edges:\n\t\t\tself.edges[_from][_color].append(_to)\n\t\t\tself.edges[_to][_color].append(_from)\n\t\tself.id = 0\n\n\tdef initialize(self):\n\t\tself.discovered = [[0] * (self.n + 1) for i in range(self.m + 1)]\n\n\tdef bfs(self, x0, color):\n\t\tself.id += 1\n\t\tstack = [x0]\n\t\twhile stack:\n\t\t\tn = stack.pop()\n\t\t\tif not self.discovered[color][n]:\n\t\t\t\tself.discovered[color][n] = self.id\n\t\t\t\tfor neigh in self.edges[n][color]:\n\t\t\t\t\tstack.append(neigh)\n\ndef solve(graph, colors, u, v):\n\tcounter = 0\n\tfor color in colors:\n\t\tif not graph.discovered[color][u] and (not graph.discovered[color][v]):\n\t\t\tgraph.bfs(u, color)\n\t\tif graph.discovered[color][u] == graph.discovered[color][v]:\n\t\t\tcounter += 1\n\treturn counter\n\ndef main():\n\t(n, m) = map(int, input().split())\n\tedges = []\n\tcolors = set()\n\tfor _ in range(m):\n\t\t(a, b, c) = map(int, input().split())\n\t\tcolors.add(c)\n\t\tedges.append((a, b, c))\n\tgraph = Solution(n, m, edges)\n\tgraph.initialize()\n\tq = int(input())\n\tfor _ in range(q):\n\t\t(u, v) = map(int, input().split())\n\t\tprint(solve(graph, colors, u, v))\nmain()\n", "def find(num, color):\n\twhile dsu[color][num] != num:\n\t\tnum = dsu[color][num]\n\treturn num\ninp = lambda : map(int, input().split())\n(n, m) = inp()\ndsu = [[i for i in range(n + 1)] for _ in range(101)]\nfor i in range(m):\n\t(x, y, z) = inp()\n\tx1 = find(x, z)\n\ty1 = find(y, z)\n\tif x1 != y1:\n\t\tdsu[z][x1] = y1\nq = int(input())\nfor i in range(q):\n\t(x, y) = inp()\n\tans = 0\n\tfor j in range(101):\n\t\tif find(x, j) == find(y, j):\n\t\t\tans += 1\n\tprint(ans)\n", "import math, sys, bisect, heapq\nfrom collections import defaultdict, Counter, deque\nfrom itertools import groupby, accumulate\nint1 = lambda x: int(x) - 1\ninput = iter(sys.stdin.buffer.read().decode().splitlines()).__next__\nilele = lambda : map(int, input().split())\nalele = lambda : list(map(int, input().split()))\nilelec = lambda : map(int1, input().split())\nalelec = lambda : list(map(int1, input().split()))\n\ndef list2d(a, b, c):\n\treturn [[c] * b for i in range(a)]\n\ndef list3d(a, b, c, d):\n\treturn [[[d] * c for j in range(b)] for i in range(a)]\n\ndef Y(c):\n\tprint(['NO', 'YES'][c])\n\ndef y(c):\n\tprint(['no', 'yes'][c])\n\ndef Yy(c):\n\tprint(['No', 'Yes'][c])\n(n, m) = ilele()\nColor = defaultdict(set)\nG = defaultdict(set)\nC = set()\n\ndef addEdge(a, b):\n\tG[a].add(b)\n\tG[b].add(a)\n\ndef addColor(a, b, c):\n\tColor[a, b].add(c)\n\tColor[b, a].add(c)\n\tC.add(c)\nfor i in range(m):\n\t(a, b, c) = ilele()\n\taddColor(a, b, c)\n\taddEdge(a, b)\nvis = [False] * (n + 1)\nAns = []\n\ndef fun(node, dest, vis, grp):\n\tif not grp:\n\t\treturn\n\tif node == dest:\n\t\tfor i in grp:\n\t\t\tAns.append(i)\n\t\treturn\n\tvis[node] = True\n\tfor i in G.get(node, []):\n\t\tif not vis[i]:\n\t\t\tnewvis = vis.copy()\n\t\t\tz = grp.intersection(Color[node, i])\n\t\t\tfun(i, dest, newvis, z)\nfor i in range(int(input())):\n\t(a, b) = ilele()\n\tvis = [False] * (n + 1)\n\tgrp = C.copy()\n\tfun(a, b, vis, grp)\n\tprint(len(set(Ans)))\n\tAns = []\n", "(n, m) = list(map(int, input().split(' ')))\nMeow = []\nfor i in range(101):\n\tMeow.append([])\n\tfor j in range(n + 1):\n\t\tMeow[i].append(j)\n\ndef root(N, C):\n\twhile Meow[C][N] != N:\n\t\tMeow[C][N] = Meow[C][Meow[C][N]]\n\t\tN = Meow[C][N]\n\treturn N\n\ndef union(A, B, C):\n\tp = root(A, C)\n\tq = root(B, C)\n\tMeow[C][p] = q\nfor i in range(m):\n\t(a, b, c) = list(map(int, input().split(' ')))\n\tunion(a, b, c)\nq = int(input())\nfor i in range(q):\n\t(a, b) = list(map(int, input().split(' ')))\n\tcnt = 0\n\tfor i in range(1, 101):\n\t\tif root(a, i) == root(b, i):\n\t\t\tcnt += 1\n\tprint(cnt)\n", "from collections import defaultdict\n__author__ = 'artyom'\nread = lambda : map(int, input().split())\nall_edges = defaultdict(list)\n(n, m) = read()\nfor _ in range(m):\n\t(a, b, c) = read()\n\tall_edges[c].append((a, b))\ngraphs = []\n\ndef root(components, x, l=0):\n\treturn (x, l) if components[x] == x else root(components, components[x], l + 1)\n\ndef connected_components(edges):\n\tcomponents = [i for i in range(n + 1)]\n\tfor (u, v) in edges:\n\t\t(ru, lu) = root(components, u)\n\t\t(rv, lv) = root(components, v)\n\t\tif ru != rv:\n\t\t\tif lu < lv:\n\t\t\t\tcomponents[ru] = rv\n\t\t\telse:\n\t\t\t\tcomponents[rv] = ru\n\treturn components\nfor (c, edges) in all_edges.items():\n\tgraphs.append(connected_components(edges))\n\ndef count_in_same_component(u, v):\n\tcount = 0\n\tfor graph in graphs:\n\t\tif root(graph, u)[0] == root(graph, v)[0]:\n\t\t\tcount += 1\n\treturn count\nans = ''\nfor __ in range(int(input())):\n\t(u, v) = read()\n\tans += str(count_in_same_component(u, v)) + '\\n'\nprint(ans)\n", "(n, m) = map(int, input().split())\nl = []\nfor i in range(m):\n\t(a, b, c) = map(int, input().split())\n\tif len(l) <= c - 1:\n\t\tfor i in range(c - len(l)):\n\t\t\tl.append([])\n\tp = l[c - 1]\n\tm = []\n\tfor i in range(len(p)):\n\t\tif a in p[i] or b in p[i]:\n\t\t\tm.append(i)\n\tnew = [a, b]\n\tfor i in range(len(m)):\n\t\tnew = new + p[m[i]]\n\tfor i in range(len(m)):\n\t\tp.pop(m[i] - i)\n\tp.append(new)\n\tl[c - 1] = p\nq = int(input())\nfor i in range(q):\n\tcounter = 0\n\t(u, v) = map(int, input().split())\n\tfor j in range(len(l)):\n\t\tyes = 0\n\t\tfor k in range(len(l[j])):\n\t\t\tif yes == 0 and u in l[j][k] and (v in l[j][k]):\n\t\t\t\tyes = 1\n\t\t\t\tcounter += 1\n\tprint(counter)\n", "class Union:\n\n\tdef __init__(self, size):\n\t\tself.ancestor = [i for i in range(size + 1)]\n\n\tdef find(self, node):\n\t\tif self.ancestor[node] == node:\n\t\t\treturn node\n\t\tself.ancestor[node] = self.find(self.ancestor[node])\n\t\treturn self.ancestor[node]\n\n\tdef merge(self, a, b):\n\t\t(a, b) = (self.find(a), self.find(b))\n\t\tself.ancestor[a] = b\n(n, m) = map(int, input().split())\nunions = [Union(n) for _ in range(m + 1)]\ngraph = [[] for _ in range(n + 1)]\nfor _ in range(m):\n\t(a, b, c) = map(int, input().split())\n\tgraph[a].append((b, c))\n\tgraph[b].append((a, c))\n\tunions[c].merge(a, b)\nfor _ in range(int(input())):\n\t(a, b) = map(int, input().split())\n\tans = 0\n\tfor i in range(1, m + 1):\n\t\tans += unions[i].find(a) == unions[i].find(b)\n\tprint(ans)\n", "class ufds:\n\n\tdef __init__(self):\n\t\tself.rank = dict()\n\t\tself.value = dict()\n\n\tdef union(self, a, b):\n\t\t(x, y) = (self.findSet(a), self.findSet(b))\n\t\tif self.rank[x] > self.rank[y]:\n\t\t\tself.value[y] = x\n\t\telse:\n\t\t\tself.value[x] = y\n\t\tif self.rank[x] == self.rank[y]:\n\t\t\tself.rank[y] += 1\n\n\tdef findSet(self, x):\n\t\tif x != self.value[x]:\n\t\t\tself.value[x] = self.findSet(self.value[x])\n\t\treturn self.value[x]\n\n\tdef sameSet(self, a, b):\n\t\treturn self.findSet(a) == self.findSet(b)\n\n\tdef createKey(self, x):\n\t\tself.rank.update({x: 0})\n\t\tself.value.update({x: x})\na = list(map(int, input().split()))\nsize = a[0]\ngraph = dict()\nfor i in range(a[1]):\n\tb = list(map(int, input().split()))\n\tcolor = b[2]\n\tif color not in graph.keys():\n\t\tgraph.update({color: ufds()})\n\t\tfor i in range(size):\n\t\t\tgraph[color].createKey(i + 1)\n\tgraph[color].union(b[0], b[1])\nfor i in range(int(input())):\n\tb = list(map(int, input().split()))\n\tcounter = 0\n\tfor j in graph.keys():\n\t\tif graph[j].sameSet(b[0], b[1]):\n\t\t\tcounter += 1\n\tprint(counter)\n", "import sys\n\nclass Dsu:\n\n\tdef __init__(self):\n\t\tself.__sz = {}\n\t\tself.__parent = {}\n\n\tdef parent(self, a):\n\t\tif a not in self.__parent or a == self.__parent[a]:\n\t\t\treturn a\n\t\telse:\n\t\t\tself.__parent[a] = self.parent(self.__parent[a])\n\t\t\treturn self.__parent[a]\n\n\tdef connect(self, a, b):\n\t\tp1 = self.parent(a)\n\t\tp2 = self.parent(b)\n\t\tif p2 != p1:\n\t\t\tif p1 not in self.__sz:\n\t\t\t\tself.__sz[p1] = 1\n\t\t\tif p2 not in self.__sz:\n\t\t\t\tself.__sz[p2] = 1\n\t\t\tsz1 = self.__sz[p1]\n\t\t\tsz2 = self.__sz[p2]\n\t\t\tif sz1 >= sz2:\n\t\t\t\tself.__parent[p2] = p1\n\t\t\t\tself.__sz[p1] += self.__sz[p2]\n\t\t\telse:\n\t\t\t\tself.__parent[p1] = p2\n\t\t\t\tself.__sz[p2] += self.__sz[p1]\n\n\tdef connected(self, a, b):\n\t\treturn self.parent(a) == self.parent(b)\n(n, m) = [int(i) for i in input().split(' ')]\ng = {}\nchoice = {}\nfor j in range(m):\n\t(a, b, c) = [int(i) for i in input().split(' ')]\n\tif c not in g:\n\t\tg[c] = Dsu()\n\tg[c].connect(a, b)\n\tif a not in choice:\n\t\tchoice[a] = []\n\tif b not in choice:\n\t\tchoice[b] = []\n\tchoice[a].append(c)\n\tchoice[b].append(c)\nq = int(input())\nmem = {}\nfor j in range(q):\n\t(a, b) = [int(i) for i in input().split(' ')]\n\tif a not in choice or b not in choice:\n\t\tprint('0')\n\t\tcontinue\n\tif a in mem and type(mem[a]) == dict and (b in mem[a]):\n\t\ts = mem[a][b]\n\telse:\n\t\toptions = set.intersection(set(choice[a]), set(choice[b]))\n\t\ts = 0\n\t\tfor c in options:\n\t\t\ts += int(g[c].connected(a, b))\n\t\tif a not in mem:\n\t\t\tmem[a] = {}\n\t\tif b not in mem:\n\t\t\tmem[b] = {}\n\t\tmem[a][b] = mem[b][a] = s\n\tprint(s)\n", "from collections import defaultdict\n\ndef main():\n\t(n, m) = map(int, input().split())\n\tedges = defaultdict(lambda : defaultdict(list))\n\tfor _ in range(m):\n\t\t(a, b, c) = map(int, input().split())\n\t\td = edges[c]\n\t\td[a].append(b)\n\t\td[b].append(a)\n\n\tdef dfs(t):\n\t\tchain.add(t)\n\t\tdd = color.get(t, ())\n\t\tfor y in dd:\n\t\t\tif y not in chain:\n\t\t\t\tdfs(y)\n\tres = []\n\tchain = set()\n\tfor _ in range(int(input())):\n\t\t(a, b) = map(int, input().split())\n\t\tx = 0\n\t\tfor color in edges.values():\n\t\t\tchain.clear()\n\t\t\tdfs(a)\n\t\t\tif b in chain:\n\t\t\t\tx += 1\n\t\tres.append(str(x))\n\tprint('\\n'.join(res))\nmain()\n", "scanf = lambda : map(int, input().split())\n(n, m) = scanf()\nf = [list(range(n + 1)) for _ in range(m + 2)]\n\ndef fd(a, c):\n\tif f[c][a] != a:\n\t\tf[c][a] = fd(f[c][a], c)\n\treturn f[c][a]\n\ndef un(a, b, c):\n\t(ra, rb) = (fd(a, c), fd(b, c))\n\tif ra == rb:\n\t\treturn\n\tf[c][ra] = rb\n\ndef swap(a, b):\n\ttmp = a\n\ta = b\n\tb = tmp\nfor (a, b, c) in [map(int, input().split()) for _ in range(m)]:\n\tun(a, b, c)\nq = int(input())\nfor (x, y) in [map(int, input().split()) for _ in range(q)]:\n\tprint(sum((1 for i in range(1, m + 1) if fd(x, i) == fd(y, i))))\n", "class Graph(object):\n\n\tdef __init__(self, num_nodes):\n\t\tself.num_nodes = num_nodes\n\t\tself.adj_list = {}\n\n\tdef __add_directional_edge(self, a, b, c):\n\t\tif a in self.adj_list:\n\t\t\tif b in self.adj_list[a]:\n\t\t\t\tif c not in self.adj_list[a][b]:\n\t\t\t\t\tself.adj_list[a][b].append(c)\n\t\t\telse:\n\t\t\t\tself.adj_list[a][b] = []\n\t\t\t\tself.adj_list[a][b].append(c)\n\t\telse:\n\t\t\tself.adj_list[a] = {}\n\t\t\tself.adj_list[a][b] = []\n\t\t\tself.adj_list[a][b].append(c)\n\n\tdef add_edge(self, a, b, c):\n\t\tself.__add_directional_edge(a, b, c)\n\t\tself.__add_directional_edge(b, a, c)\n\n\tdef print_graph(self):\n\t\tprint(self.adj_list)\n\ndef tc():\n\tg = readGraph()\n\tfor k in range(1, g.num_nodes + 1):\n\t\tfor i in range(1, g.num_nodes + 1):\n\t\t\tfor j in range(1, g.num_nodes + 1):\n\t\t\t\tl1 = g.adj_list.get(i, {}).get(k, [])\n\t\t\t\tl2 = g.adj_list.get(k, {}).get(j, [])\n\t\t\t\tfor color in l1:\n\t\t\t\t\tif color in l2:\n\t\t\t\t\t\tg.add_edge(i, j, color)\n\treturn g\n\ndef readGraph():\n\t(n, m) = map(int, input().split())\n\tg = Graph(n)\n\tfor _ in range(m):\n\t\t(a, b, c) = map(int, input().split())\n\t\tg.add_edge(a, b, c)\n\treturn g\n\ndef read_query():\n\tq = int(input())\n\tq_list = []\n\tfor _ in range(q):\n\t\t(u, v) = map(int, input().split())\n\t\tq_list.append((u, v))\n\treturn q_list\n\ndef solve_query(g, q_list):\n\tfor (u, v) in q_list:\n\t\tif u in g.adj_list:\n\t\t\tif v in g.adj_list[u]:\n\t\t\t\tprint(len(g.adj_list[u][v]))\n\t\t\telse:\n\t\t\t\tprint('0')\n\t\telse:\n\t\t\tprint('0')\n\ndef main():\n\tg = tc()\n\tq_list = read_query()\n\tsolve_query(g, q_list)\nmain()\n", "def solution():\n\t(n, m) = [int(x) for x in input().split(' ')]\n\tgraphs = {}\n\tedges = {}\n\tfor i in range(m):\n\t\t(x, y, c) = input().split(' ')\n\t\tif c not in graphs:\n\t\t\tgraphs[c] = {}\n\t\tif x not in graphs[c]:\n\t\t\tgraphs[c][x] = []\n\t\tif y not in graphs[c]:\n\t\t\tgraphs[c][y] = []\n\t\tgraphs[c][x].append(y)\n\t\tgraphs[c][y].append(x)\n\tq = int(input())\n\tqueries = []\n\tfor i in range(q):\n\t\t(x, y) = input().split(' ')\n\t\tans = 0\n\t\tfor (c, graph) in graphs.items():\n\t\t\tans += 1 if areConnected(x, y, graph) else 0\n\t\tprint(ans)\n\ndef areConnected(x, y, graph):\n\tif x not in graph or y not in graph:\n\t\treturn False\n\tqueu = [x]\n\talready = [x]\n\twhile len(queu) != 0:\n\t\tcurrent = queu[0]\n\t\tif current == y:\n\t\t\treturn True\n\t\tdel queu[0]\n\t\talready.append(current)\n\t\tfor i in graph[current]:\n\t\t\tif i not in already and i not in queu:\n\t\t\t\tif i == y:\n\t\t\t\t\treturn True\n\t\t\t\tqueu.append(i)\n\treturn False\nsolution()\n", "(n, m) = map(int, input().split())\nadj = [[] for _ in range(n)]\nfor i in range(m):\n\t(a, b, c) = map(int, input().split())\n\ta -= 1\n\tb -= 1\n\tadj[a].append([b, c])\n\tadj[b].append([a, c])\n\ndef dfs(v, c, u, vis):\n\tans = []\n\tvis[v] = True\n\tif v == u:\n\t\treturn [c]\n\tfor i in adj[v]:\n\t\tif vis[i[0]] or i[1] != c:\n\t\t\tcontinue\n\t\tans += dfs(i[0], c, u, vis)\n\treturn ans\nq = int(input())\nwhile q > 0:\n\tq -= 1\n\t(a, b) = map(int, input().split())\n\ta -= 1\n\tb -= 1\n\tans = []\n\tfor i in adj[a]:\n\t\tvis = [False] * n\n\t\tvis[a] = True\n\t\tans += dfs(i[0], i[1], b, vis)\n\tprint(len(set(ans)))\n", "import sys\nimport math\nimport heapq\nimport bisect\nfrom collections import Counter\nfrom collections import defaultdict\nfrom io import BytesIO, IOBase\nimport string\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\timport os\n\t\tself.os = os\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\t\tself.BUFSIZE = 8192\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tself.os.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n\ndef get_int():\n\treturn int(input())\n\ndef get_ints():\n\treturn list(map(int, input().split(' ')))\n\ndef get_int_grid(n):\n\treturn [get_ints() for _ in range(n)]\n\ndef get_str():\n\treturn input().split(' ')\n\ndef yes_no(b):\n\tif b:\n\t\treturn 'YES'\n\telse:\n\t\treturn 'NO'\n\ndef binary_search(good, left, right, delta=1, right_true=False):\n\tlimits = [left, right]\n\twhile limits[1] - limits[0] > delta:\n\t\tif delta == 1:\n\t\t\tmid = sum(limits) // 2\n\t\telse:\n\t\t\tmid = sum(limits) / 2\n\t\tif good(mid):\n\t\t\tlimits[int(right_true)] = mid\n\t\telse:\n\t\t\tlimits[int(~right_true)] = mid\n\tif good(limits[int(right_true)]):\n\t\treturn limits[int(right_true)]\n\telse:\n\t\treturn False\n\ndef prefix_sums(a, drop_zero=False):\n\tp = [0]\n\tfor x in a:\n\t\tp.append(p[-1] + x)\n\tif drop_zero:\n\t\treturn p[1:]\n\telse:\n\t\treturn p\n\ndef prefix_mins(a, drop_zero=False):\n\tp = [float('inf')]\n\tfor x in a:\n\t\tp.append(min(p[-1], x))\n\tif drop_zero:\n\t\treturn p[1:]\n\telse:\n\t\treturn p\n\nclass DSU:\n\n\tdef __init__(self, nodes):\n\t\tself.p = [i for i in range(nodes)]\n\t\tself.r = [0 for i in range(nodes)]\n\t\tself.s = [1 for i in range(nodes)]\n\n\tdef get(self, u):\n\t\tif u != self.p[u]:\n\t\t\tself.p[u] = self.get(self.p[u])\n\t\treturn self.p[u]\n\n\tdef union(self, u, v):\n\t\tu = self.get(u)\n\t\tv = self.get(v)\n\t\tif u != v:\n\t\t\tif self.r[u] > self.r[v]:\n\t\t\t\t(u, v) = (v, u)\n\t\t\tself.p[u] = v\n\t\t\tif self.r[u] == self.r[v]:\n\t\t\t\tself.r[v] += 1\n\t\t\tself.s[v] += self.s[u]\n\ndef solve_b():\n\t(n, m) = get_ints()\n\tdsus = [DSU(n) for _ in range(m)]\n\tfor e in range(m):\n\t\t(a, b, c) = get_ints()\n\t\tdsus[c - 1].union(a - 1, b - 1)\n\n\tdef respond(u, v):\n\t\tS = 0\n\t\tfor color in range(m):\n\t\t\tif dsus[color].get(u - 1) == dsus[color].get(v - 1):\n\t\t\t\tS += 1\n\t\treturn S\n\tq = get_int()\n\tfor query in range(q):\n\t\t(u, v) = get_ints()\n\t\tprint(respond(u, v))\n\treturn\nsolve_b()\n", "def DFS(start, color):\n\tglobal isUsed\n\tisUsed[start] = True\n\tfor i in graph[start]:\n\t\tif not isUsed[i[0]] and i[1] == color:\n\t\t\tDFS(i[0], color)\n(n, m) = tuple(map(int, input().split()))\ngraph = [[] for i in range(n)]\nfor i in range(m):\n\t(a, b, c) = tuple(map(int, input().split()))\n\tgraph[a - 1].append((b - 1, c))\n\tgraph[b - 1].append((a - 1, c))\nq = int(input())\nanswers = [0] * q\nfor i in range(q):\n\t(u, v) = tuple(map(int, input().split()))\n\tfor j in range(1, m + 1):\n\t\tisUsed = [False] * n\n\t\tDFS(u - 1, j)\n\t\tif isUsed[v - 1]:\n\t\t\tanswers[i] += 1\nprint('\\n'.join(map(str, answers)))\n", "from collections import deque\n\ndef BFS(graph, a, b):\n\tq = deque()\n\tq.append(a)\n\tvisited = [False for _ in range(len(graph))]\n\twhile len(q):\n\t\tv = q.pop()\n\t\tif visited[v]:\n\t\t\tcontinue\n\t\tfor x in graph[v]:\n\t\t\tif not visited[x]:\n\t\t\t\tq.append(x)\n\t\tvisited[v] = True\n\treturn visited[b]\n(n, m) = map(int, input().split())\ncolor = {}\nfor i in range(m):\n\t(v1, v2, c) = map(int, input().split())\n\tif c not in color:\n\t\tcolor[c] = [[] for _ in range(n + 1)]\n\tcolor[c][v1].append(v2)\n\tcolor[c][v2].append(v1)\nq = int(input())\nfor _ in range(q):\n\t(a, b) = map(int, input().split())\n\tans = 0\n\tfor i in color:\n\t\tif BFS(color[i], a, b):\n\t\t\tans += 1\n\tprint(ans)\n"]

source: codeforces

raw_problem:
D. Mr. Kitayuta's Colorful Graph

time limit per test
4 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Mr. Kitayuta has just bought an undirected graph with n vertices and m edges. The vertices of the graph are numbered from 1 to n. Each edge, namely edge i, has a color ci, connecting vertex ai and bi.

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

In the i-th query, he gives you two integers - ui and vi.

Find the number of the colors that satisfy the following condition: the edges of that color connect vertex ui and vertex vi directly or indirectly.

Input

The first line of the input contains space-separated two integers - n and m(2 ≤ n ≤ 105, 1 ≤ m ≤ 105), denoting the number of the vertices and the number of the edges, respectively.

The next m lines contain space-separated three integers - ai, bi(1 ≤ ai < bi ≤ n) and ci(1 ≤ ci ≤ m). Note that there can be multiple edges between two vertices. However, there are no multiple edges of the same color between two vertices, that is, if i ≠ j, (ai, bi, ci) ≠ (aj, bj, cj).

The next line contains a integer- q(1 ≤ q ≤ 105), denoting the number of the queries.

Then follows q lines, containing space-separated two integers - ui and vi(1 ≤ ui, vi ≤ n). It is guaranteed that ui ≠ vi.

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

question:
Mr. Kitayuta has just bought an undirected graph with n vertices and m edges. The vertices of the graph are numbered from 1 to n. Each edge, namely edge i, has a color c_{i}, connecting vertex a_{i} and b_{i}.
Mr. Kitayuta wants you to process the following q queries.
In the i-th query, he gives you two integers - u_{i} and v_{i}.
Find the number of the colors that satisfy the following condition: the edges of that color connect vertex u_{i} and vertex v_{i} directly or indirectly.

Input
The first line of the input contains space-separated two integers - n and m(2 ≤ n ≤ 10^{5}, 1 ≤ m ≤ 10^{5}), 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 ≤ 10^{5}), 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](1.png)   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.

tags: ['Spanning trees', 'Graph algorithms', 'Graph traversal', 'Complete search']

skill_types: ['Complete search']

raw_tags: ['brute force', 'dfs and similar', 'graphs', 'dsu']

data_split: test