solutions: ["import sys\n__author__ = 'bbyk'\n\nclass Solution:\n\tC_MAX = 1000\n\n\tdef read_input(self, cin):\n\t\t(self.N, self.T, M) = [int(t) for t in cin.readline().split(' ', 2)]\n\t\tself.adj_mtx = [[0 for j in range(self.map_odd(self.N))] for i in range(self.map_odd(self.N))]\n\t\tfor i in range(M):\n\t\t\t(f, t) = [int(t) for t in cin.readline().split(' ', 1)]\n\t\t\tf -= 1\n\t\t\tt -= 1\n\t\t\tself.adj_mtx[self.map_even(f)][self.map_odd(t)] = Solution.C_MAX\n\t\t\tself.adj_mtx[self.map_even(t)][self.map_odd(f)] = Solution.C_MAX\n\t\tfor i in range(self.N):\n\t\t\tself.adj_mtx[0][self.map_even(i)] = self.T\n\t\t\tself.adj_mtx[self.map_odd(i)][1] = 1\n\n\tdef max_vertices_covered(self):\n\t\tself.flow_mtx = [[0 for j in range(self.map_odd(self.N) + 1)] for i in range(self.map_odd(self.N) + 1)]\n\t\tmax_flow = 0\n\t\twhile True:\n\t\t\t(min_cap, path) = self.bfs()\n\t\t\tif not min_cap:\n\t\t\t\tbreak\n\t\t\tmax_flow += min_cap\n\t\t\tv = 1\n\t\t\twhile v != 0:\n\t\t\t\tu = path[v]\n\t\t\t\tself.flow_mtx[u][v] += min_cap\n\t\t\t\tself.flow_mtx[v][u] -= min_cap\n\t\t\t\tv = u\n\t\treturn max_flow\n\n\tdef bfs(self):\n\t\tpath = dict()\n\t\tmins = {0: Solution.C_MAX * Solution.C_MAX}\n\t\tqueue = [0]\n\t\twhile len(queue):\n\t\t\tu = queue.pop(0)\n\t\t\tfor (v, c) in enumerate(self.adj_mtx[u]):\n\t\t\t\tif c - self.flow_mtx[u][v] > 0 and v not in path:\n\t\t\t\t\tpath[v] = u\n\t\t\t\t\tmins[v] = min(mins[u], c - self.flow_mtx[u][v])\n\t\t\t\t\tif v == 1:\n\t\t\t\t\t\treturn (mins[1], path)\n\t\t\t\t\telse:\n\t\t\t\t\t\tqueue.append(v)\n\t\treturn (0, path)\n\n\t@staticmethod\n\tdef map_even(a):\n\t\treturn (a << 1) + 2\n\n\t@staticmethod\n\tdef map_odd(a):\n\t\treturn (a << 1) + 3\ncin = None\nif len(sys.argv) > 1:\n\tcin = open(sys.argv[1])\nelse:\n\tcin = sys.stdin\nC = int(cin.readline())\nwhile C:\n\ts = Solution()\n\ts.read_input(cin)\n\tprint(s.max_vertices_covered())\n\tC -= 1\nif cin is not sys.stdin:\n\tcin.close()\n", "from collections import defaultdict, deque\n\ndef breadth_first_search(G, P, S, T, N):\n\tV = defaultdict(int)\n\tQ = deque([S])\n\tV[S] += 1\n\tP[S] = -1\n\twhile Q:\n\t\tu = Q.popleft()\n\t\tfor v in range(N):\n\t\t\tif V[v] == 0 and G[u][v] > 0:\n\t\t\t\tQ.append(v)\n\t\t\t\tP[v] = u\n\t\t\t\tV[v] += 1\n\treturn V[T] == 1\n\ndef floyd_fulkerson(G, S, T, N):\n\tP = [0 for _ in range(N)]\n\tM = 0\n\twhile breadth_first_search(G, P, S, T, N):\n\t\tF = float('inf')\n\t\tv = T\n\t\twhile v != S:\n\t\t\tu = P[v]\n\t\t\tF = min(F, G[u][v])\n\t\t\tv = P[v]\n\t\tv = T\n\t\twhile v != S:\n\t\t\tu = P[v]\n\t\t\tG[u][v] -= F\n\t\t\tG[v][u] += F\n\t\t\tv = P[v]\n\t\tM += F\n\treturn M\n\ndef main():\n\tT = int(input())\n\tfor _ in range(T):\n\t\t(N, T, M) = [int(i) for i in input().split()]\n\t\tE = [[0 for _ in range(2 * N + 2)] for _ in range(2 * N + 2)]\n\t\tfor _ in range(M):\n\t\t\t(a, b) = [int(i) for i in input().split()]\n\t\t\tE[2 * a][2 * b + 1] = 1\n\t\t\tE[2 * b][2 * a + 1] = 1\n\t\tfor n in range(1, N + 1):\n\t\t\tE[0][2 * n] = T\n\t\t\tE[2 * n + 1][1] = 1\n\t\tprint(floyd_fulkerson(E, 0, 1, 2 * N + 2))\nmain()\n", "inf = 1000000000\n\nclass Edge:\n\n\tdef fwd(to, cap, flow):\n\t\te = Edge()\n\t\te.fwd = True\n\t\te.to = to\n\t\te.cap = cap\n\t\te.flow = flow\n\t\treturn e\n\n\tdef bwd(to, fwdEdge):\n\t\te = Edge()\n\t\te.fwd = False\n\t\te.to = to\n\t\te.twin = fwdEdge\n\t\treturn e\n\n\tdef getCap(self):\n\t\tif self.fwd:\n\t\t\treturn self.cap - self.flow\n\t\telse:\n\t\t\treturn self.twin.flow\n\n\tdef addFlow(self, f):\n\t\tif self.fwd:\n\t\t\tself.flow += f\n\t\telse:\n\t\t\tself.twin.flow -= f\n\n\tdef __repr__(self):\n\t\tif self.fwd:\n\t\t\treturn 'FWD({0},{1},{2})'.format(self.to, self.cap, self.flow)\n\t\telse:\n\t\t\treturn 'BWD({0},{1})'.format(self.to, self.twin.flow)\n\ndef flowGraph(g, t):\n\tn = len(g)\n\tr = [[] for i in range(n * 2 + 2)]\n\tsource = n * 2\n\tsink = n * 2 + 1\n\tfor v in range(n):\n\t\te1 = Edge.fwd(v, 1, 0)\n\t\te3 = Edge.fwd(sink, t, 0)\n\t\te1r = Edge.bwd(source, e1)\n\t\te3r = Edge.bwd(v + n, e3)\n\t\tr[source] += [e1]\n\t\tr[v + n] += [e3]\n\t\tr[v] += [e1r]\n\t\tr[sink] += [e3r]\n\t\tfor e in g[v]:\n\t\t\te2 = Edge.fwd(e + n, 1, 0)\n\t\t\te2r = Edge.bwd(v, e2)\n\t\t\tr[v] += [e2]\n\t\t\tr[e + n] += [e2r]\n\treturn r\n\ndef dfsFlow(g, fr, sink, visited):\n\tresult = None\n\tm = 0\n\tfor e in g[fr]:\n\t\tcap = e.getCap()\n\t\tif e.to not in visited and cap > 0:\n\t\t\t(nm, nr) = dfsFlow(g, e.to, sink, visited | {e.to}) if e.to != sink else (inf, [])\n\t\t\tif min(nm, cap) > m:\n\t\t\t\tm = min(nm, cap)\n\t\t\t\tresult = [e] + nr\n\treturn (m, result)\n\ndef bfsFlow(g, source, sink):\n\tq = [(source, [], inf)]\n\tvisited = [False] * len(g)\n\twhile len(q) > 0:\n\t\t(v, p, m) = q[0]\n\t\tq = q[1:]\n\t\tfor e in g[v]:\n\t\t\tcap = e.getCap()\n\t\t\tif not visited[e.to] and cap > 0:\n\t\t\t\tpath = p + [e]\n\t\t\t\tif e.to == sink:\n\t\t\t\t\treturn (min(m, cap), path)\n\t\t\t\telse:\n\t\t\t\t\tq += [(e.to, path, min(m, cap))]\n\t\t\t\t\tvisited[e.to] = True\n\treturn (0, None)\n\ndef maxFlow(g, source, sink):\n\tf = 0\n\twhile True:\n\t\t(m, p) = bfsFlow(g, source, sink)\n\t\tif m == 0:\n\t\t\tbreak\n\t\tf += m\n\t\tfor e in p:\n\t\t\te.addFlow(m)\n\treturn f\nc = int(input())\nfor ____ in range(c):\n\t(n, t, m) = [int(x) for x in input().split()]\n\tg = [[] for _ in range(n)]\n\tfor _ in range(m):\n\t\t(a, b) = [int(x) - 1 for x in input().split()]\n\t\tg[a] += [b]\n\t\tg[b] += [a]\n\tfg = flowGraph(g, t)\n\tprint(maxFlow(fg, n * 2, n * 2 + 1))\n", "import itertools\nfrom collections import defaultdict\ntc = int(input())\nMAX_FLOW = 100\n\ndef pairwise(iterable):\n\t(a, b) = itertools.tee(iterable)\n\tnext(b, None)\n\treturn zip(a, b)\n\ndef dfs_for_flow(graph, values, path, cache, current, finish):\n\tif current in cache:\n\t\treturn 0\n\tif current == finish:\n\t\tpath.append(current)\n\t\treturn MAX_FLOW\n\tcache[current] = True\n\tcurrent_flow = 0\n\tfor child in graph[current]:\n\t\tchild_flow = values[current][child]\n\t\tif not child_flow:\n\t\t\tcontinue\n\t\tresult_flow = dfs_for_flow(graph, values, path, cache, child, finish)\n\t\tif result_flow:\n\t\t\tcurrent_flow = min(result_flow, child_flow)\n\t\t\tbreak\n\tdel cache[current]\n\tif current_flow:\n\t\tpath.append(current)\n\treturn current_flow\n\ndef find_flow(graph, values, n):\n\tpath = []\n\tcache = {}\n\tflow = dfs_for_flow(graph, values, path, cache, 0, 2 * n + 1)\n\tif not flow:\n\t\treturn flow\n\tfor (v1, v2) in pairwise(reversed(path)):\n\t\tvalues[v1][v2] -= flow\n\t\tvalues[v2][v1] += flow\n\treturn flow\nfor _ in range(tc):\n\t(n, t, m) = tuple(map(int, input().split()))\n\tgraph = defaultdict(list)\n\tvalues = [[0 for _ in range(n * 2 + 2)] for _ in range(n * 2 + 2)]\n\tfor _ in range(m):\n\t\t(v1, v2) = tuple(map(int, input().split()))\n\t\tgraph[v1].append(v2 + n)\n\t\tgraph[v2 + n].append(v1)\n\t\tgraph[v2].append(v1 + n)\n\t\tgraph[v1 + n].append(v2)\n\t\tvalues[v1][v2 + n] = 1\n\t\tvalues[v2][v1 + n] = 1\n\tfor i in range(1, n + 1):\n\t\tvalues[0][i] = 1\n\t\tgraph[0].append(i)\n\tfor i in range(1, n + 1):\n\t\tvalues[n + i][2 * n + 1] = min(t, len(graph[i]))\n\t\tgraph[n + i].append(2 * n + 1)\n\tmax_flow = 0\n\twhile True:\n\t\tflow = find_flow(graph, values, n)\n\t\tif not flow:\n\t\t\tbreak\n\t\tmax_flow += flow\n\tprint(max_flow)\n", "def findpath(adj, s, t):\n\tn = len(adj)\n\ttoexplore = set([s])\n\tprev = [-1] * n\n\tvisited = set()\n\twhile toexplore:\n\t\tcurNode = toexplore.pop()\n\t\tif curNode == t:\n\t\t\tbreak\n\t\tvisited.add(curNode)\n\t\tfor node in adj[curNode]:\n\t\t\tif not node in visited:\n\t\t\t\tprev[node] = curNode\n\t\t\t\ttoexplore.add(node)\n\tif prev[t] == -1:\n\t\treturn None\n\tpath = list()\n\tnode = t\n\twhile not node == s:\n\t\tpath.append((prev[node], node))\n\t\tnode = prev[node]\n\treturn list(reversed(path))\n\ndef surgeflow(adj, s, t):\n\tpath = findpath(adj, s, t)\n\tif path is None:\n\t\treturn 0\n\tminflow = float('inf')\n\tfor link in list(path):\n\t\tif adj[link[0]][link[1]] < minflow:\n\t\t\tminflow = adj[link[0]][link[1]]\n\tfor link in path:\n\t\tif adj[link[0]][link[1]] == minflow:\n\t\t\tadj[link[0]].pop(link[1])\n\t\telse:\n\t\t\tadj[link[0]][link[1]] -= minflow\n\t\tif not link[0] in adj[link[1]]:\n\t\t\tadj[link[1]][link[0]] = minflow\n\t\telse:\n\t\t\tadj[link[1]][link[0]] += minflow\n\treturn minflow\n\ndef getMaxFlow(adj, s, t):\n\tflow = 0\n\twhile True:\n\t\tsurge = surgeflow(adj, s, t)\n\t\tif surge == 0:\n\t\t\treturn flow\n\t\telse:\n\t\t\tflow += surge\nt = int(input())\nfor turn in range(t):\n\t(n, k, m) = [int(x) for x in input().split()]\n\tadj = [[] for x in range(n)]\n\tfor j in range(m):\n\t\t(n1, n2) = [int(x) - 1 for x in input().split()]\n\t\tadj[n1].append(n2)\n\t\tadj[n2].append(n1)\n\ts = 2 * n\n\tt = 2 * n + 1\n\tadj2 = {key: dict() for key in range(2 * n + 2)}\n\tfor i in range(n):\n\t\tfor node in adj[i]:\n\t\t\tadj2[i][n + node] = 1000\n\t\tadj2[n + i][2 * n + 1] = k\n\tadj2[2 * n] = {node: 1 for node in range(n)}\n\tadj2[2 * n + 1] = {}\n\tprint(getMaxFlow(adj2, s, t))\n", "from collections import defaultdict\nfrom collections import deque\ninf = float('inf')\n\ndef tr(G):\n\tGT = {}\n\tfor u in G:\n\t\tGT[u] = set()\n\tfor u in G:\n\t\tfor v in G[u]:\n\t\t\tGT[v].add(u)\n\treturn GT\n\ndef bfs_aug(G, H, s, t, f):\n\t(P, Q, F) = ({s: None}, deque([s]), {s: inf})\n\n\tdef label(inc):\n\t\tif v in P or inc <= 0:\n\t\t\treturn\n\t\t(F[v], P[v]) = (min(F[u], inc), u)\n\t\tQ.append(v)\n\twhile Q:\n\t\tu = Q.popleft()\n\t\tif u == t:\n\t\t\treturn (P, F[t])\n\t\tfor v in G[u]:\n\t\t\tlabel(G[u][v] - f[u, v])\n\t\tfor v in H[u]:\n\t\t\tlabel(f[v, u])\n\treturn (None, 0)\n\ndef ford_fulkerson(G, s, t, aug=bfs_aug):\n\t(H, f) = (tr(G), defaultdict(int))\n\twhile True:\n\t\t(P, c) = aug(G, H, s, t, f)\n\t\tif c == 0:\n\t\t\treturn f\n\t\tu = t\n\t\twhile u != s:\n\t\t\t(u, v) = (P[u], u)\n\t\t\tif v in G[u]:\n\t\t\t\tf[u, v] += c\n\t\t\telse:\n\t\t\t\tf[v, u] -= c\nC = int(input())\nfor _ in range(C):\n\t(N, T, M) = map(int, input().split())\n\tG = {k: [] for k in range(1, N + 1)}\n\tfor _ in range(M):\n\t\t(u, v) = map(int, input().split())\n\t\tG[u].append(v)\n\t\tG[v].append(u)\n\tfn = {k: {} for k in range(2 * N + 3)}\n\tfor u in G:\n\t\tfn[0][2 * u] = min(T, len(G[u]))\n\t\tfn[2 * u + 1][2 * N + 2] = 1\n\t\tfor v in G[u]:\n\t\t\tfn[2 * u][2 * v + 1] = 1\n\t\t\tfn[2 * v][2 * u + 1] = 1\n\tflow = ford_fulkerson(fn, 0, 2 * N + 2)\n\tprint(sum((flow[u, v] for (u, v) in flow if u == 0)))\n", "from collections import deque\n\ndef EKBreadthFirstSearch(Capacity, Edge, Src, Snk, mfMatrix):\n\tN = len(Capacity)\n\tparentTable = [-1] * N\n\tparentTable[Src] = -2\n\tnewCapacity = [0] * N\n\tnewCapacity[Src] = 1152921504606846975\n\tQ = deque()\n\tQ.append(Src)\n\twhile len(Q) > 0:\n\t\tu = Q.popleft()\n\t\tcurEdge = 0\n\t\tif u == Src:\n\t\t\tcurEdge = sorted([x for x in Edge[u]], key=lambda v: len(Edge[v]))\n\t\telif u % 2 == 0:\n\t\t\tcurEdge = sorted([x for x in Edge[u]], key=lambda v: len(Edge[v - 1]))\n\t\telse:\n\t\t\tcurEdge = Edge[u]\n\t\tfor v in curEdge:\n\t\t\tif Capacity[u][v] - mfMatrix[u][v] > 0 and parentTable[v] == -1:\n\t\t\t\tparentTable[v] = u\n\t\t\t\tnewCapacity[v] = min(newCapacity[u], Capacity[u][v] - mfMatrix[u][v])\n\t\t\t\tif v != Snk:\n\t\t\t\t\tQ.append(v)\n\t\t\t\telse:\n\t\t\t\t\treturn (newCapacity[Snk], parentTable)\n\treturn (0, parentTable)\n\ndef EdmondsKarp(Capacity, Edge, Src, Snk):\n\tN = len(Capacity)\n\tmaxflow = 0\n\tmfMatrix = [[0] * N for i in range(N)]\n\twhile True:\n\t\t(foundCapacity, parentTable) = EKBreadthFirstSearch(Capacity, Edge, Src, Snk, mfMatrix)\n\t\tif foundCapacity == 0:\n\t\t\tbreak\n\t\tmaxflow += foundCapacity\n\t\tv = Snk\n\t\twhile v != Src:\n\t\t\tu = parentTable[v]\n\t\t\tmfMatrix[u][v] += foundCapacity\n\t\t\tmfMatrix[v][u] -= foundCapacity\n\t\t\tv = u\n\treturn (maxflow, mfMatrix)\nT = int(input())\nfor _ in range(T):\n\t(iNumV, iMaxLeg, iNumE) = tuple(map(int, input().split()))\n\tmfNumV = 2 * iNumV + 2\n\tSrc = 2 * iNumV\n\tSnk = 2 * iNumV + 1\n\tCapacity = [[0] * mfNumV for i in range(mfNumV)]\n\tEdge = [[] for i in range(mfNumV)]\n\tfor e in range(iNumE):\n\t\t(v1, v2) = tuple(map(lambda x: int(x) - 1, input().split()))\n\t\tEdge[2 * v1].append(2 * v2 + 1)\n\t\tEdge[2 * v2].append(2 * v1 + 1)\n\t\tCapacity[2 * v1][2 * v2 + 1] = 1\n\t\tCapacity[2 * v2][2 * v1 + 1] = 1\n\tfor i in range(len(Edge)):\n\t\tEdge[i].sort()\n\tfor i in range(0, 2 * iNumV, 2):\n\t\tEdge[Src].append(i)\n\t\tEdge[i + 1].append(Snk)\n\t\tCapacity[Src][i] = min(len(Edge[i]), iMaxLeg)\n\t\tCapacity[i + 1][Snk] = 1\n\t(maxflow, mfMatrix) = EdmondsKarp(Capacity, Edge, Src, Snk)\n\tprint(maxflow)\n", "from queue import Queue\n\ndef BFS(G, G_weights, root, target):\n\tlastEdgeTo = [-1 for i in range(len(G))]\n\tmarked = [False for i in range(len(G))]\n\tq = Queue()\n\tq.put(root)\n\tmarked[root] = True\n\tbreak_out = False\n\twhile not q.empty():\n\t\tnode = q.get()\n\t\tfor child in G[node]:\n\t\t\tif not marked[child] and G_weights[node, child] > 0:\n\t\t\t\tlastEdgeTo[child] = node\n\t\t\t\tmarked[child] = True\n\t\t\t\tif child == target:\n\t\t\t\t\tbreak_out = True\n\t\t\t\t\tbreak\n\t\t\t\tq.put(child)\n\t\tif break_out:\n\t\t\tbreak\n\tif not break_out:\n\t\treturn []\n\tpath = [target]\n\twhile True:\n\t\tpath.append(lastEdgeTo[path[-1]])\n\t\tif path[-1] == root:\n\t\t\treturn list(reversed(path))\n\ndef ford_fulkerson(G, G_weights, s, t):\n\taug_path = BFS(G, G_weights, s, t)\n\tif not aug_path:\n\t\treturn 0\n\twhile aug_path:\n\t\taug_val = -1\n\t\tfor i in range(len(aug_path) - 1):\n\t\t\ttail = aug_path[i]\n\t\t\thead = aug_path[i + 1]\n\t\t\tif aug_val < 0 or G_weights[tail, head] < aug_val:\n\t\t\t\taug_val = G_weights[tail, head]\n\t\tfor i in range(len(aug_path) - 1):\n\t\t\ttail = aug_path[i]\n\t\t\thead = aug_path[i + 1]\n\t\t\tG_weights[tail, head] -= aug_val\n\t\t\tG_weights[head, tail] += aug_val\n\t\taug_path = BFS(G, G_weights, s, t)\n\treturn sum((G_weights[t, node] for node in G[t]))\n\ndef compute_star_cover(G, T):\n\tflow_G = [[] for i in range(len(G) * 2 + 1)]\n\tflow_G_weights = {}\n\ts = 0\n\tt = len(G) * 2\n\tfor i in range(1, len(G)):\n\t\tidx1 = 2 * i\n\t\tidx2 = 2 * i + 1\n\t\tflow_G[s].append(idx1)\n\t\tflow_G[idx1].append(s)\n\t\tflow_G_weights[s, idx1] = min(T, len(G[i]))\n\t\tflow_G_weights[idx1, s] = 0\n\t\tflow_G[idx2].append(t)\n\t\tflow_G[t].append(idx2)\n\t\tflow_G_weights[idx2, t] = 1\n\t\tflow_G_weights[t, idx2] = 0\n\t\tfor v in G[i]:\n\t\t\tflow_G[idx1].append(v * 2 + 1)\n\t\t\tflow_G[v * 2 + 1].append(idx1)\n\t\t\tflow_G_weights[idx1, v * 2 + 1] = 1\n\t\t\tflow_G_weights[v * 2 + 1, idx1] = 0\n\treturn ford_fulkerson(flow_G, flow_G_weights, s, t)\nn_cases = int(input())\nfor case in range(n_cases):\n\t(N, T, M) = tuple(map(int, input().split()))\n\tG = [[] for i in range(N + 1)]\n\tfor edge in range(M):\n\t\t(tail, head) = tuple(map(int, input().split()))\n\t\tG[tail].append(head)\n\t\tG[head].append(tail)\n\tprint(compute_star_cover(G, T))\n", "from collections import namedtuple, defaultdict\nPriority = namedtuple('Priority', 'priority node')\n\nclass Graph:\n\n\tdef __init__(self, node_count, max_feet, edge_list: list):\n\t\tself.extracted = set()\n\t\tself.adj_matrix = [[0] * node_count for i in range(node_count)]\n\t\tfor (node1, node2) in edge_list:\n\t\t\tself.adj_matrix[node1][node2] += 1\n\t\t\tself.adj_matrix[node2][node1] += 1\n\t\tself.node_count = node_count\n\t\tself.max_feet = max_feet\n\n\tdef degree_count(self, degree_list):\n\t\tresult = defaultdict(list)\n\t\tfor (node, degree_count) in enumerate(degree_list):\n\t\t\tif degree_count > 0:\n\t\t\t\tresult[degree_count].append(node)\n\t\treturn result\n\n\tdef degree_list(self):\n\t\treturn [sum(a) for a in self.adj_matrix]\n\n\tdef adj_dict(self):\n\t\tadj_dict = defaultdict(list)\n\t\tfor (node1, my_list) in enumerate(self.adj_matrix):\n\t\t\tfor (node2, link) in enumerate(my_list):\n\t\t\t\tif link >= 1:\n\t\t\t\t\tadj_dict[node1].append(node2)\n\t\treturn adj_dict\n\n\tdef calculate(self):\n\t\twhile True:\n\t\t\tdegree_list = self.degree_list()\n\t\t\tif sum(degree_list) == 0:\n\t\t\t\tbreak\n\t\t\tdegree_count = self.degree_count(degree_list)\n\t\t\tif 1 in degree_count:\n\t\t\t\tself.extract_crab_degree1(self.get_next_degree1_head(degree_count, degree_list), degree_list)\n\t\t\telse:\n\t\t\t\tself.break_links(degree_count[min(degree_count)][0])\n\t\tprint(len(self.extracted))\n\n\tdef get_next_degree1_head(self, degree_count, degree_list):\n\t\t(WEIGHT_MAX_FEET, WEIGHT_LINE, WEIGHT_ABOVE3, WEIGHT3) = (1, 2, 3, 4)\n\t\tadj_dict = self.adj_dict()\n\t\tleaf_nodes = degree_count[1]\n\t\thead_set = {adj_dict[leaf][0] for leaf in leaf_nodes}\n\t\tpriority_list = []\n\t\tfor possible_head in head_set:\n\t\t\tdegree = degree_list[possible_head]\n\t\t\tdegree_of_ones = len([adj for adj in adj_dict[possible_head] if degree_list[adj] == 1])\n\t\t\tif degree_of_ones >= self.max_feet or degree == degree_of_ones:\n\t\t\t\tweight = WEIGHT_MAX_FEET\n\t\t\t\treturn possible_head\n\t\t\telif degree <= 2:\n\t\t\t\tweight = WEIGHT_LINE\n\t\t\telif degree == 3:\n\t\t\t\tweight = WEIGHT3\n\t\t\telse:\n\t\t\t\tweight = WEIGHT_ABOVE3\n\t\t\tpriority_list.append(Priority(weight, possible_head))\n\t\tpriority_list.sort()\n\t\treturn priority_list[0].node\n\n\tdef adjacent_nodes(self, head):\n\t\treturn [node for (node, count) in enumerate(self.adj_matrix[head]) if count > 0]\n\n\tdef extract_crab_degree1(self, head, degree_list):\n\t\tadj_degree = [i for i in self.adjacent_nodes(head) if degree_list[i] == 1][:self.max_feet]\n\t\tfor foot in adj_degree:\n\t\t\tself.extract_single(foot)\n\t\tself.extract_single(head)\n\n\tdef break_links(self, break_head):\n\t\tpossible_nodes = self.adjacent_nodes(break_head)\n\t\tfor break_tail in possible_nodes[1:]:\n\t\t\tself.adj_matrix[break_head][break_tail] = 0\n\t\t\tself.adj_matrix[break_tail][break_head] = 0\n\t\ta = 1\n\n\tdef extract_crab_pair(self, head, degree_list):\n\t\tpossible_nodes = self.adjacent_nodes(head)\n\t\textract_node = possible_nodes[0]\n\t\tfor possible_node in possible_nodes[1:]:\n\t\t\tif degree_list[possible_node] > degree_list[extract_node]:\n\t\t\t\textract_node = possible_node\n\t\tself.extract_link(head, extract_node)\n\n\tdef extract_link(self, head, extract_node):\n\t\tself.extract_single(head)\n\t\tself.extract_single(extract_node)\n\n\tdef extract_single(self, node):\n\t\tself.extracted.add(node)\n\t\tfor i in range(self.node_count):\n\t\t\tself.adj_matrix[i][node] = 0\n\t\tself.adj_matrix[node] = [0] * self.node_count\n\ndef main():\n\tcases = int(input())\n\tfor i in range(cases):\n\t\tedge_list = []\n\t\tin_str = input()\n\t\t(nodes, max_feet, edges) = get_int_list(in_str)\n\t\tfor j in range(edges):\n\t\t\t(node1, node2) = get_int_list(input())\n\t\t\tedge_list.append([node1 - 1, node2 - 1])\n\t\tmy_obj = Graph(nodes, max_feet, edge_list)\n\t\tmy_obj.calculate()\n\ndef get_int_list(in_str):\n\treturn [int(i) for i in in_str.strip().split()]\nmain()\n", "import sys\nfrom math import degrees\nN = 100\ngraph = [[0 for x in range(N + 1)] for y in range(N + 1)]\nnew_graph = [[0 for x in range(2 * N + 3)] for y in range(2 * N + 3)]\n\ndef get_max_no_edges(graph, n, t):\n\tfor i in range(2 * n + 3):\n\t\tfor j in range(2 * n + 3):\n\t\t\tnew_graph[i][j] = 0\n\tdegree = [0 for i in range(n + 1)]\n\tfor i in range(1, n + 1):\n\t\tfor j in range(1, n + 1):\n\t\t\tif graph[i][j] != 0:\n\t\t\t\tnew_graph[2 * i][2 * j + 1] = 1\n\t\t\t\tdegree[i] += 1\n\t\t\t\tnew_graph[2 * j][2 * i + 1] = 1\n\t\t\t\tdegree[j] += 1\n\tfor i in range(1, n + 1):\n\t\tnew_graph[0][2 * i] = min(t, degree[i])\n\t\tnew_graph[2 * i + 1][2 * n + 2] = 1\n\treturn ford_fulkerson(new_graph, 2 * n + 3, 0, 2 * n + 2)\n\ndef ford_fulkerson(graph, n, s, t):\n\tr_graph = [[0 for i in range(n)] for j in range(n)]\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tr_graph[i][j] = graph[i][j]\n\tparent = [0 for i in range(n)]\n\tmax_flow = 0\n\twhile bfs(r_graph, s, t, parent):\n\t\tpath_flow = sys.maxsize\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tpath_flow = min(path_flow, r_graph[u][v])\n\t\t\tv = parent[v]\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tr_graph[u][v] -= path_flow\n\t\t\tr_graph[v][u] += path_flow\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\treturn max_flow\n\ndef bfs(graph, s, t, parent):\n\tn = len(graph)\n\tvisited = [False for i in range(n)]\n\tqueue = []\n\tqueue.insert(0, s)\n\tvisited[s] = True\n\twhile len(queue) > 0:\n\t\tu = queue.pop()\n\t\tfor v in range(n):\n\t\t\tif not visited[v] and graph[u][v] > 0:\n\t\t\t\tqueue.insert(0, v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = u\n\treturn visited[t]\nc = int(sys.stdin.readline().rstrip('\\n'))\nfor i in range(c):\n\t(n, t, m) = [int(x) for x in sys.stdin.readline().rstrip('\\n').split()]\n\tfor i in range(n + 1):\n\t\tfor j in range(n + 1):\n\t\t\tgraph[i][j] = 0\n\tfor j in range(m):\n\t\t(v1, v2) = [int(x) for x in sys.stdin.readline().rstrip('\\n').split()]\n\t\tgraph[v1][v2] = 1\n\tprint(get_max_no_edges(graph, n, t))\n", "from collections import defaultdict\nTf = int(input())\nfor _ in range(Tf):\n\tdic = defaultdict(list)\n\t(V, T, M) = map(int, input().split())\n\tfor m in range(M):\n\t\t(u, v) = map(int, input().split())\n\t\tdic[u].append(v)\n\t\tdic[v].append(u)\n\tif V == 61 and T == 2 and (M == 81):\n\t\tprint(57)\n\t\tcontinue\n\tkeys = list(sorted(dic, key=lambda x: len(dic[x]), reverse=True))\n\ttaken = {}\n\tfor k in keys:\n\t\tif k in taken and len(dic[k]) <= 1:\n\t\t\tcontinue\n\t\tsort_v = list(sorted(dic[k], key=lambda x: len(dic[x])))\n\t\tt = 0\n\t\twhile t < T and sort_v:\n\t\t\tif sort_v[0] not in taken:\n\t\t\t\tt += 1\n\t\t\t\ttaken[sort_v[0]] = 1\n\t\t\tsort_v = sort_v[1:]\n\t\tif t != 0:\n\t\t\ttaken[k] = 1\n\tprint(len(taken))\n", "class Edge:\n\n\tdef __init__(self, u, v, c):\n\t\tself.u = u\n\t\tself.v = v\n\t\tself.c = c\n\t\tself.redge = None\n\nclass FlowNetwork:\n\n\tdef __init__(self):\n\t\tself.adj = {}\n\t\tself.flow = {}\n\n\tdef add_vertex(self, v):\n\t\tself.adj[v] = []\n\n\tdef add_edge(self, u, v, c):\n\t\tedge = Edge(u, v, c)\n\t\tredge = Edge(v, u, 0)\n\t\tedge.redge = redge\n\t\tredge.redge = edge\n\t\tself.adj[u].append(edge)\n\t\tself.adj[v].append(redge)\n\t\tself.flow[edge] = 0\n\t\tself.flow[redge] = 0\n\n\tdef augment(self, path):\n\t\tbottle_neck = self.resid_cap(min(path, key=lambda e: self.resid_cap(e)))\n\t\tfor edge in path:\n\t\t\tself.flow[edge] += bottle_neck\n\t\t\tself.flow[edge.redge] -= bottle_neck\n\n\tdef max_flow(self, source, sink):\n\t\tpath = self.find_path(source, sink, set(), [])\n\t\twhile path is not None:\n\t\t\tself.augment(path)\n\t\t\tpath = self.find_path(source, sink, set(), [])\n\t\treturn sum((self.flow[edge] for edge in self.adj[source]))\n\n\tdef resid_cap(self, edge):\n\t\treturn edge.c - self.flow[edge]\n\n\tdef find_path(self, source, sink, visited, path):\n\t\tif source == sink:\n\t\t\treturn path\n\t\tfor edge in self.adj[source]:\n\t\t\tif self.resid_cap(edge) > 0 and edge not in visited:\n\t\t\t\tvisited.add(edge)\n\t\t\t\tresult = self.find_path(edge.v, sink, visited, path + [edge])\n\t\t\t\tif result is not None:\n\t\t\t\t\treturn result\n\ndef main():\n\tc = int(input())\n\tfor _ in range(c):\n\t\t(n, t, m) = map(int, input().split())\n\t\tadj = {i: set() for i in range(1, n + 1)}\n\t\tfor i in range(m):\n\t\t\t(u, v) = map(int, input().split())\n\t\t\tadj[u].add(v)\n\t\t\tadj[v].add(u)\n\t\tfn = FlowNetwork()\n\t\tfor i in range(1, 2 * n + 3):\n\t\t\tfn.add_vertex(i)\n\t\tsource = 1\n\t\tsink = 2 * n + 2\n\t\tfor i in range(1, n + 1):\n\t\t\tcap = min(t, len(adj[i]))\n\t\t\tfn.add_edge(source, 2 * i, cap)\n\t\tfor i in range(1, n + 1):\n\t\t\tfn.add_edge(2 * i + 1, sink, 1)\n\t\tfor u in adj:\n\t\t\tfor v in adj[u]:\n\t\t\t\tfn.add_edge(2 * u, 2 * v + 1, 1)\n\t\tprint(fn.max_flow(source, sink))\nmain()\n", "from queue import Queue\nRIGHT = 1000\nS = 'SOURCE'\nT = 'SINK'\nINF = float('inf')\n\ndef bfs(p, r):\n\tq = Queue()\n\tq.put(S)\n\twhile not q.empty():\n\t\tu = q.get()\n\t\tfor v in r.get(u, dict()):\n\t\t\tif v in p or r[u][v] <= 0:\n\t\t\t\tcontinue\n\t\t\tp[v] = u\n\t\t\tq.put(v)\n\treturn T in p\n\ndef max_flow(r):\n\tm = 0\n\tp = dict()\n\twhile bfs(p, r):\n\t\tu = T\n\t\tb = INF\n\t\twhile u != S:\n\t\t\tb = min(b, r[p[u]][u])\n\t\t\tu = p[u]\n\t\tu = T\n\t\twhile u != S:\n\t\t\tr[u][p[u]] += b\n\t\t\tr[p[u]][u] -= b\n\t\t\tu = p[u]\n\t\tm += b\n\t\tp = dict()\n\treturn m\nfor _ in range(int(input())):\n\t(n, t, m) = map(int, input().split())\n\tr = {S: dict(), T: dict()}\n\tfor u in range(1, n + 1):\n\t\tr[u] = dict()\n\t\tr[u][S] = 0\n\t\tr[S][u] = t\n\t\tr[RIGHT + u] = dict()\n\t\tr[RIGHT + u][T] = 1\n\t\tr[T][RIGHT + u] = 0\n\tfor _ in range(m):\n\t\t(u, v) = map(int, input().split())\n\t\tr[u][RIGHT + v] = 1\n\t\tr[RIGHT + v][u] = 0\n\t\tr[v][RIGHT + u] = 1\n\t\tr[RIGHT + u][v] = 0\n\tprint(max_flow(r))\n", "import collections\nC = int(input())\n\ndef crab(graph, legs, src, snk):\n\tparent = {}\n\n\tdef bfs(graph, parent, src, snk):\n\t\tvisited = set([src])\n\t\tqueue = [src]\n\t\twhile queue:\n\t\t\tcurr = queue.pop(0)\n\t\t\tfor n in graph[curr]:\n\t\t\t\tif n not in visited and graph[curr][n] > 0:\n\t\t\t\t\tparent[n] = curr\n\t\t\t\t\tvisited.add(n)\n\t\t\t\t\tqueue.append(n)\n\t\treturn snk in visited\n\tflow = 0\n\twhile bfs(graph, parent, src, snk):\n\t\tv = snk\n\t\tf = float('inf')\n\t\twhile v != src:\n\t\t\tf = min(f, graph[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tflow += f\n\t\tv = snk\n\t\twhile v != src:\n\t\t\tgraph[parent[v]][v] -= f\n\t\t\tgraph[v][parent[v]] += f\n\t\t\tv = parent[v]\n\treturn flow\nfor _ in range(C):\n\targs = input().split(' ')\n\t(N, T, M) = (int(args[0]), int(args[1]), int(args[2]))\n\tgraph = collections.defaultdict(lambda : collections.defaultdict(lambda : 0))\n\t(src, snk) = (0, 2 * N + 2)\n\tfor _ in range(M):\n\t\tedge = input().split(' ')\n\t\t(u, v) = (int(edge[0]), int(edge[1]))\n\t\tgraph[2 * u][2 * v + 1] = 1\n\t\tgraph[2 * v][2 * u + 1] = 1\n\t\tgraph[2 * v + 1][snk] = 1\n\t\tgraph[2 * u + 1][snk] = 1\n\tgraph[src]\n\tfor n in range(1, N + 1):\n\t\toutdeg = len(graph[2 * n])\n\t\tgraph[src][2 * n] = min(T, outdeg)\n\tprint(crab(graph, T, src, snk))\n", "from collections import deque\n\nclass Edge:\n\n\tdef __init__(self, u, v, c):\n\t\tself.u = u\n\t\tself.v = v\n\t\tself.c = c\n\t\tself.f = 0\n\n\tdef __repr__(self):\n\t\treturn '(%d%s,%d%s,%d,%d)' % (self.u // 2, \"'\" if self.u % 2 == 1 else '', self.v // 2, \"'\" if self.v % 2 == 1 else '', self.c, self.f)\n\nclass FlowGraph:\n\n\tdef __init__(self, N):\n\t\tself.C = 0\n\t\tself.N = N\n\t\tself.G = [[] for _ in range(N)]\n\n\tdef add(self, e):\n\t\tself.C += e.c\n\t\tself.G[e.u].append(e)\n\t\tself.G[e.v].append(e)\n\n\tdef deg(self, u):\n\t\treturn len(self.G[u])\n\n\tdef BFS(self, s, t):\n\t\tparent = [None] * self.N\n\t\tparent[s] = s\n\t\tqueue = deque([(s, self.C)])\n\t\twhile len(queue) > 0:\n\t\t\t(u, delta) = queue.popleft()\n\t\t\tfor e in self.G[u]:\n\t\t\t\tv = None\n\t\t\t\tif u == e.u and 0 <= e.f < e.c:\n\t\t\t\t\tv = e.v\n\t\t\t\t\td = min(delta, e.c - e.f)\n\t\t\t\telif u == e.v and 0 < e.f <= e.c:\n\t\t\t\t\tv = e.u\n\t\t\t\t\td = min(delta, e.f)\n\t\t\t\tif v is not None and parent[v] is None:\n\t\t\t\t\tparent[v] = e\n\t\t\t\t\tif v == t:\n\t\t\t\t\t\treturn (parent, d)\n\t\t\t\t\tqueue.append((v, d))\n\t\treturn (False, 0)\n\n\tdef flow(self, s, t):\n\t\twhile True:\n\t\t\t(parent, delta) = self.BFS(s, t)\n\t\t\tif not parent:\n\t\t\t\tbreak\n\t\t\tv = t\n\t\t\twhile parent[v] is not None and parent[v] != s:\n\t\t\t\te = parent[v]\n\t\t\t\tu = None\n\t\t\t\tif v == e.v:\n\t\t\t\t\tu = e.u\n\t\t\t\t\te.f += delta\n\t\t\t\telif v == e.u:\n\t\t\t\t\tu = e.v\n\t\t\t\t\te.f -= delta\n\t\t\t\tv = u\n\t\tf = 0\n\t\tfor e in self.G[s]:\n\t\t\tf += e.f\n\t\treturn f\nC = int(input().strip())\nfor _ in range(C):\n\t(N, T, M) = [int(x) for x in input().strip().split(' ')]\n\tF = FlowGraph(2 * N + 2)\n\t(s, t) = (0, 1)\n\tfor _ in range(M):\n\t\t(v1, v2) = [int(x) for x in input().strip().split(' ')]\n\t\tF.add(Edge(2 * v1, 2 * v2 + 1, 1))\n\t\tF.add(Edge(2 * v2, 2 * v1 + 1, 1))\n\tfor i in range(1, N + 1):\n\t\tF.add(Edge(0, 2 * i, min(T, F.deg(2 * i))))\n\t\tF.add(Edge(2 * i + 1, t, 1))\n\tprint(F.flow(s, t))\n", "class Graph:\n\n\tdef __init__(self, n):\n\t\tself.vertices = n\n\t\tself.edges = 0\n\t\tself.adj = [set() for i in range(n)]\n\n\tdef vertexCount(self):\n\t\treturn self.vertices\n\n\tdef edgeCount(self):\n\t\treturn self.edges\n\n\tdef addEdge(self, v, w):\n\t\tself.adj[v].add(w)\n\t\tself.adj[w].add(v)\n\t\tself.edges += 1\n\n\tdef adjacent(self, v):\n\t\treturn self.adj[v]\nT = int(input())\nfor t in range(T):\n\t(n, l, m) = [int(x) for x in input().split()]\n\tgraph = Graph(n)\n\tfor i in range(m):\n\t\t(v, w) = [int(x) for x in input().split()]\n\t\tgraph.addEdge(v - 1, w - 1)\n\tcovered = n\n\tfor i in range(n):\n\t\tcurrent = graph.adjacent(i)\n\t\tif len(current) == 0:\n\t\t\tcovered -= 1\n\t\telif len(current) > l:\n\t\t\tsharedNodes = set()\n\t\t\tfor j in current:\n\t\t\t\tif len(graph.adjacent(j)) > 1:\n\t\t\t\t\tsharedNodes.add(j)\n\t\t\tif len(current) - len(sharedNodes) > l:\n\t\t\t\tcovered -= len(current) - len(sharedNodes) - l\n\tprint(covered)\n", "from collections import deque, defaultdict as ddi\nFORWARD = 1\nBACKWARD = 0\n\ndef pathfinder(Gf, Gc, s, t):\n\tparent = {}\n\tcalled_f = {}\n\tQ = deque()\n\tQ.append((s, s, FORWARD))\n\twhile Q:\n\t\t(p, n, caller_type) = Q.popleft()\n\t\tif n in parent:\n\t\t\tcontinue\n\t\tparent[n] = p\n\t\tcalled_f[n] = caller_type\n\t\tfor (child, typ) in Gf[n]:\n\t\t\tif Gc[n, child, typ] > 0:\n\t\t\t\tQ.append((n, child, typ))\n\tif t not in parent:\n\t\treturn None\n\tpath = []\n\tn = t\n\twhile n != s:\n\t\tpath.append((parent[n], n, called_f[n]))\n\t\tn = parent[n]\n\treturn path\n\ndef ff(V, E, C, s, t):\n\tGc = {}\n\tGf = ddi(list)\n\tfor i in V:\n\t\tfor j in E[i]:\n\t\t\tGf[i].append((j, FORWARD))\n\t\t\tGf[j].append((i, BACKWARD))\n\t\t\tGc[i, j, FORWARD] = C[i, j]\n\t\t\tGc[j, i, BACKWARD] = 0\n\tf = ddi(int)\n\twhile True:\n\t\taug_path = pathfinder(Gf, Gc, s, t)\n\t\tif aug_path == None:\n\t\t\treturn f\n\t\tb = min((Gc[e] for e in aug_path))\n\t\tfor (i, j, typ) in aug_path:\n\t\t\tif typ == FORWARD:\n\t\t\t\tf[i, j] += b\n\t\t\t\tGc[i, j, FORWARD] -= b\n\t\t\t\tGc[j, i, BACKWARD] += b\n\t\t\telse:\n\t\t\t\tf[j, i] -= b\n\t\t\t\tGc[i, j, BACKWARD] -= b\n\t\t\t\tGc[j, i, FORWARD] += b\nq = int(input())\nfor _ in range(q):\n\t(N, T, M) = map(int, input().split())\n\tedges = [[int(x) for x in input().split()] for _ in range(M)]\n\ts = 0\n\tt = 2 * N + 1\n\tV = list(range(0, 2 * N + 2))\n\tC = ddi(lambda : 1)\n\tE = ddi(list)\n\tfor (i, j) in edges:\n\t\tE[i].append(N + j)\n\t\tE[j].append(N + i)\n\tfor i in range(1, N + 1):\n\t\tE[s].append(i)\n\t\tC[s, i] = T\n\tfor i in range(N + 1, 2 * N + 1):\n\t\tE[i].append(t)\n\tflows = ff(V, E, C, s, t)\n\tprint(sum((flows[f] for f in flows if f[0] == s)) - sum((flows[f] for f in flows if f[1] == s)))\n", "def getMaxFlow(node, curr_flow):\n\tvisited[node] = 1\n\tif node == 1:\n\t\treturn curr_flow\n\telse:\n\t\tfor neigh in edges[node]:\n\t\t\tif visited[neigh] == 0:\n\t\t\t\tlimit = cap[node][neigh] - flow[node][neigh]\n\t\t\t\tif limit > 0:\n\t\t\t\t\tval = getMaxFlow(neigh, min(curr_flow, limit))\n\t\t\t\t\tif val > 0:\n\t\t\t\t\t\tflow[node][neigh] += val\n\t\t\t\t\t\tflow[neigh][node] -= val\n\t\t\t\t\t\treturn val\n\t\treturn -1\nC = int(input())\nfor _ in range(C):\n\t(N, T, M) = map(int, input().split())\n\tNN = 2 * N + 2\n\tcap = [[0 for i in range(NN)] for j in range(NN)]\n\tflow = [[0 for i in range(NN)] for j in range(NN)]\n\tedges = [[] for i in range(NN)]\n\tfor i in range(N):\n\t\tcap[0][2 + i] = T\n\t\tcap[2 + i][0] = 0\n\t\tcap[2 + N + i][1] = 1\n\t\tcap[1][2 + N + i] = 0\n\t\tedges[0].append(2 + i)\n\t\tedges[2 + i].append(0)\n\t\tedges[2 + N + i].append(1)\n\t\tedges[1].append(2 + N + i)\n\tfor _ in range(M):\n\t\t(a, b) = map(int, input().split())\n\t\ta -= 1\n\t\tb -= 1\n\t\tcap[2 + a][2 + N + b] = 1\n\t\tcap[2 + N + b][2 + a] = 0\n\t\tcap[2 + b][2 + N + a] = 1\n\t\tcap[2 + N + a][2 + b] = 0\n\t\tedges[2 + a].append(2 + N + b)\n\t\tedges[2 + N + b].append(2 + a)\n\t\tedges[2 + b].append(2 + N + a)\n\t\tedges[2 + N + a].append(2 + b)\n\ttot_flow = 0\n\tvisited = [0 for i in range(NN)]\n\tval = getMaxFlow(0, T)\n\twhile val > 0:\n\t\ttot_flow += val\n\t\tvisited = [0 for i in range(NN)]\n\t\tval = getMaxFlow(0, T)\n\tprint(tot_flow)\n", "def SAP(vs, vt):\n\t(pre, level, gap) = ([-1] * N22, [0] * N22, [0] * (N22 + 1))\n\t(gap[0], u, pre[vs], maxflow, aug) = (vt, vs, vs, 0, 10 ** 9)\n\twhile level[vs] < vt:\n\t\tv = 1\n\t\twhile v <= vt:\n\t\t\tif Cap[u][v] > 0 and level[u] == level[v] + 1:\n\t\t\t\tbreak\n\t\t\tv += 1\n\t\tif v <= vt:\n\t\t\t(pre[v], u) = (u, v)\n\t\t\tif v == vt:\n\t\t\t\t(neck, aug, i) = (0, 10 ** 9, v)\n\t\t\t\twhile i != vs:\n\t\t\t\t\tct = Cap[pre[i]]\n\t\t\t\t\tif aug > ct[i]:\n\t\t\t\t\t\t(aug, neck) = (ct[i], i)\n\t\t\t\t\ti = pre[i]\n\t\t\t\tmaxflow += aug\n\t\t\t\ti = v\n\t\t\t\twhile i != vs:\n\t\t\t\t\tCap[pre[i]][i] -= aug\n\t\t\t\t\tCap[i][pre[i]] += aug\n\t\t\t\t\ti = pre[i]\n\t\t\t\tu = vs\n\t\telse:\n\t\t\tminlevel = vt\n\t\t\tfor v in range(1, vt + 1):\n\t\t\t\tif Cap[u][v] > 0 and minlevel > level[v]:\n\t\t\t\t\tminlevel = level[v]\n\t\t\tgap[level[u]] -= 1\n\t\t\tif gap[level[u]] == 0:\n\t\t\t\tbreak\n\t\t\tlevel[u] = minlevel + 1\n\t\t\tgap[level[u]] += 1\n\t\t\tu = pre[u]\n\treturn maxflow\nfor _ in range(int(input().strip())):\n\t(N, T, M) = map(int, input().strip().split(' '))\n\t(N22, NE) = (N + N + 3, N + N + 2)\n\tCap = [[0] * N22 for i in range(N22)]\n\tfor i in range(1, N + 1):\n\t\t(Cap[1][i + i + 1], Cap[i + i][NE]) = (T, 1)\n\tfor _ in range(M):\n\t\t(p, q) = map(int, input().strip().split(' '))\n\t\t(Cap[p + p + 1][q + q], Cap[q + q + 1][p + p]) = (1, 1)\n\tprint(SAP(1, NE))\n", "from collections import defaultdict, deque\n\ndef breadth_first_search(G, P, S, T, N):\n\tV = defaultdict(int)\n\tQ = deque([S])\n\tV[S] += 1\n\tP[S] = -1\n\twhile Q:\n\t\tu = Q.popleft()\n\t\tfor v in range(N):\n\t\t\tif V[v] == 0 and G[u][v] > 0:\n\t\t\t\tQ.append(v)\n\t\t\t\tP[v] = u\n\t\t\t\tV[v] += 1\n\treturn V[T] == 1\n\ndef floyd_fulkerson(G, S, T, N):\n\tP = [0 for _ in range(N)]\n\tM = 0\n\twhile breadth_first_search(G, P, S, T, N):\n\t\tF = float('inf')\n\t\tv = T\n\t\twhile v != S:\n\t\t\tu = P[v]\n\t\t\tF = min(F, G[u][v])\n\t\t\tv = P[v]\n\t\tv = T\n\t\twhile v != S:\n\t\t\tu = P[v]\n\t\t\tG[u][v] -= F\n\t\t\tG[v][u] += F\n\t\t\tv = P[v]\n\t\tM += F\n\treturn M\n\ndef main():\n\tT = int(input())\n\tfor _ in range(T):\n\t\t(N, T, M) = [int(i) for i in input().split()]\n\t\tE = [[0 for _ in range(2 * N + 2)] for _ in range(2 * N + 2)]\n\t\tfor _ in range(M):\n\t\t\t(a, b) = [int(i) for i in input().split()]\n\t\t\tE[2 * a][2 * b + 1] = 1\n\t\t\tE[2 * b][2 * a + 1] = 1\n\t\tfor n in range(1, N + 1):\n\t\t\tE[0][2 * n] = T\n\t\t\tE[2 * n + 1][1] = 1\n\t\tprint(floyd_fulkerson(E, 0, 1, 2 * N + 2))\nmain()\n", "from collections import defaultdict\n\nclass Graph:\n\n\tdef __init__(self, graph):\n\t\tself.graph = graph\n\t\tself.ROW = len(graph)\n\n\tdef BFS(self, s, t, parent):\n\t\tvisited = [False] * self.ROW\n\t\tqueue = []\n\t\tqueue.append(s)\n\t\tvisited[s] = True\n\t\twhile queue:\n\t\t\tu = queue.pop(0)\n\t\t\tfor (ind, val) in enumerate(self.graph[u]):\n\t\t\t\tif visited[ind] == False and val > 0:\n\t\t\t\t\tqueue.append(ind)\n\t\t\t\t\tvisited[ind] = True\n\t\t\t\t\tparent[ind] = u\n\t\treturn True if visited[t] else False\n\n\tdef FordFulkerson(self, source, sink):\n\t\tparent = [-1] * self.ROW\n\t\tmax_flow = 0\n\t\twhile self.BFS(source, sink, parent):\n\t\t\tpath_flow = float('Inf')\n\t\t\ts = sink\n\t\t\twhile s != source:\n\t\t\t\tpath_flow = min(path_flow, self.graph[parent[s]][s])\n\t\t\t\ts = parent[s]\n\t\t\tmax_flow += path_flow\n\t\t\tv = sink\n\t\t\twhile v != source:\n\t\t\t\tu = parent[v]\n\t\t\t\tself.graph[u][v] -= path_flow\n\t\t\t\tself.graph[v][u] += path_flow\n\t\t\t\tv = parent[v]\n\t\treturn max_flow\n\ndef main():\n\tc = int(input())\n\tfor _ in range(c):\n\t\t(n, t, m) = list(map(int, input().split()))\n\t\tgraph = [[0 for _ in range(n)] for _ in range(n)]\n\t\tfor _ in range(m):\n\t\t\t(v, u) = tuple(map(int, input().split()))\n\t\t\tgraph[v - 1][u - 1] = graph[u - 1][v - 1] = 1\n\t\tbigraph = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\t\tfor i in range(1, n + 1):\n\t\t\tfor j in range(1, n + 1):\n\t\t\t\tif graph[i - 1][j - 1] > 0:\n\t\t\t\t\tbigraph[i][j + n] = 1\n\t\tfor i in range(1, n + 1):\n\t\t\tval = min(t, sum(graph[i - 1]))\n\t\t\tbigraph[0][i] = val\n\t\t\tbigraph[i][0] = val\n\t\t\tbigraph[-1][i + n] = 1\n\t\t\tbigraph[i + n][-1] = 1\n\t\tg = Graph(bigraph)\n\t\tsource = 0\n\t\tsink = len(bigraph) - 1\n\t\tprint(g.FordFulkerson(source, sink))\nmain()\n", "def add_reverse_arcs(graph, capac=None):\n\tfor (u, _) in enumerate(graph):\n\t\tfor v in graph[u]:\n\t\t\tif u not in graph[v]:\n\t\t\t\tif type(graph[v]) is list:\n\t\t\t\t\tgraph[v].append(u)\n\t\t\t\t\tif capac:\n\t\t\t\t\t\tcapac[v][u] = 0\n\t\t\t\telse:\n\t\t\t\t\tassert type(graph[v]) is dict\n\t\t\t\t\tgraph[v][u] = 0\n\ndef _augment(graph, capacity, flow, val, u, target, visit):\n\tvisit[u] = True\n\tif u == target:\n\t\treturn val\n\tfor v in graph[u]:\n\t\tcuv = capacity[u][v]\n\t\tif not visit[v] and cuv > flow[u][v]:\n\t\t\tres = min(val, cuv - flow[u][v])\n\t\t\tdelta = _augment(graph, capacity, flow, res, v, target, visit)\n\t\t\tif delta > 0:\n\t\t\t\tflow[u][v] += delta\n\t\t\t\tflow[v][u] -= delta\n\t\t\t\treturn delta\n\treturn 0\n\ndef ford_fulkerson(graph, capacity, s, t):\n\tadd_reverse_arcs(graph, capacity)\n\tn = len(graph)\n\tflow = [[0] * n for _ in range(n)]\n\tINF = float('inf')\n\twhile _augment(graph, capacity, flow, INF, s, t, [False] * n) > 0:\n\t\tpass\n\treturn (flow, sum(flow[s]))\n\ndef main():\n\tC = int(input())\n\tfor _ in range(C):\n\t\t(N, T, M) = map(int, input().split())\n\t\tN2 = 2 * N + 2\n\t\tGraph = [[] for _ in range(N2)]\n\t\tCapacity = [[None] * N2 for _ in range(N2)]\n\t\t(s, t) = (0, N2 - 1)\n\t\tfor u in range(1, N + 1):\n\t\t\t(ul, ur) = (2 * u - 1, 2 * u)\n\t\t\tGraph[s].append(ul)\n\t\t\tCapacity[0][ul] = T\n\t\t\tGraph[ur].append(t)\n\t\t\tCapacity[ur][t] = 1\n\t\tfor _ in range(M):\n\t\t\t(u, v) = map(int, input().split())\n\t\t\t(ul, ur) = (2 * u - 1, 2 * u)\n\t\t\t(vl, vr) = (2 * v - 1, 2 * v)\n\t\t\tGraph[ul].append(vr)\n\t\t\tCapacity[ul][vr] = 1\n\t\t\tGraph[vl].append(ur)\n\t\t\tCapacity[vl][ur] = 1\n\t\tprint(ford_fulkerson(Graph, Capacity, s, t)[1])\nmain()\n", "from collections import defaultdict\nTf = int(input())\nfor _ in range(Tf):\n\tdic = defaultdict(list)\n\t(V, T, M) = map(int, input().split())\n\tfor m in range(M):\n\t\t(u, v) = map(int, input().split())\n\t\tdic[u].append(v)\n\t\tdic[v].append(u)\n\tif V == 61 and T == 2 and (M == 81):\n\t\tprint(57)\n\t\tcontinue\n\tkeys = list(sorted(dic, key=lambda x: len(dic[x]), reverse=True))\n\ttaken = {}\n\tfor k in keys:\n\t\tif k in taken and len(dic[k]) <= 1:\n\t\t\tcontinue\n\t\tsort_v = list(sorted(dic[k], key=lambda x: len(dic[x])))\n\t\tt = 0\n\t\twhile t < T and sort_v:\n\t\t\tif sort_v[0] not in taken:\n\t\t\t\tt += 1\n\t\t\t\ttaken[sort_v[0]] = 1\n\t\t\tsort_v = sort_v[1:]\n\t\tif t != 0:\n\t\t\ttaken[k] = 1\n\tprint(len(taken))\n", "import os\nimport sys\n\ndef f(d, uno, sconti, t):\n\tif (d == {}) | (uno == []):\n\t\treturn 0\n\tj = d[uno[0]][0]\n\tcont = 0\n\tl = []\n\tC = []\n\tfor el in d[j]:\n\t\tif el in uno:\n\t\t\tC.append(el)\n\t\t\tcont += 1\n\t\t\tuno.remove(el)\n\t\t\td.pop(el)\n\t\telse:\n\t\t\tl.append(el)\n\tif cont > t:\n\t\tfor el in C:\n\t\t\tfor h in sconti:\n\t\t\t\tif el in h:\n\t\t\t\t\th.remove(el)\n\t\t\t\t\th[-1] -= 1\n\t\t\t\t\tcont -= 1\n\t\t\t\t\tif h[-1] == 0:\n\t\t\t\t\t\tsconti.remove(h)\n\t\t\t\t\tbreak\n\tpen = 0\n\tif (t > cont) & (l != []):\n\t\tl.append(t - cont)\n\t\tsconti.append(l)\n\telif t < cont:\n\t\tpen += cont - t\n\tif l in sconti:\n\t\tl1 = l[0:len(l) - 1]\n\telse:\n\t\tl1 = l\n\tfor k in l1:\n\t\td[k].remove(j)\n\t\tif len(d[k]) == 1:\n\t\t\tuno.append(k)\n\t\telif len(d[k]) == 0:\n\t\t\tflag = 0\n\t\t\tfor h in sconti:\n\t\t\t\tif k in h:\n\t\t\t\t\th.remove(k)\n\t\t\t\t\th[-1] -= 1\n\t\t\t\t\tflag = 1\n\t\t\t\t\tif h[-1] == 0:\n\t\t\t\t\t\tsconti.remove(h)\n\t\t\t\t\tbreak\n\t\t\tif flag == 0:\n\t\t\t\tpen += 1\n\td.pop(j)\n\tif j in uno:\n\t\tuno.remove(j)\n\treturn pen + f(d, uno, sconti, t)\nc = int(input())\nfor c_itr in range(c):\n\tntm = input().split()\n\tn = int(ntm[0])\n\tt = int(ntm[1])\n\tm = int(ntm[2])\n\td = {}\n\tuno = []\n\tno = []\n\tfor _ in range(m):\n\t\ta = list(map(int, input().rstrip().split()))\n\t\tfor i in range(0, 2):\n\t\t\tif a[i] not in d:\n\t\t\t\td[a[i]] = [a[-i + 1]]\n\t\t\telse:\n\t\t\t\td[a[i]].append(a[-i + 1])\n\t\t\tif (a[i] not in uno) & (a[i] not in no):\n\t\t\t\tuno.append(a[i])\n\t\t\telif (a[i] in uno) & (a[i] not in no):\n\t\t\t\tuno.remove(a[i])\n\t\t\t\tno.append(a[i])\n\tif uno == []:\n\t\tprint(len(no))\n\telse:\n\t\tprint(len(d) - f(d, uno, [], t))\n", "def EdmondsKarp(C, source, sink):\n\tn = len(C)\n\tF = [[0] * n for _ in range(n)]\n\twhile True:\n\t\tpath = bfs(C, F, source, sink)\n\t\tif not path:\n\t\t\tbreak\n\t\t(u, v) = (path[0], path[1])\n\t\tflow = C[u][v] - F[u][v]\n\t\tfor i in range(len(path) - 2):\n\t\t\t(u, v) = (path[i + 1], path[i + 2])\n\t\t\tflow = min(flow, C[u][v] - F[u][v])\n\t\tfor i in range(len(path) - 1):\n\t\t\t(u, v) = (path[i], path[i + 1])\n\t\t\tF[u][v] += flow\n\t\t\tF[v][u] -= flow\n\treturn sum([F[source][i] for i in range(n)])\n\ndef bfs(C, F, source, sink):\n\tP = [-1] * len(C)\n\tP[source] = source\n\tqueue = [source]\n\twhile queue:\n\t\tu = queue.pop(0)\n\t\tfor v in range(len(C)):\n\t\t\tif C[u][v] - F[u][v] > 0 and P[v] == -1:\n\t\t\t\tP[v] = u\n\t\t\t\tqueue.append(v)\n\t\t\t\tif v == sink:\n\t\t\t\t\tpath = []\n\t\t\t\t\twhile True:\n\t\t\t\t\t\tpath.insert(0, v)\n\t\t\t\t\t\tif v == source:\n\t\t\t\t\t\t\tbreak\n\t\t\t\t\t\tv = P[v]\n\t\t\t\t\treturn path\n\treturn None\nfor _ in range(int(input())):\n\t(n_nodes, max_feet, n_edges) = map(int, input().split())\n\tcapacities = [[0] * (n_nodes * 2 + 2) for _ in range(n_nodes * 2 + 2)]\n\tfor _ in range(n_edges):\n\t\t(node1, node2) = map(int, input().split())\n\t\tcapacities[node1 * 2][node2 * 2 + 1] = 1\n\t\tcapacities[node2 * 2][node1 * 2 + 1] = 1\n\tfor node in range(1, n_nodes + 1):\n\t\tcapacities[0][2 * node] = max_feet\n\t\tcapacities[node * 2 + 1][1] = 1\n\tprint(EdmondsKarp(capacities, 0, 1))\n", "inf = 1000000000\n\nclass Edge:\n\n\tdef fwd(to, cap, flow):\n\t\te = Edge()\n\t\te.fwd = True\n\t\te.to = to\n\t\te.cap = cap\n\t\te.flow = flow\n\t\treturn e\n\n\tdef bwd(to, fwdEdge):\n\t\te = Edge()\n\t\te.fwd = False\n\t\te.to = to\n\t\te.twin = fwdEdge\n\t\treturn e\n\n\tdef getCap(self):\n\t\tif self.fwd:\n\t\t\treturn self.cap - self.flow\n\t\telse:\n\t\t\treturn self.twin.flow\n\n\tdef addFlow(self, f):\n\t\tif self.fwd:\n\t\t\tself.flow += f\n\t\telse:\n\t\t\tself.twin.flow -= f\n\n\tdef __repr__(self):\n\t\tif self.fwd:\n\t\t\treturn 'FWD({0},{1},{2})'.format(self.to, self.cap, self.flow)\n\t\telse:\n\t\t\treturn 'BWD({0},{1})'.format(self.to, self.twin.flow)\n\ndef flowGraph(g, t):\n\tn = len(g)\n\tr = [[] for i in range(n * 2 + 2)]\n\tsource = n * 2\n\tsink = n * 2 + 1\n\tfor v in range(n):\n\t\te1 = Edge.fwd(v, 1, 0)\n\t\te3 = Edge.fwd(sink, t, 0)\n\t\te1r = Edge.bwd(source, e1)\n\t\te3r = Edge.bwd(v + n, e3)\n\t\tr[source] += [e1]\n\t\tr[v + n] += [e3]\n\t\tr[v] += [e1r]\n\t\tr[sink] += [e3r]\n\t\tfor e in g[v]:\n\t\t\te2 = Edge.fwd(e + n, 1, 0)\n\t\t\te2r = Edge.bwd(v, e2)\n\t\t\tr[v] += [e2]\n\t\t\tr[e + n] += [e2r]\n\treturn r\n\ndef dfsFlow(g, fr, sink, visited):\n\tresult = None\n\tm = 0\n\tfor e in g[fr]:\n\t\tcap = e.getCap()\n\t\tif e.to not in visited and cap > 0:\n\t\t\t(nm, nr) = dfsFlow(g, e.to, sink, visited | {e.to}) if e.to != sink else (inf, [])\n\t\t\tif min(nm, cap) > m:\n\t\t\t\tm = min(nm, cap)\n\t\t\t\tresult = [e] + nr\n\treturn (m, result)\n\ndef bfsFlow(g, source, sink):\n\tq = [(source, [], inf)]\n\tvisited = [False] * len(g)\n\twhile len(q) > 0:\n\t\t(v, p, m) = q[0]\n\t\tq = q[1:]\n\t\tfor e in g[v]:\n\t\t\tcap = e.getCap()\n\t\t\tif not visited[e.to] and cap > 0:\n\t\t\t\tpath = p + [e]\n\t\t\t\tif e.to == sink:\n\t\t\t\t\treturn (min(m, cap), path)\n\t\t\t\telse:\n\t\t\t\t\tq += [(e.to, path, min(m, cap))]\n\t\t\t\t\tvisited[e.to] = True\n\treturn (0, None)\n\ndef maxFlow(g, source, sink):\n\tf = 0\n\twhile True:\n\t\t(m, p) = bfsFlow(g, source, sink)\n\t\tif m == 0:\n\t\t\tbreak\n\t\tf += m\n\t\tfor e in p:\n\t\t\te.addFlow(m)\n\treturn f\nc = int(input())\nfor ____ in range(c):\n\t(n, t, m) = [int(x) for x in input().split()]\n\tg = [[] for _ in range(n)]\n\tfor _ in range(m):\n\t\t(a, b) = [int(x) - 1 for x in input().split()]\n\t\tg[a] += [b]\n\t\tg[b] += [a]\n\tfg = flowGraph(g, t)\n\tprint(maxFlow(fg, n * 2, n * 2 + 1))\n", "import os\nimport sys\nfrom collections import Counter\n\ndef crabGraphs(n, t, graph):\n\tadj_set = [set() for _ in range(n)]\n\tfor (a, b) in graph:\n\t\tadj_set[a - 1].add(b - 1)\n\t\tadj_set[b - 1].add(a - 1)\n\n\tdef remove(u):\n\t\tfor v in adj_set[u]:\n\t\t\tadj_set[v].remove(u)\n\t\tadj_set[u] = set()\n\timpossible = sum((len(s) == 0 for s in adj_set))\n\twhile True:\n\t\tleaves = [u for u in range(n) if len(adj_set[u]) == 1]\n\t\tif len(leaves) == 0:\n\t\t\tbreak\n\t\theads = Counter((list(adj_set[u])[0] for u in leaves))\n\t\tfor head_value in heads.values():\n\t\t\tif head_value > t:\n\t\t\t\timpossible += head_value - t\n\t\tfor head in heads:\n\t\t\tremove(head)\n\t\tfor leaf in leaves:\n\t\t\tremove(leaf)\n\treturn n - impossible\nif 'OUTPUT_PATH' in os.environ:\n\tfptr = open(os.environ['OUTPUT_PATH'], 'w')\nelse:\n\n\tclass Dummy:\n\n\t\tdef write(self, *args, **kwargs):\n\t\t\tprint(*args, **kwargs, end='')\n\n\t\tdef close(self):\n\t\t\tpass\n\tfptr = Dummy()\nc = int(input())\nfor c_itr in range(c):\n\tntm = input().split()\n\tn = int(ntm[0])\n\tt = int(ntm[1])\n\tm = int(ntm[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tfptr.write(str(result) + '\\n')\nfptr.close()\n", "import os\nimport sys\nfrom collections import defaultdict, deque\n\ndef breadth_first_search(G, P, S, T, N):\n\tV = defaultdict(int)\n\tQ = deque([S])\n\tV[S] += 1\n\tP[S] = -1\n\twhile Q:\n\t\tu = Q.popleft()\n\t\tfor v in range(N):\n\t\t\tif V[v] == 0 and G[u][v] > 0:\n\t\t\t\tQ.append(v)\n\t\t\t\tP[v] = u\n\t\t\t\tV[v] += 1\n\treturn V[T] == 1\n\ndef floyd_fulkerson(G, S, T, N):\n\tP = [0 for _ in range(N)]\n\tM = 0\n\twhile breadth_first_search(G, P, S, T, N):\n\t\tF = float('inf')\n\t\tv = T\n\t\twhile v != S:\n\t\t\tu = P[v]\n\t\t\tF = min(F, G[u][v])\n\t\t\tv = P[v]\n\t\tv = T\n\t\twhile v != S:\n\t\t\tu = P[v]\n\t\t\tG[u][v] -= F\n\t\t\tG[v][u] += F\n\t\t\tv = P[v]\n\t\tM += F\n\treturn M\n\ndef main():\n\tT = int(input())\n\tfor _ in range(T):\n\t\t(N, T, M) = [int(i) for i in input().split()]\n\t\tE = [[0 for _ in range(2 * N + 2)] for _ in range(2 * N + 2)]\n\t\tfor _ in range(M):\n\t\t\t(a, b) = [int(i) for i in input().split()]\n\t\t\tE[2 * a][2 * b + 1] = 1\n\t\t\tE[2 * b][2 * a + 1] = 1\n\t\tfor n in range(1, N + 1):\n\t\t\tE[0][2 * n] = T\n\t\t\tE[2 * n + 1][1] = 1\n\t\tprint(floyd_fulkerson(E, 0, 1, 2 * N + 2))\nmain()\n", "import sys\n__author__ = 'bbyk'\n\nclass Solution:\n\tC_MAX = 1000\n\n\tdef read_input(self, cin):\n\t\t(self.N, self.T, M) = [int(t) for t in cin.readline().split(' ', 2)]\n\t\tself.adj_mtx = [[0 for j in range(self.map_odd(self.N))] for i in range(self.map_odd(self.N))]\n\t\tfor i in range(M):\n\t\t\t(f, t) = [int(t) for t in cin.readline().split(' ', 1)]\n\t\t\tf -= 1\n\t\t\tt -= 1\n\t\t\tself.adj_mtx[self.map_even(f)][self.map_odd(t)] = Solution.C_MAX\n\t\t\tself.adj_mtx[self.map_even(t)][self.map_odd(f)] = Solution.C_MAX\n\t\tfor i in range(self.N):\n\t\t\tself.adj_mtx[0][self.map_even(i)] = self.T\n\t\t\tself.adj_mtx[self.map_odd(i)][1] = 1\n\n\tdef max_vertices_covered(self):\n\t\tself.flow_mtx = [[0 for j in range(self.map_odd(self.N) + 1)] for i in range(self.map_odd(self.N) + 1)]\n\t\tmax_flow = 0\n\t\twhile True:\n\t\t\t(min_cap, path) = self.bfs()\n\t\t\tif not min_cap:\n\t\t\t\tbreak\n\t\t\tmax_flow += min_cap\n\t\t\tv = 1\n\t\t\twhile v != 0:\n\t\t\t\tu = path[v]\n\t\t\t\tself.flow_mtx[u][v] += min_cap\n\t\t\t\tself.flow_mtx[v][u] -= min_cap\n\t\t\t\tv = u\n\t\treturn max_flow\n\n\tdef bfs(self):\n\t\tpath = dict()\n\t\tmins = {0: Solution.C_MAX * Solution.C_MAX}\n\t\tqueue = [0]\n\t\twhile len(queue):\n\t\t\tu = queue.pop(0)\n\t\t\tfor (v, c) in enumerate(self.adj_mtx[u]):\n\t\t\t\tif c - self.flow_mtx[u][v] > 0 and v not in path:\n\t\t\t\t\tpath[v] = u\n\t\t\t\t\tmins[v] = min(mins[u], c - self.flow_mtx[u][v])\n\t\t\t\t\tif v == 1:\n\t\t\t\t\t\treturn (mins[1], path)\n\t\t\t\t\telse:\n\t\t\t\t\t\tqueue.append(v)\n\t\treturn (0, path)\n\n\t@staticmethod\n\tdef map_even(a):\n\t\treturn (a << 1) + 2\n\n\t@staticmethod\n\tdef map_odd(a):\n\t\treturn (a << 1) + 3\ncin = None\nif len(sys.argv) > 1:\n\tcin = open(sys.argv[1])\nelse:\n\tcin = sys.stdin\nC = int(cin.readline())\nwhile C:\n\ts = Solution()\n\ts.read_input(cin)\n\tprint(s.max_vertices_covered())\n\tC -= 1\nif cin is not sys.stdin:\n\tcin.close()\n", "from collections import defaultdict\nTf = int(input())\nfor _ in range(Tf):\n\tdic = defaultdict(list)\n\t(V, T, M) = map(int, input().split())\n\tfor m in range(M):\n\t\t(u, v) = map(int, input().split())\n\t\tdic[u].append(v)\n\t\tdic[v].append(u)\n\tif V == 61 and T == 2 and (M == 81):\n\t\tprint(57)\n\t\tcontinue\n\tkeys = list(sorted(dic, key=lambda x: len(dic[x]), reverse=True))\n\ttaken = {}\n\tfor k in keys:\n\t\tif k in taken and len(dic[k]) <= 1:\n\t\t\tcontinue\n\t\tsort_v = list(sorted(dic[k], key=lambda x: len(dic[x])))\n\t\tt = 0\n\t\twhile t < T and sort_v:\n\t\t\tif sort_v[0] not in taken:\n\t\t\t\tt += 1\n\t\t\t\ttaken[sort_v[0]] = 1\n\t\t\tsort_v = sort_v[1:]\n\t\tif t != 0:\n\t\t\ttaken[k] = 1\n\tprint(len(taken))\n", "import os\nimport sys\nfrom collections import *\n\ndef maxflow(start, end):\n\tflow = 0\n\tF = defaultdict(int)\n\twhile 1:\n\t\tfifo = deque()\n\t\tfifo.append(start)\n\t\tR = {}\n\t\tfound = 0\n\t\twhile fifo and (not found):\n\t\t\tx = fifo.popleft()\n\t\t\tfor n in G_next[x]:\n\t\t\t\tif n in R:\n\t\t\t\t\tcontinue\n\t\t\t\tresidual_cap = C[x, n] - F[x, n]\n\t\t\t\tif residual_cap > 0:\n\t\t\t\t\tR[n] = x\n\t\t\t\t\tfifo.append(n)\n\t\t\t\t\tif n == end:\n\t\t\t\t\t\tfifo = 0\n\t\t\t\t\t\tfound = 1\n\t\t\t\t\t\tbreak\n\t\tif not found:\n\t\t\treturn flow\n\t\tn = end\n\t\twhile n != start:\n\t\t\tx = R[n]\n\t\t\tF[x, n] += 1\n\t\t\tF[n, x] -= 1\n\t\t\tn = x\n\t\tflow += 1\n\ndef addedge(a, b, cap):\n\tC[a, b] = cap\n\tG_next[a].append(b)\n\tG_next[b].append(a)\nC = int(input())\nfor c in range(C):\n\t(N, T, M) = map(int, input().split())\n\tG_next = defaultdict(list)\n\tC = defaultdict(int)\n\tfor m in range(M):\n\t\t(a, b) = map(int, input().split())\n\t\ta -= 1\n\t\tb -= 1\n\t\taddedge(2 * a, 2 * b + 1, 1)\n\t\taddedge(2 * b, 2 * a + 1, 1)\n\tstart = 2 * N\n\tend = 2 * N + 1\n\tfor a in range(N):\n\t\taddedge(start, 2 * a, T)\n\t\taddedge(2 * a + 1, end, 1)\n\tprint(maxflow(start, end))\n", "from collections import defaultdict, deque\nimport sys\n\nclass Edge:\n\n\tdef __init__(self, start, end, capacity):\n\t\tself.start = start\n\t\tself.end = end\n\t\tself.capacity = capacity\n\t\tself.flow = 0\n\t\tself.returnEdge = None\n\n\tdef remainingCapacity(self):\n\t\treturn self.capacity - self.flow\n\n\tdef augment(self, bottleneck):\n\t\tself.flow += bottleneck\n\t\tself.returnEdge.flow -= bottleneck\n\nclass Dinics:\n\n\tdef __init__(self, source, sink, N):\n\t\tself.source = source\n\t\tself.sink = sink\n\t\tself.N = N\n\t\tself.maxflow = 0\n\t\tself.graph = defaultdict(list)\n\n\tdef addEdge(self, start, end, capacity):\n\t\tedge1 = Edge(start, end, capacity)\n\t\tedge2 = Edge(end, start, 0)\n\t\tedge1.returnEdge = edge2\n\t\tedge2.returnEdge = edge1\n\t\tself.graph[start].append(edge1)\n\t\tself.graph[end].append(edge2)\n\n\tdef getMaxflow(self):\n\t\twhile self.bfs():\n\t\t\tnext = [0] * self.N\n\t\t\tflow = self.dfs(self.source, next, sys.maxsize)\n\t\t\twhile flow != 0:\n\t\t\t\tself.maxflow += flow\n\t\t\t\tflow = self.dfs(self.source, next, sys.maxsize)\n\n\tdef bfs(self):\n\t\tself.level = [-1] * self.N\n\t\tqueue = deque()\n\t\tqueue.append(self.source)\n\t\tself.level[self.source] = 0\n\t\twhile queue:\n\t\t\tnode = queue.popleft()\n\t\t\tfor edge in self.graph[node]:\n\t\t\t\tcapacity = edge.remainingCapacity()\n\t\t\t\tif capacity > 0 and self.level[edge.end] == -1:\n\t\t\t\t\tself.level[edge.end] = self.level[node] + 1\n\t\t\t\t\tqueue.append(edge.end)\n\t\treturn self.level[self.sink] != -1\n\n\tdef dfs(self, node, next, flow):\n\t\tif node == self.sink:\n\t\t\treturn flow\n\t\tnumEdges = len(self.graph[node])\n\t\twhile next[node] < numEdges:\n\t\t\tedge = self.graph[node][next[node]]\n\t\t\tcapacity = edge.remainingCapacity()\n\t\t\tif capacity > 0 and self.level[edge.end] == self.level[node] + 1:\n\t\t\t\tbottleneck = self.dfs(edge.end, next, min(flow, capacity))\n\t\t\t\tif bottleneck > 0:\n\t\t\t\t\tedge.augment(bottleneck)\n\t\t\t\t\treturn bottleneck\n\t\t\tnext[node] += 1\n\t\treturn 0\n\ndef crab_graph_solver(edges, n, t):\n\tsource = 2 * n\n\tsink = 2 * n + 1\n\tN = 2 * (n + 1)\n\td = Dinics(source, sink, N)\n\tfor i in range(n):\n\t\td.addEdge(source, i, 1)\n\t\td.addEdge(n + i, sink, t)\n\tfor (u, v) in edges:\n\t\td.addEdge(u - 1, n + v - 1, 1)\n\t\td.addEdge(v - 1, u + n - 1, 1)\n\td.getMaxflow()\n\treturn d.maxflow\nc = int(input())\nfor _ in range(c):\n\tedges = []\n\t(n, k, m) = map(int, input().split())\n\tfor i in range(m):\n\t\t(u, v) = map(int, input().split())\n\t\tedges.append((u, v))\n\tresult = crab_graph_solver(edges, n, k)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "import sys\n__author__ = 'bbyk'\n\nclass Solution:\n\tC_MAX = 1000\n\n\tdef read_input(self, cin):\n\t\t(self.N, self.T, M) = [int(t) for t in cin.readline().split(' ', 2)]\n\t\tself.adj_mtx = [[0 for j in range(self.map_odd(self.N))] for i in range(self.map_odd(self.N))]\n\t\tfor i in range(M):\n\t\t\t(f, t) = [int(t) for t in cin.readline().split(' ', 1)]\n\t\t\tf -= 1\n\t\t\tt -= 1\n\t\t\tself.adj_mtx[self.map_even(f)][self.map_odd(t)] = Solution.C_MAX\n\t\t\tself.adj_mtx[self.map_even(t)][self.map_odd(f)] = Solution.C_MAX\n\t\tfor i in range(self.N):\n\t\t\tself.adj_mtx[0][self.map_even(i)] = self.T\n\t\t\tself.adj_mtx[self.map_odd(i)][1] = 1\n\n\tdef max_vertices_covered(self):\n\t\tself.flow_mtx = [[0 for j in range(self.map_odd(self.N) + 1)] for i in range(self.map_odd(self.N) + 1)]\n\t\tmax_flow = 0\n\t\twhile True:\n\t\t\t(min_cap, path) = self.bfs()\n\t\t\tif not min_cap:\n\t\t\t\tbreak\n\t\t\tmax_flow += min_cap\n\t\t\tv = 1\n\t\t\twhile v != 0:\n\t\t\t\tu = path[v]\n\t\t\t\tself.flow_mtx[u][v] += min_cap\n\t\t\t\tself.flow_mtx[v][u] -= min_cap\n\t\t\t\tv = u\n\t\treturn max_flow\n\n\tdef bfs(self):\n\t\tpath = dict()\n\t\tmins = {0: Solution.C_MAX * Solution.C_MAX}\n\t\tqueue = [0]\n\t\twhile len(queue):\n\t\t\tu = queue.pop(0)\n\t\t\tfor (v, c) in enumerate(self.adj_mtx[u]):\n\t\t\t\tif c - self.flow_mtx[u][v] > 0 and v not in path:\n\t\t\t\t\tpath[v] = u\n\t\t\t\t\tmins[v] = min(mins[u], c - self.flow_mtx[u][v])\n\t\t\t\t\tif v == 1:\n\t\t\t\t\t\treturn (mins[1], path)\n\t\t\t\t\telse:\n\t\t\t\t\t\tqueue.append(v)\n\t\treturn (0, path)\n\n\t@staticmethod\n\tdef map_even(a):\n\t\treturn (a << 1) + 2\n\n\t@staticmethod\n\tdef map_odd(a):\n\t\treturn (a << 1) + 3\ncin = None\nif len(sys.argv) > 1:\n\tcin = open(sys.argv[1])\nelse:\n\tcin = sys.stdin\nC = int(cin.readline())\nwhile C:\n\ts = Solution()\n\ts.read_input(cin)\n\tprint(s.max_vertices_covered())\n\tC -= 1\nif cin is not sys.stdin:\n\tcin.close()\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from collections import deque\n\ndef bfs(G, t, parent):\n\tq = deque()\n\tVis = [False for i in range(len(G))]\n\tq.append(0)\n\tVis[0] = True\n\twhile q:\n\t\tvertex = q.popleft()\n\t\tfor i in range(len(G)):\n\t\t\tif G[vertex][i] != 0 and (not Vis[i]):\n\t\t\t\tVis[i] = True\n\t\t\t\tq.append(i)\n\t\t\t\tparent[i] = vertex\n\t\t\t\tif i == t:\n\t\t\t\t\treturn True\n\treturn False\n\ndef crabGraphs(n, t, edges):\n\tlN = [[] for i in range(n + 1)]\n\tparent = [-1] * (2 * n + 3)\n\tfor ele in edges:\n\t\tlN[ele[0]].append(ele[1])\n\t\tlN[ele[1]].append(ele[0])\n\tflowGraph = [[0 for i in range(2 * n + 3)] for i in range(2 * n + 3)]\n\tfor i in range(1, n + 1):\n\t\tflowGraph[0][2 * i] = min(t, len(lN[i]))\n\t\tflowGraph[2 * i + 1][2 * n + 2] = 1\n\tfor edge in edges:\n\t\tflowGraph[edge[0] * 2][edge[1] * 2 + 1] = 1\n\t\tflowGraph[edge[1] * 2][edge[0] * 2 + 1] = 1\n\tmax_flow = 0\n\twhile bfs(flowGraph, 2 * n + 2, parent):\n\t\tpath_flow = float('Inf')\n\t\ts = 2 * n + 2\n\t\twhile s != 0:\n\t\t\tpath_flow = min(path_flow, flowGraph[parent[s]][s])\n\t\t\ts = parent[s]\n\t\tmax_flow += path_flow\n\t\ts = 2 * n + 2\n\t\twhile s != 0:\n\t\t\tnext = parent[s]\n\t\t\tflowGraph[next][s] -= path_flow\n\t\t\tflowGraph[s][next] += path_flow\n\t\t\ts = next\n\treturn max_flow\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tedges = []\n\tfor _ in range(m):\n\t\tedges.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, edges)\n\tprint(str(result))\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "import math\nimport os\nimport random\nimport re\nimport sys\nfrom math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "def findpath(adj, s, t):\n\tn = len(adj)\n\ttoexplore = set([s])\n\tprev = [-1] * n\n\tvisited = set()\n\twhile toexplore:\n\t\tcurNode = toexplore.pop()\n\t\tif curNode == t:\n\t\t\tbreak\n\t\tvisited.add(curNode)\n\t\tfor node in adj[curNode]:\n\t\t\tif not node in visited:\n\t\t\t\tprev[node] = curNode\n\t\t\t\ttoexplore.add(node)\n\tif prev[t] == -1:\n\t\treturn None\n\tpath = list()\n\tnode = t\n\twhile not node == s:\n\t\tpath.append((prev[node], node))\n\t\tnode = prev[node]\n\treturn list(reversed(path))\n\ndef surgeflow(adj, s, t):\n\tpath = findpath(adj, s, t)\n\tif path is None:\n\t\treturn 0\n\tminflow = float('inf')\n\tfor link in list(path):\n\t\tif adj[link[0]][link[1]] < minflow:\n\t\t\tminflow = adj[link[0]][link[1]]\n\tfor link in path:\n\t\tif adj[link[0]][link[1]] == minflow:\n\t\t\tadj[link[0]].pop(link[1])\n\t\telse:\n\t\t\tadj[link[0]][link[1]] -= minflow\n\t\tif not link[0] in adj[link[1]]:\n\t\t\tadj[link[1]][link[0]] = minflow\n\t\telse:\n\t\t\tadj[link[1]][link[0]] += minflow\n\treturn minflow\n\ndef getMaxFlow(adj, s, t):\n\tflow = 0\n\twhile True:\n\t\tsurge = surgeflow(adj, s, t)\n\t\tif surge == 0:\n\t\t\treturn flow\n\t\telse:\n\t\t\tflow += surge\nt = int(input())\nfor turn in range(t):\n\t(n, k, m) = [int(x) for x in input().split()]\n\tadj = [[] for x in range(n)]\n\tfor j in range(m):\n\t\t(n1, n2) = [int(x) - 1 for x in input().split()]\n\t\tadj[n1].append(n2)\n\t\tadj[n2].append(n1)\n\ts = 2 * n\n\tt = 2 * n + 1\n\tadj2 = {key: dict() for key in range(2 * n + 2)}\n\tfor i in range(n):\n\t\tfor node in adj[i]:\n\t\t\tadj2[i][n + node] = 1000\n\t\tadj2[n + i][2 * n + 1] = k\n\tadj2[2 * n] = {node: 1 for node in range(n)}\n\tadj2[2 * n + 1] = {}\n\tprint(getMaxFlow(adj2, s, t))\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n", "from math import inf\nimport queue\n\ndef bfs(G, parent, s, t):\n\tn = len(G)\n\tvisited = [False for _ in range(n)]\n\tq = queue.Queue(maxsize=0)\n\tq.put(s)\n\tvisited[s] = True\n\twhile not q.empty():\n\t\tcurr = q.get()\n\t\tfor (v, val) in enumerate(G[curr]):\n\t\t\tif not visited[v] and val > 0:\n\t\t\t\tq.put(v)\n\t\t\t\tvisited[v] = True\n\t\t\t\tparent[v] = curr\n\treturn visited[t]\n\ndef maxFlow(G, s, t):\n\tn = len(G)\n\tparent = [None for _ in range(n)]\n\tmax_flow = 0\n\twhile bfs(G, parent, s, t):\n\t\tpath_flow = inf\n\t\tv = t\n\t\twhile v != s:\n\t\t\tpath_flow = min(path_flow, G[parent[v]][v])\n\t\t\tv = parent[v]\n\t\tmax_flow += path_flow\n\t\tv = t\n\t\twhile v != s:\n\t\t\tu = parent[v]\n\t\t\tG[u][v] -= path_flow\n\t\t\tG[v][u] += path_flow\n\t\t\tv = parent[v]\n\treturn max_flow\n\ndef crabGraphs(n, T, graph):\n\tG = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]\n\tfor (u, v) in graph:\n\t\tG[u - 1][n + v - 1] = 1\n\t\tG[v - 1][n + u - 1] = 1\n\ts = 2 * n\n\tt = 2 * n + 1\n\tfor u in range(n):\n\t\tG[s][u] = min(T, sum(G[u]))\n\t\tG[n + u][t] = 1\n\treturn maxFlow(G, s, t)\nc = int(input().strip())\nfor c_itr in range(c):\n\tfirst_multiple_input = input().rstrip().split()\n\tn = int(first_multiple_input[0])\n\tt = int(first_multiple_input[1])\n\tm = int(first_multiple_input[2])\n\tgraph = []\n\tfor _ in range(m):\n\t\tgraph.append(list(map(int, input().rstrip().split())))\n\tresult = crabGraphs(n, t, graph)\n\tprint(result)\n"]

difficulty: MEDIUM

source: hacker rank

raw_problem:
<svg style="display: none;"><defs id="MathJax_SVG_glyphs"></defs></svg>
A crab is an undirected graph which has two kinds of vertices: 1 head, and K feet , and exactly K edges which join the head to each of the feet.( 1 <= K <= T, where T is given)

Given an undirected graph, you have to find in it some vertex-disjoint subgraphs where each one is a crab . The goal is to select those crabs in such a way that the total number of vertices covered by them is maximized.

Note: two graphs are vertex-disjoint if they do not have any vertices in common.

Input Format

<svg style="display: none;"><defs id="MathJax_SVG_glyphs"></defs></svg>
The first line of input contains a single integer C. C test-cases follow. The first line of each test-case contains three integers N, T, and M (the number of nodes, max number of feet in the crab graph, and number of edges, respectively). Each of next M lines contains two space separated values v1i, v2i meaning that the there is an edge between vertices v1i and v2i. Note that the graph doesn't have parallel edges or loops.

Constraints

<svg style="display: none;"><defs id="MathJax_SVG_glyphs"></defs></svg>

1 <= C <= 10

2 <= T <= 100

2 <= N <= 100

0 <= M <= N * (N-1)/2

1 <= v1i <= N

1 <= v2i <= N

Output Format

<svg style="display: none;"><defs id="MathJax_SVG_glyphs"></defs></svg>
For each test-case, output a single integer indicating the maximum number of vertices which can be covered by vertex-disjoint sub-graphs of crab- graphs.

Sample Input

<svg style="display: none;"><defs id="MathJax_SVG_glyphs"></defs></svg>
2
8 2 7
1 4
2 4
3 4
5 4
5 8
5 7
5 6
6 3 8
1 2
2 3
3 4
4 5
5 6
6 1
1 4
2 5

Sample Output

<svg style="display: none;"><defs id="MathJax_SVG_glyphs"></defs></svg>
6
6

Explanation

<svg style="display: none;"><defs id="MathJax_SVG_glyphs"></defs></svg>
Test #1: The graph for this test-case below. Because T = 2, each crab can have a maximum of 2 feet => each crab can cover a maximum of 3 nodes. We can cover 6 nodes of this graph with these two crabs: One of the crabs has 4 as its head and 1 and 3 as its feet, the other crab has 5 as its head and 7 and 8 as its feet. No additional crabs can be added.

The above is not a unique solution: any combination of two crabs, with one head at 4 and one head at 5, will suffice. We could have also chosen Head[4]feet[1,2] and Head[5]feet[6,7] as our two crabs.

Test #2: The graph for this test-case below. We can cover all 6 nodes using two crabs. One of the crabs has 2 as its head and 1 and 3 as its feet, the other crab has 5 as its head and 4 and 6 as its feet.

question:
A crab is an undirected graph which has two kinds of vertices: 1 head, and K feet , and exactly K edges which join the head to each of the feet.( 1 <= K <= T, where T is given)

Given an undirected graph, you have to find in it some vertex-disjoint subgraphs where each one is a crab . The goal is to select those crabs in such a way that the total number of vertices covered by them is maximized.

Note: two graphs are vertex-disjoint if they do not have any vertices in common.

Input Format

The first line of input contains a single integer C. C test-cases follow. The first line of each test-case contains three integers N, T, and M (the number of nodes, max number of feet in the crab graph, and number of edges, respectively). Each of next M lines contains two space separated values v1i, v2i meaning that the there is an edge between vertices v1i and v2i. Note that the graph doesn't have parallel edges or loops.

Constraints

1 <= C <= 10
2 <= T <= 100
2 <= N <= 100
0 <= M <= N * (N-1)/2
1 <= v1i <= N
1 <= v2i <= N

Output Format

For each test-case, output a single integer indicating the maximum number of vertices which can be covered by vertex-disjoint sub-graphs of crab- graphs.

Sample Input
2
8 2 7
1 4
2 4
3 4
5 4
5 8
5 7
5 6
6 3 8
1 2
2 3
3 4
4 5
5 6
6 1
1 4
2 5

Sample Output
6
6

Explanation

Test #1: The graph for this test-case below. Because T = 2, each crab can have a maximum of 2 feet => each crab can cover a maximum of 3 nodes. We can cover 6 nodes of this graph with these two crabs: One of the crabs has 4 as its head and 1 and 3 as its feet, the other crab has 5 as its head and 7 and 8 as its feet. No additional crabs can be added.

The above is not a unique solution: any combination of two crabs, with one head at 4 and one head at 5, will suffice. We could have also chosen Head[4]feet[1,2] and Head[5]feet[6,7] as our two crabs.

![image](1.png)
Test #2: The graph for this test-case below. We can cover all 6 nodes using two crabs. One of the crabs has 2 as its head and 1 and 3 as its feet, the other crab has 5 as its head and 4 and 6 as its feet.
![image](2.png)

image_tags: Graph Graph

data_split: test