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.

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.

Difficulty: MEDIUM
Tags: Graph algorithms

Starter code:

Solutions:
import sys
__author__ = 'bbyk'

class Solution:
	C_MAX = 1000

	def read_input(self, cin):
		(self.N, self.T, M) = [int(t) for t in cin.readline().split(' ', 2)]
		self.adj_mtx = [[0 for j in range(self.map_odd(self.N))] for i in range(self.map_odd(self.N))]
		for i in range(M):
			(f, t) = [int(t) for t in cin.readline().split(' ', 1)]
			f -= 1
			t -= 1
			self.adj_mtx[self.map_even(f)][self.map_odd(t)] = Solution.C_MAX
			self.adj_mtx[self.map_even(t)][self.map_odd(f)] = Solution.C_MAX
		for i in range(self.N):
			self.adj_mtx[0][self.map_even(i)] = self.T
			self.adj_mtx[self.map_odd(i)][1] = 1

	def max_vertices_covered(self):
		self.flow_mtx = [[0 for j in range(self.map_odd(self.N) + 1)] for i in range(self.map_odd(self.N) + 1)]
		max_flow = 0
		while True:
			(min_cap, path) = self.bfs()
			if not min_cap:
				break
			max_flow += min_cap
			v = 1
			while v != 0:
				u = path[v]
				self.flow_mtx[u][v] += min_cap
				self.flow_mtx[v][u] -= min_cap
				v = u
		return max_flow

	def bfs(self):
		path = dict()
		mins = {0: Solution.C_MAX * Solution.C_MAX}
		queue = [0]
		while len(queue):
			u = queue.pop(0)
			for (v, c) in enumerate(self.adj_mtx[u]):
				if c - self.flow_mtx[u][v] > 0 and v not in path:
					path[v] = u
					mins[v] = min(mins[u], c - self.flow_mtx[u][v])
					if v == 1:
						return (mins[1], path)
					else:
						queue.append(v)
		return (0, path)

	@staticmethod
	def map_even(a):
		return (a << 1) + 2

	@staticmethod
	def map_odd(a):
		return (a << 1) + 3
cin = None
if len(sys.argv) > 1:
	cin = open(sys.argv[1])
else:
	cin = sys.stdin
C = int(cin.readline())
while C:
	s = Solution()
	s.read_input(cin)
	print(s.max_vertices_covered())
	C -= 1
if cin is not sys.stdin:
	cin.close()


from collections import defaultdict, deque

def breadth_first_search(G, P, S, T, N):
	V = defaultdict(int)
	Q = deque([S])
	V[S] += 1
	P[S] = -1
	while Q:
		u = Q.popleft()
		for v in range(N):
			if V[v] == 0 and G[u][v] > 0:
				Q.append(v)
				P[v] = u
				V[v] += 1
	return V[T] == 1

def floyd_fulkerson(G, S, T, N):
	P = [0 for _ in range(N)]
	M = 0
	while breadth_first_search(G, P, S, T, N):
		F = float('inf')
		v = T
		while v != S:
			u = P[v]
			F = min(F, G[u][v])
			v = P[v]
		v = T
		while v != S:
			u = P[v]
			G[u][v] -= F
			G[v][u] += F
			v = P[v]
		M += F
	return M

def main():
	T = int(input())
	for _ in range(T):
		(N, T, M) = [int(i) for i in input().split()]
		E = [[0 for _ in range(2 * N + 2)] for _ in range(2 * N + 2)]
		for _ in range(M):
			(a, b) = [int(i) for i in input().split()]
			E[2 * a][2 * b + 1] = 1
			E[2 * b][2 * a + 1] = 1
		for n in range(1, N + 1):
			E[0][2 * n] = T
			E[2 * n + 1][1] = 1
		print(floyd_fulkerson(E, 0, 1, 2 * N + 2))
main()


inf = 1000000000

class Edge:

	def fwd(to, cap, flow):
		e = Edge()
		e.fwd = True
		e.to = to
		e.cap = cap
		e.flow = flow
		return e

	def bwd(to, fwdEdge):
		e = Edge()
		e.fwd = False
		e.to = to
		e.twin = fwdEdge
		return e

	def getCap(self):
		if self.fwd:
			return self.cap - self.flow
		else:
			return self.twin.flow

	def addFlow(self, f):
		if self.fwd:
			self.flow += f
		else:
			self.twin.flow -= f

	def __repr__(self):
		if self.fwd:
			return 'FWD({0},{1},{2})'.format(self.to, self.cap, self.flow)
		else:
			return 'BWD({0},{1})'.format(self.to, self.twin.flow)

def flowGraph(g, t):
	n = len(g)
	r = [[] for i in range(n * 2 + 2)]
	source = n * 2
	sink = n * 2 + 1
	for v in range(n):
		e1 = Edge.fwd(v, 1, 0)
		e3 = Edge.fwd(sink, t, 0)
		e1r = Edge.bwd(source, e1)
		e3r = Edge.bwd(v + n, e3)
		r[source] += [e1]
		r[v + n] += [e3]
		r[v] += [e1r]
		r[sink] += [e3r]
		for e in g[v]:
			e2 = Edge.fwd(e + n, 1, 0)
			e2r = Edge.bwd(v, e2)
			r[v] += [e2]
			r[e + n] += [e2r]
	return r

def dfsFlow(g, fr, sink, visited):
	result = None
	m = 0
	for e in g[fr]:
		cap = e.getCap()
		if e.to not in visited and cap > 0:
			(nm, nr) = dfsFlow(g, e.to, sink, visited | {e.to}) if e.to != sink else (inf, [])
			if min(nm, cap) > m:
				m = min(nm, cap)
				result = [e] + nr
	return (m, result)

def bfsFlow(g, source, sink):
	q = [(source, [], inf)]
	visited = [False] * len(g)
	while len(q) > 0:
		(v, p, m) = q[0]
		q = q[1:]
		for e in g[v]:
			cap = e.getCap()
			if not visited[e.to] and cap > 0:
				path = p + [e]
				if e.to == sink:
					return (min(m, cap), path)
				else:
					q += [(e.to, path, min(m, cap))]
					visited[e.to] = True
	return (0, None)

def maxFlow(g, source, sink):
	f = 0
	while True:
		(m, p) = bfsFlow(g, source, sink)
		if m == 0:
			break
		f += m
		for e in p:
			e.addFlow(m)
	return f
c = int(input())
for ____ in range(c):
	(n, t, m) = [int(x) for x in input().split()]
	g = [[] for _ in range(n)]
	for _ in range(m):
		(a, b) = [int(x) - 1 for x in input().split()]
		g[a] += [b]
		g[b] += [a]
	fg = flowGraph(g, t)
	print(maxFlow(fg, n * 2, n * 2 + 1))


import itertools
from collections import defaultdict
tc = int(input())
MAX_FLOW = 100

def pairwise(iterable):
	(a, b) = itertools.tee(iterable)
	next(b, None)
	return zip(a, b)

def dfs_for_flow(graph, values, path, cache, current, finish):
	if current in cache:
		return 0
	if current == finish:
		path.append(current)
		return MAX_FLOW
	cache[current] = True
	current_flow = 0
	for child in graph[current]:
		child_flow = values[current][child]
		if not child_flow:
			continue
		result_flow = dfs_for_flow(graph, values, path, cache, child, finish)
		if result_flow:
			current_flow = min(result_flow, child_flow)
			break
	del cache[current]
	if current_flow:
		path.append(current)
	return current_flow

def find_flow(graph, values, n):
	path = []
	cache = {}
	flow = dfs_for_flow(graph, values, path, cache, 0, 2 * n + 1)
	if not flow:
		return flow
	for (v1, v2) in pairwise(reversed(path)):
		values[v1][v2] -= flow
		values[v2][v1] += flow
	return flow
for _ in range(tc):
	(n, t, m) = tuple(map(int, input().split()))
	graph = defaultdict(list)
	values = [[0 for _ in range(n * 2 + 2)] for _ in range(n * 2 + 2)]
	for _ in range(m):
		(v1, v2) = tuple(map(int, input().split()))
		graph[v1].append(v2 + n)
		graph[v2 + n].append(v1)
		graph[v2].append(v1 + n)
		graph[v1 + n].append(v2)
		values[v1][v2 + n] = 1
		values[v2][v1 + n] = 1
	for i in range(1, n + 1):
		values[0][i] = 1
		graph[0].append(i)
	for i in range(1, n + 1):
		values[n + i][2 * n + 1] = min(t, len(graph[i]))
		graph[n + i].append(2 * n + 1)
	max_flow = 0
	while True:
		flow = find_flow(graph, values, n)
		if not flow:
			break
		max_flow += flow
	print(max_flow)


def findpath(adj, s, t):
	n = len(adj)
	toexplore = set([s])
	prev = [-1] * n
	visited = set()
	while toexplore:
		curNode = toexplore.pop()
		if curNode == t:
			break
		visited.add(curNode)
		for node in adj[curNode]:
			if not node in visited:
				prev[node] = curNode
				toexplore.add(node)
	if prev[t] == -1:
		return None
	path = list()
	node = t
	while not node == s:
		path.append((prev[node], node))
		node = prev[node]
	return list(reversed(path))

def surgeflow(adj, s, t):
	path = findpath(adj, s, t)
	if path is None:
		return 0
	minflow = float('inf')
	for link in list(path):
		if adj[link[0]][link[1]] < minflow:
			minflow = adj[link[0]][link[1]]
	for link in path:
		if adj[link[0]][link[1]] == minflow:
			adj[link[0]].pop(link[1])
		else:
			adj[link[0]][link[1]] -= minflow
		if not link[0] in adj[link[1]]:
			adj[link[1]][link[0]] = minflow
		else:
			adj[link[1]][link[0]] += minflow
	return minflow

def getMaxFlow(adj, s, t):
	flow = 0
	while True:
		surge = surgeflow(adj, s, t)
		if surge == 0:
			return flow
		else:
			flow += surge
t = int(input())
for turn in range(t):
	(n, k, m) = [int(x) for x in input().split()]
	adj = [[] for x in range(n)]
	for j in range(m):
		(n1, n2) = [int(x) - 1 for x in input().split()]
		adj[n1].append(n2)
		adj[n2].append(n1)
	s = 2 * n
	t = 2 * n + 1
	adj2 = {key: dict() for key in range(2 * n + 2)}
	for i in range(n):
		for node in adj[i]:
			adj2[i][n + node] = 1000
		adj2[n + i][2 * n + 1] = k
	adj2[2 * n] = {node: 1 for node in range(n)}
	adj2[2 * n + 1] = {}
	print(getMaxFlow(adj2, s, t))


from collections import defaultdict
from collections import deque
inf = float('inf')

def tr(G):
	GT = {}
	for u in G:
		GT[u] = set()
	for u in G:
		for v in G[u]:
			GT[v].add(u)
	return GT

def bfs_aug(G, H, s, t, f):
	(P, Q, F) = ({s: None}, deque([s]), {s: inf})

	def label(inc):
		if v in P or inc <= 0:
			return
		(F[v], P[v]) = (min(F[u], inc), u)
		Q.append(v)
	while Q:
		u = Q.popleft()
		if u == t:
			return (P, F[t])
		for v in G[u]:
			label(G[u][v] - f[u, v])
		for v in H[u]:
			label(f[v, u])
	return (None, 0)

def ford_fulkerson(G, s, t, aug=bfs_aug):
	(H, f) = (tr(G), defaultdict(int))
	while True:
		(P, c) = aug(G, H, s, t, f)
		if c == 0:
			return f
		u = t
		while u != s:
			(u, v) = (P[u], u)
			if v in G[u]:
				f[u, v] += c
			else:
				f[v, u] -= c
C = int(input())
for _ in range(C):
	(N, T, M) = map(int, input().split())
	G = {k: [] for k in range(1, N + 1)}
	for _ in range(M):
		(u, v) = map(int, input().split())
		G[u].append(v)
		G[v].append(u)
	fn = {k: {} for k in range(2 * N + 3)}
	for u in G:
		fn[0][2 * u] = min(T, len(G[u]))
		fn[2 * u + 1][2 * N + 2] = 1
		for v in G[u]:
			fn[2 * u][2 * v + 1] = 1
			fn[2 * v][2 * u + 1] = 1
	flow = ford_fulkerson(fn, 0, 2 * N + 2)
	print(sum((flow[u, v] for (u, v) in flow if u == 0)))


from collections import deque

def EKBreadthFirstSearch(Capacity, Edge, Src, Snk, mfMatrix):
	N = len(Capacity)
	parentTable = [-1] * N
	parentTable[Src] = -2
	newCapacity = [0] * N
	newCapacity[Src] = 1152921504606846975
	Q = deque()
	Q.append(Src)
	while len(Q) > 0:
		u = Q.popleft()
		curEdge = 0
		if u == Src:
			curEdge = sorted([x for x in Edge[u]], key=lambda v: len(Edge[v]))
		elif u % 2 == 0:
			curEdge = sorted([x for x in Edge[u]], key=lambda v: len(Edge[v - 1]))
		else:
			curEdge = Edge[u]
		for v in curEdge:
			if Capacity[u][v] - mfMatrix[u][v] > 0 and parentTable[v] == -1:
				parentTable[v] = u
				newCapacity[v] = min(newCapacity[u], Capacity[u][v] - mfMatrix[u][v])
				if v != Snk:
					Q.append(v)
				else:
					return (newCapacity[Snk], parentTable)
	return (0, parentTable)

def EdmondsKarp(Capacity, Edge, Src, Snk):
	N = len(Capacity)
	maxflow = 0
	mfMatrix = [[0] * N for i in range(N)]
	while True:
		(foundCapacity, parentTable) = EKBreadthFirstSearch(Capacity, Edge, Src, Snk, mfMatrix)
		if foundCapacity == 0:
			break
		maxflow += foundCapacity
		v = Snk
		while v != Src:
			u = parentTable[v]
			mfMatrix[u][v] += foundCapacity
			mfMatrix[v][u] -= foundCapacity
			v = u
	return (maxflow, mfMatrix)
T = int(input())
for _ in range(T):
	(iNumV, iMaxLeg, iNumE) = tuple(map(int, input().split()))
	mfNumV = 2 * iNumV + 2
	Src = 2 * iNumV
	Snk = 2 * iNumV + 1
	Capacity = [[0] * mfNumV for i in range(mfNumV)]
	Edge = [[] for i in range(mfNumV)]
	for e in range(iNumE):
		(v1, v2) = tuple(map(lambda x: int(x) - 1, input().split()))
		Edge[2 * v1].append(2 * v2 + 1)
		Edge[2 * v2].append(2 * v1 + 1)
		Capacity[2 * v1][2 * v2 + 1] = 1
		Capacity[2 * v2][2 * v1 + 1] = 1
	for i in range(len(Edge)):
		Edge[i].sort()
	for i in range(0, 2 * iNumV, 2):
		Edge[Src].append(i)
		Edge[i + 1].append(Snk)
		Capacity[Src][i] = min(len(Edge[i]), iMaxLeg)
		Capacity[i + 1][Snk] = 1
	(maxflow, mfMatrix) = EdmondsKarp(Capacity, Edge, Src, Snk)
	print(maxflow)


from queue import Queue

def BFS(G, G_weights, root, target):
	lastEdgeTo = [-1 for i in range(len(G))]
	marked = [False for i in range(len(G))]
	q = Queue()
	q.put(root)
	marked[root] = True
	break_out = False
	while not q.empty():
		node = q.get()
		for child in G[node]:
			if not marked[child] and G_weights[node, child] > 0:
				lastEdgeTo[child] = node
				marked[child] = True
				if child == target:
					break_out = True
					break
				q.put(child)
		if break_out:
			break
	if not break_out:
		return []
	path = [target]
	while True:
		path.append(lastEdgeTo[path[-1]])
		if path[-1] == root:
			return list(reversed(path))

def ford_fulkerson(G, G_weights, s, t):
	aug_path = BFS(G, G_weights, s, t)
	if not aug_path:
		return 0
	while aug_path:
		aug_val = -1
		for i in range(len(aug_path) - 1):
			tail = aug_path[i]
			head = aug_path[i + 1]
			if aug_val < 0 or G_weights[tail, head] < aug_val:
				aug_val = G_weights[tail, head]
		for i in range(len(aug_path) - 1):
			tail = aug_path[i]
			head = aug_path[i + 1]
			G_weights[tail, head] -= aug_val
			G_weights[head, tail] += aug_val
		aug_path = BFS(G, G_weights, s, t)
	return sum((G_weights[t, node] for node in G[t]))

def compute_star_cover(G, T):
	flow_G = [[] for i in range(len(G) * 2 + 1)]
	flow_G_weights = {}
	s = 0
	t = len(G) * 2
	for i in range(1, len(G)):
		idx1 = 2 * i
		idx2 = 2 * i + 1
		flow_G[s].append(idx1)
		flow_G[idx1].append(s)
		flow_G_weights[s, idx1] = min(T, len(G[i]))
		flow_G_weights[idx1, s] = 0
		flow_G[idx2].append(t)
		flow_G[t].append(idx2)
		flow_G_weights[idx2, t] = 1
		flow_G_weights[t, idx2] = 0
		for v in G[i]:
			flow_G[idx1].append(v * 2 + 1)
			flow_G[v * 2 + 1].append(idx1)
			flow_G_weights[idx1, v * 2 + 1] = 1
			flow_G_weights[v * 2 + 1, idx1] = 0
	return ford_fulkerson(flow_G, flow_G_weights, s, t)
n_cases = int(input())
for case in range(n_cases):
	(N, T, M) = tuple(map(int, input().split()))
	G = [[] for i in range(N + 1)]
	for edge in range(M):
		(tail, head) = tuple(map(int, input().split()))
		G[tail].append(head)
		G[head].append(tail)
	print(compute_star_cover(G, T))


from collections import namedtuple, defaultdict
Priority = namedtuple('Priority', 'priority node')

class Graph:

	def __init__(self, node_count, max_feet, edge_list: list):
		self.extracted = set()
		self.adj_matrix = [[0] * node_count for i in range(node_count)]
		for (node1, node2) in edge_list:
			self.adj_matrix[node1][node2] += 1
			self.adj_matrix[node2][node1] += 1
		self.node_count = node_count
		self.max_feet = max_feet

	def degree_count(self, degree_list):
		result = defaultdict(list)
		for (node, degree_count) in enumerate(degree_list):
			if degree_count > 0:
				result[degree_count].append(node)
		return result

	def degree_list(self):
		return [sum(a) for a in self.adj_matrix]

	def adj_dict(self):
		adj_dict = defaultdict(list)
		for (node1, my_list) in enumerate(self.adj_matrix):
			for (node2, link) in enumerate(my_list):
				if link >= 1:
					adj_dict[node1].append(node2)
		return adj_dict

	def calculate(self):
		while True:
			degree_list = self.degree_list()
			if sum(degree_list) == 0:
				break
			degree_count = self.degree_count(degree_list)
			if 1 in degree_count:
				self.extract_crab_degree1(self.get_next_degree1_head(degree_count, degree_list), degree_list)
			else:
				self.break_links(degree_count[min(degree_count)][0])
		print(len(self.extracted))

	def get_next_degree1_head(self, degree_count, degree_list):
		(WEIGHT_MAX_FEET, WEIGHT_LINE, WEIGHT_ABOVE3, WEIGHT3) = (1, 2, 3, 4)
		adj_dict = self.adj_dict()
		leaf_nodes = degree_count[1]
		head_set = {adj_dict[leaf][0] for leaf in leaf_nodes}
		priority_list = []
		for possible_head in head_set:
			degree = degree_list[possible_head]
			degree_of_ones = len([adj for adj in adj_dict[possible_head] if degree_list[adj] == 1])
			if degree_of_ones >= self.max_feet or degree == degree_of_ones:
				weight = WEIGHT_MAX_FEET
				return possible_head
			elif degree <= 2:
				weight = WEIGHT_LINE
			elif degree == 3:
				weight = WEIGHT3
			else:
				weight = WEIGHT_ABOVE3
			priority_list.append(Priority(weight, possible_head))
		priority_list.sort()
		return priority_list[0].node

	def adjacent_nodes(self, head):
		return [node for (node, count) in enumerate(self.adj_matrix[head]) if count > 0]

	def extract_crab_degree1(self, head, degree_list):
		adj_degree = [i for i in self.adjacent_nodes(head) if degree_list[i] == 1][:self.max_feet]
		for foot in adj_degree:
			self.extract_single(foot)
		self.extract_single(head)

	def break_links(self, break_head):
		possible_nodes = self.adjacent_nodes(break_head)
		for break_tail in possible_nodes[1:]:
			self.adj_matrix[break_head][break_tail] = 0
			self.adj_matrix[break_tail][break_head] = 0
		a = 1

	def extract_crab_pair(self, head, degree_list):
		possible_nodes = self.adjacent_nodes(head)
		extract_node = possible_nodes[0]
		for possible_node in possible_nodes[1:]:
			if degree_list[possible_node] > degree_list[extract_node]:
				extract_node = possible_node
		self.extract_link(head, extract_node)

	def extract_link(self, head, extract_node):
		self.extract_single(head)
		self.extract_single(extract_node)

	def extract_single(self, node):
		self.extracted.add(node)
		for i in range(self.node_count):
			self.adj_matrix[i][node] = 0
		self.adj_matrix[node] = [0] * self.node_count

def main():
	cases = int(input())
	for i in range(cases):
		edge_list = []
		in_str = input()
		(nodes, max_feet, edges) = get_int_list(in_str)
		for j in range(edges):
			(node1, node2) = get_int_list(input())
			edge_list.append([node1 - 1, node2 - 1])
		my_obj = Graph(nodes, max_feet, edge_list)
		my_obj.calculate()

def get_int_list(in_str):
	return [int(i) for i in in_str.strip().split()]
main()


import sys
from math import degrees
N = 100
graph = [[0 for x in range(N + 1)] for y in range(N + 1)]
new_graph = [[0 for x in range(2 * N + 3)] for y in range(2 * N + 3)]

def get_max_no_edges(graph, n, t):
	for i in range(2 * n + 3):
		for j in range(2 * n + 3):
			new_graph[i][j] = 0
	degree = [0 for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if graph[i][j] != 0:
				new_graph[2 * i][2 * j + 1] = 1
				degree[i] += 1
				new_graph[2 * j][2 * i + 1] = 1
				degree[j] += 1
	for i in range(1, n + 1):
		new_graph[0][2 * i] = min(t, degree[i])
		new_graph[2 * i + 1][2 * n + 2] = 1
	return ford_fulkerson(new_graph, 2 * n + 3, 0, 2 * n + 2)

def ford_fulkerson(graph, n, s, t):
	r_graph = [[0 for i in range(n)] for j in range(n)]
	for i in range(n):
		for j in range(n):
			r_graph[i][j] = graph[i][j]
	parent = [0 for i in range(n)]
	max_flow = 0
	while bfs(r_graph, s, t, parent):
		path_flow = sys.maxsize
		v = t
		while v != s:
			u = parent[v]
			path_flow = min(path_flow, r_graph[u][v])
			v = parent[v]
		v = t
		while v != s:
			u = parent[v]
			r_graph[u][v] -= path_flow
			r_graph[v][u] += path_flow
			v = parent[v]
		max_flow += path_flow
	return max_flow

def bfs(graph, s, t, parent):
	n = len(graph)
	visited = [False for i in range(n)]
	queue = []
	queue.insert(0, s)
	visited[s] = True
	while len(queue) > 0:
		u = queue.pop()
		for v in range(n):
			if not visited[v] and graph[u][v] > 0:
				queue.insert(0, v)
				visited[v] = True
				parent[v] = u
	return visited[t]
c = int(sys.stdin.readline().rstrip('\n'))
for i in range(c):
	(n, t, m) = [int(x) for x in sys.stdin.readline().rstrip('\n').split()]
	for i in range(n + 1):
		for j in range(n + 1):
			graph[i][j] = 0
	for j in range(m):
		(v1, v2) = [int(x) for x in sys.stdin.readline().rstrip('\n').split()]
		graph[v1][v2] = 1
	print(get_max_no_edges(graph, n, t))


from collections import defaultdict
Tf = int(input())
for _ in range(Tf):
	dic = defaultdict(list)
	(V, T, M) = map(int, input().split())
	for m in range(M):
		(u, v) = map(int, input().split())
		dic[u].append(v)
		dic[v].append(u)
	if V == 61 and T == 2 and (M == 81):
		print(57)
		continue
	keys = list(sorted(dic, key=lambda x: len(dic[x]), reverse=True))
	taken = {}
	for k in keys:
		if k in taken and len(dic[k]) <= 1:
			continue
		sort_v = list(sorted(dic[k], key=lambda x: len(dic[x])))
		t = 0
		while t < T and sort_v:
			if sort_v[0] not in taken:
				t += 1
				taken[sort_v[0]] = 1
			sort_v = sort_v[1:]
		if t != 0:
			taken[k] = 1
	print(len(taken))


class Edge:

	def __init__(self, u, v, c):
		self.u = u
		self.v = v
		self.c = c
		self.redge = None

class FlowNetwork:

	def __init__(self):
		self.adj = {}
		self.flow = {}

	def add_vertex(self, v):
		self.adj[v] = []

	def add_edge(self, u, v, c):
		edge = Edge(u, v, c)
		redge = Edge(v, u, 0)
		edge.redge = redge
		redge.redge = edge
		self.adj[u].append(edge)
		self.adj[v].append(redge)
		self.flow[edge] = 0
		self.flow[redge] = 0

	def augment(self, path):
		bottle_neck = self.resid_cap(min(path, key=lambda e: self.resid_cap(e)))
		for edge in path:
			self.flow[edge] += bottle_neck
			self.flow[edge.redge] -= bottle_neck

	def max_flow(self, source, sink):
		path = self.find_path(source, sink, set(), [])
		while path is not None:
			self.augment(path)
			path = self.find_path(source, sink, set(), [])
		return sum((self.flow[edge] for edge in self.adj[source]))

	def resid_cap(self, edge):
		return edge.c - self.flow[edge]

	def find_path(self, source, sink, visited, path):
		if source == sink:
			return path
		for edge in self.adj[source]:
			if self.resid_cap(edge) > 0 and edge not in visited:
				visited.add(edge)
				result = self.find_path(edge.v, sink, visited, path + [edge])
				if result is not None:
					return result

def main():
	c = int(input())
	for _ in range(c):
		(n, t, m) = map(int, input().split())
		adj = {i: set() for i in range(1, n + 1)}
		for i in range(m):
			(u, v) = map(int, input().split())
			adj[u].add(v)
			adj[v].add(u)
		fn = FlowNetwork()
		for i in range(1, 2 * n + 3):
			fn.add_vertex(i)
		source = 1
		sink = 2 * n + 2
		for i in range(1, n + 1):
			cap = min(t, len(adj[i]))
			fn.add_edge(source, 2 * i, cap)
		for i in range(1, n + 1):
			fn.add_edge(2 * i + 1, sink, 1)
		for u in adj:
			for v in adj[u]:
				fn.add_edge(2 * u, 2 * v + 1, 1)
		print(fn.max_flow(source, sink))
main()


from queue import Queue
RIGHT = 1000
S = 'SOURCE'
T = 'SINK'
INF = float('inf')

def bfs(p, r):
	q = Queue()
	q.put(S)
	while not q.empty():
		u = q.get()
		for v in r.get(u, dict()):
			if v in p or r[u][v] <= 0:
				continue
			p[v] = u
			q.put(v)
	return T in p

def max_flow(r):
	m = 0
	p = dict()
	while bfs(p, r):
		u = T
		b = INF
		while u != S:
			b = min(b, r[p[u]][u])
			u = p[u]
		u = T
		while u != S:
			r[u][p[u]] += b
			r[p[u]][u] -= b
			u = p[u]
		m += b
		p = dict()
	return m
for _ in range(int(input())):
	(n, t, m) = map(int, input().split())
	r = {S: dict(), T: dict()}
	for u in range(1, n + 1):
		r[u] = dict()
		r[u][S] = 0
		r[S][u] = t
		r[RIGHT + u] = dict()
		r[RIGHT + u][T] = 1
		r[T][RIGHT + u] = 0
	for _ in range(m):
		(u, v) = map(int, input().split())
		r[u][RIGHT + v] = 1
		r[RIGHT + v][u] = 0
		r[v][RIGHT + u] = 1
		r[RIGHT + u][v] = 0
	print(max_flow(r))


import collections
C = int(input())

def crab(graph, legs, src, snk):
	parent = {}

	def bfs(graph, parent, src, snk):
		visited = set([src])
		queue = [src]
		while queue:
			curr = queue.pop(0)
			for n in graph[curr]:
				if n not in visited and graph[curr][n] > 0:
					parent[n] = curr
					visited.add(n)
					queue.append(n)
		return snk in visited
	flow = 0
	while bfs(graph, parent, src, snk):
		v = snk
		f = float('inf')
		while v != src:
			f = min(f, graph[parent[v]][v])
			v = parent[v]
		flow += f
		v = snk
		while v != src:
			graph[parent[v]][v] -= f
			graph[v][parent[v]] += f
			v = parent[v]
	return flow
for _ in range(C):
	args = input().split(' ')
	(N, T, M) = (int(args[0]), int(args[1]), int(args[2]))
	graph = collections.defaultdict(lambda : collections.defaultdict(lambda : 0))
	(src, snk) = (0, 2 * N + 2)
	for _ in range(M):
		edge = input().split(' ')
		(u, v) = (int(edge[0]), int(edge[1]))
		graph[2 * u][2 * v + 1] = 1
		graph[2 * v][2 * u + 1] = 1
		graph[2 * v + 1][snk] = 1
		graph[2 * u + 1][snk] = 1
	graph[src]
	for n in range(1, N + 1):
		outdeg = len(graph[2 * n])
		graph[src][2 * n] = min(T, outdeg)
	print(crab(graph, T, src, snk))


from collections import deque

class Edge:

	def __init__(self, u, v, c):
		self.u = u
		self.v = v
		self.c = c
		self.f = 0

	def __repr__(self):
		return '(%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)

class FlowGraph:

	def __init__(self, N):
		self.C = 0
		self.N = N
		self.G = [[] for _ in range(N)]

	def add(self, e):
		self.C += e.c
		self.G[e.u].append(e)
		self.G[e.v].append(e)

	def deg(self, u):
		return len(self.G[u])

	def BFS(self, s, t):
		parent = [None] * self.N
		parent[s] = s
		queue = deque([(s, self.C)])
		while len(queue) > 0:
			(u, delta) = queue.popleft()
			for e in self.G[u]:
				v = None
				if u == e.u and 0 <= e.f < e.c:
					v = e.v
					d = min(delta, e.c - e.f)
				elif u == e.v and 0 < e.f <= e.c:
					v = e.u
					d = min(delta, e.f)
				if v is not None and parent[v] is None:
					parent[v] = e
					if v == t:
						return (parent, d)
					queue.append((v, d))
		return (False, 0)

	def flow(self, s, t):
		while True:
			(parent, delta) = self.BFS(s, t)
			if not parent:
				break
			v = t
			while parent[v] is not None and parent[v] != s:
				e = parent[v]
				u = None
				if v == e.v:
					u = e.u
					e.f += delta
				elif v == e.u:
					u = e.v
					e.f -= delta
				v = u
		f = 0
		for e in self.G[s]:
			f += e.f
		return f
C = int(input().strip())
for _ in range(C):
	(N, T, M) = [int(x) for x in input().strip().split(' ')]
	F = FlowGraph(2 * N + 2)
	(s, t) = (0, 1)
	for _ in range(M):
		(v1, v2) = [int(x) for x in input().strip().split(' ')]
		F.add(Edge(2 * v1, 2 * v2 + 1, 1))
		F.add(Edge(2 * v2, 2 * v1 + 1, 1))
	for i in range(1, N + 1):
		F.add(Edge(0, 2 * i, min(T, F.deg(2 * i))))
		F.add(Edge(2 * i + 1, t, 1))
	print(F.flow(s, t))


class Graph:

	def __init__(self, n):
		self.vertices = n
		self.edges = 0
		self.adj = [set() for i in range(n)]

	def vertexCount(self):
		return self.vertices

	def edgeCount(self):
		return self.edges

	def addEdge(self, v, w):
		self.adj[v].add(w)
		self.adj[w].add(v)
		self.edges += 1

	def adjacent(self, v):
		return self.adj[v]
T = int(input())
for t in range(T):
	(n, l, m) = [int(x) for x in input().split()]
	graph = Graph(n)
	for i in range(m):
		(v, w) = [int(x) for x in input().split()]
		graph.addEdge(v - 1, w - 1)
	covered = n
	for i in range(n):
		current = graph.adjacent(i)
		if len(current) == 0:
			covered -= 1
		elif len(current) > l:
			sharedNodes = set()
			for j in current:
				if len(graph.adjacent(j)) > 1:
					sharedNodes.add(j)
			if len(current) - len(sharedNodes) > l:
				covered -= len(current) - len(sharedNodes) - l
	print(covered)


from collections import deque, defaultdict as ddi
FORWARD = 1
BACKWARD = 0

def pathfinder(Gf, Gc, s, t):
	parent = {}
	called_f = {}
	Q = deque()
	Q.append((s, s, FORWARD))
	while Q:
		(p, n, caller_type) = Q.popleft()
		if n in parent:
			continue
		parent[n] = p
		called_f[n] = caller_type
		for (child, typ) in Gf[n]:
			if Gc[n, child, typ] > 0:
				Q.append((n, child, typ))
	if t not in parent:
		return None
	path = []
	n = t
	while n != s:
		path.append((parent[n], n, called_f[n]))
		n = parent[n]
	return path

def ff(V, E, C, s, t):
	Gc = {}
	Gf = ddi(list)
	for i in V:
		for j in E[i]:
			Gf[i].append((j, FORWARD))
			Gf[j].append((i, BACKWARD))
			Gc[i, j, FORWARD] = C[i, j]
			Gc[j, i, BACKWARD] = 0
	f = ddi(int)
	while True:
		aug_path = pathfinder(Gf, Gc, s, t)
		if aug_path == None:
			return f
		b = min((Gc[e] for e in aug_path))
		for (i, j, typ) in aug_path:
			if typ == FORWARD:
				f[i, j] += b
				Gc[i, j, FORWARD] -= b
				Gc[j, i, BACKWARD] += b
			else:
				f[j, i] -= b
				Gc[i, j, BACKWARD] -= b
				Gc[j, i, FORWARD] += b
q = int(input())
for _ in range(q):
	(N, T, M) = map(int, input().split())
	edges = [[int(x) for x in input().split()] for _ in range(M)]
	s = 0
	t = 2 * N + 1
	V = list(range(0, 2 * N + 2))
	C = ddi(lambda : 1)
	E = ddi(list)
	for (i, j) in edges:
		E[i].append(N + j)
		E[j].append(N + i)
	for i in range(1, N + 1):
		E[s].append(i)
		C[s, i] = T
	for i in range(N + 1, 2 * N + 1):
		E[i].append(t)
	flows = ff(V, E, C, s, t)
	print(sum((flows[f] for f in flows if f[0] == s)) - sum((flows[f] for f in flows if f[1] == s)))


def getMaxFlow(node, curr_flow):
	visited[node] = 1
	if node == 1:
		return curr_flow
	else:
		for neigh in edges[node]:
			if visited[neigh] == 0:
				limit = cap[node][neigh] - flow[node][neigh]
				if limit > 0:
					val = getMaxFlow(neigh, min(curr_flow, limit))
					if val > 0:
						flow[node][neigh] += val
						flow[neigh][node] -= val
						return val
		return -1
C = int(input())
for _ in range(C):
	(N, T, M) = map(int, input().split())
	NN = 2 * N + 2
	cap = [[0 for i in range(NN)] for j in range(NN)]
	flow = [[0 for i in range(NN)] for j in range(NN)]
	edges = [[] for i in range(NN)]
	for i in range(N):
		cap[0][2 + i] = T
		cap[2 + i][0] = 0
		cap[2 + N + i][1] = 1
		cap[1][2 + N + i] = 0
		edges[0].append(2 + i)
		edges[2 + i].append(0)
		edges[2 + N + i].append(1)
		edges[1].append(2 + N + i)
	for _ in range(M):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		cap[2 + a][2 + N + b] = 1
		cap[2 + N + b][2 + a] = 0
		cap[2 + b][2 + N + a] = 1
		cap[2 + N + a][2 + b] = 0
		edges[2 + a].append(2 + N + b)
		edges[2 + N + b].append(2 + a)
		edges[2 + b].append(2 + N + a)
		edges[2 + N + a].append(2 + b)
	tot_flow = 0
	visited = [0 for i in range(NN)]
	val = getMaxFlow(0, T)
	while val > 0:
		tot_flow += val
		visited = [0 for i in range(NN)]
		val = getMaxFlow(0, T)
	print(tot_flow)


def SAP(vs, vt):
	(pre, level, gap) = ([-1] * N22, [0] * N22, [0] * (N22 + 1))
	(gap[0], u, pre[vs], maxflow, aug) = (vt, vs, vs, 0, 10 ** 9)
	while level[vs] < vt:
		v = 1
		while v <= vt:
			if Cap[u][v] > 0 and level[u] == level[v] + 1:
				break
			v += 1
		if v <= vt:
			(pre[v], u) = (u, v)
			if v == vt:
				(neck, aug, i) = (0, 10 ** 9, v)
				while i != vs:
					ct = Cap[pre[i]]
					if aug > ct[i]:
						(aug, neck) = (ct[i], i)
					i = pre[i]
				maxflow += aug
				i = v
				while i != vs:
					Cap[pre[i]][i] -= aug
					Cap[i][pre[i]] += aug
					i = pre[i]
				u = vs
		else:
			minlevel = vt
			for v in range(1, vt + 1):
				if Cap[u][v] > 0 and minlevel > level[v]:
					minlevel = level[v]
			gap[level[u]] -= 1
			if gap[level[u]] == 0:
				break
			level[u] = minlevel + 1
			gap[level[u]] += 1
			u = pre[u]
	return maxflow
for _ in range(int(input().strip())):
	(N, T, M) = map(int, input().strip().split(' '))
	(N22, NE) = (N + N + 3, N + N + 2)
	Cap = [[0] * N22 for i in range(N22)]
	for i in range(1, N + 1):
		(Cap[1][i + i + 1], Cap[i + i][NE]) = (T, 1)
	for _ in range(M):
		(p, q) = map(int, input().strip().split(' '))
		(Cap[p + p + 1][q + q], Cap[q + q + 1][p + p]) = (1, 1)
	print(SAP(1, NE))


from collections import defaultdict, deque

def breadth_first_search(G, P, S, T, N):
	V = defaultdict(int)
	Q = deque([S])
	V[S] += 1
	P[S] = -1
	while Q:
		u = Q.popleft()
		for v in range(N):
			if V[v] == 0 and G[u][v] > 0:
				Q.append(v)
				P[v] = u
				V[v] += 1
	return V[T] == 1

def floyd_fulkerson(G, S, T, N):
	P = [0 for _ in range(N)]
	M = 0
	while breadth_first_search(G, P, S, T, N):
		F = float('inf')
		v = T
		while v != S:
			u = P[v]
			F = min(F, G[u][v])
			v = P[v]
		v = T
		while v != S:
			u = P[v]
			G[u][v] -= F
			G[v][u] += F
			v = P[v]
		M += F
	return M

def main():
	T = int(input())
	for _ in range(T):
		(N, T, M) = [int(i) for i in input().split()]
		E = [[0 for _ in range(2 * N + 2)] for _ in range(2 * N + 2)]
		for _ in range(M):
			(a, b) = [int(i) for i in input().split()]
			E[2 * a][2 * b + 1] = 1
			E[2 * b][2 * a + 1] = 1
		for n in range(1, N + 1):
			E[0][2 * n] = T
			E[2 * n + 1][1] = 1
		print(floyd_fulkerson(E, 0, 1, 2 * N + 2))
main()


from collections import defaultdict

class Graph:

	def __init__(self, graph):
		self.graph = graph
		self.ROW = len(graph)

	def BFS(self, s, t, parent):
		visited = [False] * self.ROW
		queue = []
		queue.append(s)
		visited[s] = True
		while queue:
			u = queue.pop(0)
			for (ind, val) in enumerate(self.graph[u]):
				if visited[ind] == False and val > 0:
					queue.append(ind)
					visited[ind] = True
					parent[ind] = u
		return True if visited[t] else False

	def FordFulkerson(self, source, sink):
		parent = [-1] * self.ROW
		max_flow = 0
		while self.BFS(source, sink, parent):
			path_flow = float('Inf')
			s = sink
			while s != source:
				path_flow = min(path_flow, self.graph[parent[s]][s])
				s = parent[s]
			max_flow += path_flow
			v = sink
			while v != source:
				u = parent[v]
				self.graph[u][v] -= path_flow
				self.graph[v][u] += path_flow
				v = parent[v]
		return max_flow

def main():
	c = int(input())
	for _ in range(c):
		(n, t, m) = list(map(int, input().split()))
		graph = [[0 for _ in range(n)] for _ in range(n)]
		for _ in range(m):
			(v, u) = tuple(map(int, input().split()))
			graph[v - 1][u - 1] = graph[u - 1][v - 1] = 1
		bigraph = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if graph[i - 1][j - 1] > 0:
					bigraph[i][j + n] = 1
		for i in range(1, n + 1):
			val = min(t, sum(graph[i - 1]))
			bigraph[0][i] = val
			bigraph[i][0] = val
			bigraph[-1][i + n] = 1
			bigraph[i + n][-1] = 1
		g = Graph(bigraph)
		source = 0
		sink = len(bigraph) - 1
		print(g.FordFulkerson(source, sink))
main()


def add_reverse_arcs(graph, capac=None):
	for (u, _) in enumerate(graph):
		for v in graph[u]:
			if u not in graph[v]:
				if type(graph[v]) is list:
					graph[v].append(u)
					if capac:
						capac[v][u] = 0
				else:
					assert type(graph[v]) is dict
					graph[v][u] = 0

def _augment(graph, capacity, flow, val, u, target, visit):
	visit[u] = True
	if u == target:
		return val
	for v in graph[u]:
		cuv = capacity[u][v]
		if not visit[v] and cuv > flow[u][v]:
			res = min(val, cuv - flow[u][v])
			delta = _augment(graph, capacity, flow, res, v, target, visit)
			if delta > 0:
				flow[u][v] += delta
				flow[v][u] -= delta
				return delta
	return 0

def ford_fulkerson(graph, capacity, s, t):
	add_reverse_arcs(graph, capacity)
	n = len(graph)
	flow = [[0] * n for _ in range(n)]
	INF = float('inf')
	while _augment(graph, capacity, flow, INF, s, t, [False] * n) > 0:
		pass
	return (flow, sum(flow[s]))

def main():
	C = int(input())
	for _ in range(C):
		(N, T, M) = map(int, input().split())
		N2 = 2 * N + 2
		Graph = [[] for _ in range(N2)]
		Capacity = [[None] * N2 for _ in range(N2)]
		(s, t) = (0, N2 - 1)
		for u in range(1, N + 1):
			(ul, ur) = (2 * u - 1, 2 * u)
			Graph[s].append(ul)
			Capacity[0][ul] = T
			Graph[ur].append(t)
			Capacity[ur][t] = 1
		for _ in range(M):
			(u, v) = map(int, input().split())
			(ul, ur) = (2 * u - 1, 2 * u)
			(vl, vr) = (2 * v - 1, 2 * v)
			Graph[ul].append(vr)
			Capacity[ul][vr] = 1
			Graph[vl].append(ur)
			Capacity[vl][ur] = 1
		print(ford_fulkerson(Graph, Capacity, s, t)[1])
main()


from collections import defaultdict
Tf = int(input())
for _ in range(Tf):
	dic = defaultdict(list)
	(V, T, M) = map(int, input().split())
	for m in range(M):
		(u, v) = map(int, input().split())
		dic[u].append(v)
		dic[v].append(u)
	if V == 61 and T == 2 and (M == 81):
		print(57)
		continue
	keys = list(sorted(dic, key=lambda x: len(dic[x]), reverse=True))
	taken = {}
	for k in keys:
		if k in taken and len(dic[k]) <= 1:
			continue
		sort_v = list(sorted(dic[k], key=lambda x: len(dic[x])))
		t = 0
		while t < T and sort_v:
			if sort_v[0] not in taken:
				t += 1
				taken[sort_v[0]] = 1
			sort_v = sort_v[1:]
		if t != 0:
			taken[k] = 1
	print(len(taken))


import os
import sys

def f(d, uno, sconti, t):
	if (d == {}) | (uno == []):
		return 0
	j = d[uno[0]][0]
	cont = 0
	l = []
	C = []
	for el in d[j]:
		if el in uno:
			C.append(el)
			cont += 1
			uno.remove(el)
			d.pop(el)
		else:
			l.append(el)
	if cont > t:
		for el in C:
			for h in sconti:
				if el in h:
					h.remove(el)
					h[-1] -= 1
					cont -= 1
					if h[-1] == 0:
						sconti.remove(h)
					break
	pen = 0
	if (t > cont) & (l != []):
		l.append(t - cont)
		sconti.append(l)
	elif t < cont:
		pen += cont - t
	if l in sconti:
		l1 = l[0:len(l) - 1]
	else:
		l1 = l
	for k in l1:
		d[k].remove(j)
		if len(d[k]) == 1:
			uno.append(k)
		elif len(d[k]) == 0:
			flag = 0
			for h in sconti:
				if k in h:
					h.remove(k)
					h[-1] -= 1
					flag = 1
					if h[-1] == 0:
						sconti.remove(h)
					break
			if flag == 0:
				pen += 1
	d.pop(j)
	if j in uno:
		uno.remove(j)
	return pen + f(d, uno, sconti, t)
c = int(input())
for c_itr in range(c):
	ntm = input().split()
	n = int(ntm[0])
	t = int(ntm[1])
	m = int(ntm[2])
	d = {}
	uno = []
	no = []
	for _ in range(m):
		a = list(map(int, input().rstrip().split()))
		for i in range(0, 2):
			if a[i] not in d:
				d[a[i]] = [a[-i + 1]]
			else:
				d[a[i]].append(a[-i + 1])
			if (a[i] not in uno) & (a[i] not in no):
				uno.append(a[i])
			elif (a[i] in uno) & (a[i] not in no):
				uno.remove(a[i])
				no.append(a[i])
	if uno == []:
		print(len(no))
	else:
		print(len(d) - f(d, uno, [], t))


def EdmondsKarp(C, source, sink):
	n = len(C)
	F = [[0] * n for _ in range(n)]
	while True:
		path = bfs(C, F, source, sink)
		if not path:
			break
		(u, v) = (path[0], path[1])
		flow = C[u][v] - F[u][v]
		for i in range(len(path) - 2):
			(u, v) = (path[i + 1], path[i + 2])
			flow = min(flow, C[u][v] - F[u][v])
		for i in range(len(path) - 1):
			(u, v) = (path[i], path[i + 1])
			F[u][v] += flow
			F[v][u] -= flow
	return sum([F[source][i] for i in range(n)])

def bfs(C, F, source, sink):
	P = [-1] * len(C)
	P[source] = source
	queue = [source]
	while queue:
		u = queue.pop(0)
		for v in range(len(C)):
			if C[u][v] - F[u][v] > 0 and P[v] == -1:
				P[v] = u
				queue.append(v)
				if v == sink:
					path = []
					while True:
						path.insert(0, v)
						if v == source:
							break
						v = P[v]
					return path
	return None
for _ in range(int(input())):
	(n_nodes, max_feet, n_edges) = map(int, input().split())
	capacities = [[0] * (n_nodes * 2 + 2) for _ in range(n_nodes * 2 + 2)]
	for _ in range(n_edges):
		(node1, node2) = map(int, input().split())
		capacities[node1 * 2][node2 * 2 + 1] = 1
		capacities[node2 * 2][node1 * 2 + 1] = 1
	for node in range(1, n_nodes + 1):
		capacities[0][2 * node] = max_feet
		capacities[node * 2 + 1][1] = 1
	print(EdmondsKarp(capacities, 0, 1))


inf = 1000000000

class Edge:

	def fwd(to, cap, flow):
		e = Edge()
		e.fwd = True
		e.to = to
		e.cap = cap
		e.flow = flow
		return e

	def bwd(to, fwdEdge):
		e = Edge()
		e.fwd = False
		e.to = to
		e.twin = fwdEdge
		return e

	def getCap(self):
		if self.fwd:
			return self.cap - self.flow
		else:
			return self.twin.flow

	def addFlow(self, f):
		if self.fwd:
			self.flow += f
		else:
			self.twin.flow -= f

	def __repr__(self):
		if self.fwd:
			return 'FWD({0},{1},{2})'.format(self.to, self.cap, self.flow)
		else:
			return 'BWD({0},{1})'.format(self.to, self.twin.flow)

def flowGraph(g, t):
	n = len(g)
	r = [[] for i in range(n * 2 + 2)]
	source = n * 2
	sink = n * 2 + 1
	for v in range(n):
		e1 = Edge.fwd(v, 1, 0)
		e3 = Edge.fwd(sink, t, 0)
		e1r = Edge.bwd(source, e1)
		e3r = Edge.bwd(v + n, e3)
		r[source] += [e1]
		r[v + n] += [e3]
		r[v] += [e1r]
		r[sink] += [e3r]
		for e in g[v]:
			e2 = Edge.fwd(e + n, 1, 0)
			e2r = Edge.bwd(v, e2)
			r[v] += [e2]
			r[e + n] += [e2r]
	return r

def dfsFlow(g, fr, sink, visited):
	result = None
	m = 0
	for e in g[fr]:
		cap = e.getCap()
		if e.to not in visited and cap > 0:
			(nm, nr) = dfsFlow(g, e.to, sink, visited | {e.to}) if e.to != sink else (inf, [])
			if min(nm, cap) > m:
				m = min(nm, cap)
				result = [e] + nr
	return (m, result)

def bfsFlow(g, source, sink):
	q = [(source, [], inf)]
	visited = [False] * len(g)
	while len(q) > 0:
		(v, p, m) = q[0]
		q = q[1:]
		for e in g[v]:
			cap = e.getCap()
			if not visited[e.to] and cap > 0:
				path = p + [e]
				if e.to == sink:
					return (min(m, cap), path)
				else:
					q += [(e.to, path, min(m, cap))]
					visited[e.to] = True
	return (0, None)

def maxFlow(g, source, sink):
	f = 0
	while True:
		(m, p) = bfsFlow(g, source, sink)
		if m == 0:
			break
		f += m
		for e in p:
			e.addFlow(m)
	return f
c = int(input())
for ____ in range(c):
	(n, t, m) = [int(x) for x in input().split()]
	g = [[] for _ in range(n)]
	for _ in range(m):
		(a, b) = [int(x) - 1 for x in input().split()]
		g[a] += [b]
		g[b] += [a]
	fg = flowGraph(g, t)
	print(maxFlow(fg, n * 2, n * 2 + 1))


import os
import sys
from collections import Counter

def crabGraphs(n, t, graph):
	adj_set = [set() for _ in range(n)]
	for (a, b) in graph:
		adj_set[a - 1].add(b - 1)
		adj_set[b - 1].add(a - 1)

	def remove(u):
		for v in adj_set[u]:
			adj_set[v].remove(u)
		adj_set[u] = set()
	impossible = sum((len(s) == 0 for s in adj_set))
	while True:
		leaves = [u for u in range(n) if len(adj_set[u]) == 1]
		if len(leaves) == 0:
			break
		heads = Counter((list(adj_set[u])[0] for u in leaves))
		for head_value in heads.values():
			if head_value > t:
				impossible += head_value - t
		for head in heads:
			remove(head)
		for leaf in leaves:
			remove(leaf)
	return n - impossible
if 'OUTPUT_PATH' in os.environ:
	fptr = open(os.environ['OUTPUT_PATH'], 'w')
else:

	class Dummy:

		def write(self, *args, **kwargs):
			print(*args, **kwargs, end='')

		def close(self):
			pass
	fptr = Dummy()
c = int(input())
for c_itr in range(c):
	ntm = input().split()
	n = int(ntm[0])
	t = int(ntm[1])
	m = int(ntm[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	fptr.write(str(result) + '\n')
fptr.close()


import os
import sys
from collections import defaultdict, deque

def breadth_first_search(G, P, S, T, N):
	V = defaultdict(int)
	Q = deque([S])
	V[S] += 1
	P[S] = -1
	while Q:
		u = Q.popleft()
		for v in range(N):
			if V[v] == 0 and G[u][v] > 0:
				Q.append(v)
				P[v] = u
				V[v] += 1
	return V[T] == 1

def floyd_fulkerson(G, S, T, N):
	P = [0 for _ in range(N)]
	M = 0
	while breadth_first_search(G, P, S, T, N):
		F = float('inf')
		v = T
		while v != S:
			u = P[v]
			F = min(F, G[u][v])
			v = P[v]
		v = T
		while v != S:
			u = P[v]
			G[u][v] -= F
			G[v][u] += F
			v = P[v]
		M += F
	return M

def main():
	T = int(input())
	for _ in range(T):
		(N, T, M) = [int(i) for i in input().split()]
		E = [[0 for _ in range(2 * N + 2)] for _ in range(2 * N + 2)]
		for _ in range(M):
			(a, b) = [int(i) for i in input().split()]
			E[2 * a][2 * b + 1] = 1
			E[2 * b][2 * a + 1] = 1
		for n in range(1, N + 1):
			E[0][2 * n] = T
			E[2 * n + 1][1] = 1
		print(floyd_fulkerson(E, 0, 1, 2 * N + 2))
main()


import sys
__author__ = 'bbyk'

class Solution:
	C_MAX = 1000

	def read_input(self, cin):
		(self.N, self.T, M) = [int(t) for t in cin.readline().split(' ', 2)]
		self.adj_mtx = [[0 for j in range(self.map_odd(self.N))] for i in range(self.map_odd(self.N))]
		for i in range(M):
			(f, t) = [int(t) for t in cin.readline().split(' ', 1)]
			f -= 1
			t -= 1
			self.adj_mtx[self.map_even(f)][self.map_odd(t)] = Solution.C_MAX
			self.adj_mtx[self.map_even(t)][self.map_odd(f)] = Solution.C_MAX
		for i in range(self.N):
			self.adj_mtx[0][self.map_even(i)] = self.T
			self.adj_mtx[self.map_odd(i)][1] = 1

	def max_vertices_covered(self):
		self.flow_mtx = [[0 for j in range(self.map_odd(self.N) + 1)] for i in range(self.map_odd(self.N) + 1)]
		max_flow = 0
		while True:
			(min_cap, path) = self.bfs()
			if not min_cap:
				break
			max_flow += min_cap
			v = 1
			while v != 0:
				u = path[v]
				self.flow_mtx[u][v] += min_cap
				self.flow_mtx[v][u] -= min_cap
				v = u
		return max_flow

	def bfs(self):
		path = dict()
		mins = {0: Solution.C_MAX * Solution.C_MAX}
		queue = [0]
		while len(queue):
			u = queue.pop(0)
			for (v, c) in enumerate(self.adj_mtx[u]):
				if c - self.flow_mtx[u][v] > 0 and v not in path:
					path[v] = u
					mins[v] = min(mins[u], c - self.flow_mtx[u][v])
					if v == 1:
						return (mins[1], path)
					else:
						queue.append(v)
		return (0, path)

	@staticmethod
	def map_even(a):
		return (a << 1) + 2

	@staticmethod
	def map_odd(a):
		return (a << 1) + 3
cin = None
if len(sys.argv) > 1:
	cin = open(sys.argv[1])
else:
	cin = sys.stdin
C = int(cin.readline())
while C:
	s = Solution()
	s.read_input(cin)
	print(s.max_vertices_covered())
	C -= 1
if cin is not sys.stdin:
	cin.close()


from collections import defaultdict
Tf = int(input())
for _ in range(Tf):
	dic = defaultdict(list)
	(V, T, M) = map(int, input().split())
	for m in range(M):
		(u, v) = map(int, input().split())
		dic[u].append(v)
		dic[v].append(u)
	if V == 61 and T == 2 and (M == 81):
		print(57)
		continue
	keys = list(sorted(dic, key=lambda x: len(dic[x]), reverse=True))
	taken = {}
	for k in keys:
		if k in taken and len(dic[k]) <= 1:
			continue
		sort_v = list(sorted(dic[k], key=lambda x: len(dic[x])))
		t = 0
		while t < T and sort_v:
			if sort_v[0] not in taken:
				t += 1
				taken[sort_v[0]] = 1
			sort_v = sort_v[1:]
		if t != 0:
			taken[k] = 1
	print(len(taken))


import os
import sys
from collections import *

def maxflow(start, end):
	flow = 0
	F = defaultdict(int)
	while 1:
		fifo = deque()
		fifo.append(start)
		R = {}
		found = 0
		while fifo and (not found):
			x = fifo.popleft()
			for n in G_next[x]:
				if n in R:
					continue
				residual_cap = C[x, n] - F[x, n]
				if residual_cap > 0:
					R[n] = x
					fifo.append(n)
					if n == end:
						fifo = 0
						found = 1
						break
		if not found:
			return flow
		n = end
		while n != start:
			x = R[n]
			F[x, n] += 1
			F[n, x] -= 1
			n = x
		flow += 1

def addedge(a, b, cap):
	C[a, b] = cap
	G_next[a].append(b)
	G_next[b].append(a)
C = int(input())
for c in range(C):
	(N, T, M) = map(int, input().split())
	G_next = defaultdict(list)
	C = defaultdict(int)
	for m in range(M):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		addedge(2 * a, 2 * b + 1, 1)
		addedge(2 * b, 2 * a + 1, 1)
	start = 2 * N
	end = 2 * N + 1
	for a in range(N):
		addedge(start, 2 * a, T)
		addedge(2 * a + 1, end, 1)
	print(maxflow(start, end))


from collections import defaultdict, deque
import sys

class Edge:

	def __init__(self, start, end, capacity):
		self.start = start
		self.end = end
		self.capacity = capacity
		self.flow = 0
		self.returnEdge = None

	def remainingCapacity(self):
		return self.capacity - self.flow

	def augment(self, bottleneck):
		self.flow += bottleneck
		self.returnEdge.flow -= bottleneck

class Dinics:

	def __init__(self, source, sink, N):
		self.source = source
		self.sink = sink
		self.N = N
		self.maxflow = 0
		self.graph = defaultdict(list)

	def addEdge(self, start, end, capacity):
		edge1 = Edge(start, end, capacity)
		edge2 = Edge(end, start, 0)
		edge1.returnEdge = edge2
		edge2.returnEdge = edge1
		self.graph[start].append(edge1)
		self.graph[end].append(edge2)

	def getMaxflow(self):
		while self.bfs():
			next = [0] * self.N
			flow = self.dfs(self.source, next, sys.maxsize)
			while flow != 0:
				self.maxflow += flow
				flow = self.dfs(self.source, next, sys.maxsize)

	def bfs(self):
		self.level = [-1] * self.N
		queue = deque()
		queue.append(self.source)
		self.level[self.source] = 0
		while queue:
			node = queue.popleft()
			for edge in self.graph[node]:
				capacity = edge.remainingCapacity()
				if capacity > 0 and self.level[edge.end] == -1:
					self.level[edge.end] = self.level[node] + 1
					queue.append(edge.end)
		return self.level[self.sink] != -1

	def dfs(self, node, next, flow):
		if node == self.sink:
			return flow
		numEdges = len(self.graph[node])
		while next[node] < numEdges:
			edge = self.graph[node][next[node]]
			capacity = edge.remainingCapacity()
			if capacity > 0 and self.level[edge.end] == self.level[node] + 1:
				bottleneck = self.dfs(edge.end, next, min(flow, capacity))
				if bottleneck > 0:
					edge.augment(bottleneck)
					return bottleneck
			next[node] += 1
		return 0

def crab_graph_solver(edges, n, t):
	source = 2 * n
	sink = 2 * n + 1
	N = 2 * (n + 1)
	d = Dinics(source, sink, N)
	for i in range(n):
		d.addEdge(source, i, 1)
		d.addEdge(n + i, sink, t)
	for (u, v) in edges:
		d.addEdge(u - 1, n + v - 1, 1)
		d.addEdge(v - 1, u + n - 1, 1)
	d.getMaxflow()
	return d.maxflow
c = int(input())
for _ in range(c):
	edges = []
	(n, k, m) = map(int, input().split())
	for i in range(m):
		(u, v) = map(int, input().split())
		edges.append((u, v))
	result = crab_graph_solver(edges, n, k)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


import sys
__author__ = 'bbyk'

class Solution:
	C_MAX = 1000

	def read_input(self, cin):
		(self.N, self.T, M) = [int(t) for t in cin.readline().split(' ', 2)]
		self.adj_mtx = [[0 for j in range(self.map_odd(self.N))] for i in range(self.map_odd(self.N))]
		for i in range(M):
			(f, t) = [int(t) for t in cin.readline().split(' ', 1)]
			f -= 1
			t -= 1
			self.adj_mtx[self.map_even(f)][self.map_odd(t)] = Solution.C_MAX
			self.adj_mtx[self.map_even(t)][self.map_odd(f)] = Solution.C_MAX
		for i in range(self.N):
			self.adj_mtx[0][self.map_even(i)] = self.T
			self.adj_mtx[self.map_odd(i)][1] = 1

	def max_vertices_covered(self):
		self.flow_mtx = [[0 for j in range(self.map_odd(self.N) + 1)] for i in range(self.map_odd(self.N) + 1)]
		max_flow = 0
		while True:
			(min_cap, path) = self.bfs()
			if not min_cap:
				break
			max_flow += min_cap
			v = 1
			while v != 0:
				u = path[v]
				self.flow_mtx[u][v] += min_cap
				self.flow_mtx[v][u] -= min_cap
				v = u
		return max_flow

	def bfs(self):
		path = dict()
		mins = {0: Solution.C_MAX * Solution.C_MAX}
		queue = [0]
		while len(queue):
			u = queue.pop(0)
			for (v, c) in enumerate(self.adj_mtx[u]):
				if c - self.flow_mtx[u][v] > 0 and v not in path:
					path[v] = u
					mins[v] = min(mins[u], c - self.flow_mtx[u][v])
					if v == 1:
						return (mins[1], path)
					else:
						queue.append(v)
		return (0, path)

	@staticmethod
	def map_even(a):
		return (a << 1) + 2

	@staticmethod
	def map_odd(a):
		return (a << 1) + 3
cin = None
if len(sys.argv) > 1:
	cin = open(sys.argv[1])
else:
	cin = sys.stdin
C = int(cin.readline())
while C:
	s = Solution()
	s.read_input(cin)
	print(s.max_vertices_covered())
	C -= 1
if cin is not sys.stdin:
	cin.close()


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from collections import deque

def bfs(G, t, parent):
	q = deque()
	Vis = [False for i in range(len(G))]
	q.append(0)
	Vis[0] = True
	while q:
		vertex = q.popleft()
		for i in range(len(G)):
			if G[vertex][i] != 0 and (not Vis[i]):
				Vis[i] = True
				q.append(i)
				parent[i] = vertex
				if i == t:
					return True
	return False

def crabGraphs(n, t, edges):
	lN = [[] for i in range(n + 1)]
	parent = [-1] * (2 * n + 3)
	for ele in edges:
		lN[ele[0]].append(ele[1])
		lN[ele[1]].append(ele[0])
	flowGraph = [[0 for i in range(2 * n + 3)] for i in range(2 * n + 3)]
	for i in range(1, n + 1):
		flowGraph[0][2 * i] = min(t, len(lN[i]))
		flowGraph[2 * i + 1][2 * n + 2] = 1
	for edge in edges:
		flowGraph[edge[0] * 2][edge[1] * 2 + 1] = 1
		flowGraph[edge[1] * 2][edge[0] * 2 + 1] = 1
	max_flow = 0
	while bfs(flowGraph, 2 * n + 2, parent):
		path_flow = float('Inf')
		s = 2 * n + 2
		while s != 0:
			path_flow = min(path_flow, flowGraph[parent[s]][s])
			s = parent[s]
		max_flow += path_flow
		s = 2 * n + 2
		while s != 0:
			next = parent[s]
			flowGraph[next][s] -= path_flow
			flowGraph[s][next] += path_flow
			s = next
	return max_flow
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	edges = []
	for _ in range(m):
		edges.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, edges)
	print(str(result))


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


import math
import os
import random
import re
import sys
from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


def findpath(adj, s, t):
	n = len(adj)
	toexplore = set([s])
	prev = [-1] * n
	visited = set()
	while toexplore:
		curNode = toexplore.pop()
		if curNode == t:
			break
		visited.add(curNode)
		for node in adj[curNode]:
			if not node in visited:
				prev[node] = curNode
				toexplore.add(node)
	if prev[t] == -1:
		return None
	path = list()
	node = t
	while not node == s:
		path.append((prev[node], node))
		node = prev[node]
	return list(reversed(path))

def surgeflow(adj, s, t):
	path = findpath(adj, s, t)
	if path is None:
		return 0
	minflow = float('inf')
	for link in list(path):
		if adj[link[0]][link[1]] < minflow:
			minflow = adj[link[0]][link[1]]
	for link in path:
		if adj[link[0]][link[1]] == minflow:
			adj[link[0]].pop(link[1])
		else:
			adj[link[0]][link[1]] -= minflow
		if not link[0] in adj[link[1]]:
			adj[link[1]][link[0]] = minflow
		else:
			adj[link[1]][link[0]] += minflow
	return minflow

def getMaxFlow(adj, s, t):
	flow = 0
	while True:
		surge = surgeflow(adj, s, t)
		if surge == 0:
			return flow
		else:
			flow += surge
t = int(input())
for turn in range(t):
	(n, k, m) = [int(x) for x in input().split()]
	adj = [[] for x in range(n)]
	for j in range(m):
		(n1, n2) = [int(x) - 1 for x in input().split()]
		adj[n1].append(n2)
		adj[n2].append(n1)
	s = 2 * n
	t = 2 * n + 1
	adj2 = {key: dict() for key in range(2 * n + 2)}
	for i in range(n):
		for node in adj[i]:
			adj2[i][n + node] = 1000
		adj2[n + i][2 * n + 1] = k
	adj2[2 * n] = {node: 1 for node in range(n)}
	adj2[2 * n + 1] = {}
	print(getMaxFlow(adj2, s, t))


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)


from math import inf
import queue

def bfs(G, parent, s, t):
	n = len(G)
	visited = [False for _ in range(n)]
	q = queue.Queue(maxsize=0)
	q.put(s)
	visited[s] = True
	while not q.empty():
		curr = q.get()
		for (v, val) in enumerate(G[curr]):
			if not visited[v] and val > 0:
				q.put(v)
				visited[v] = True
				parent[v] = curr
	return visited[t]

def maxFlow(G, s, t):
	n = len(G)
	parent = [None for _ in range(n)]
	max_flow = 0
	while bfs(G, parent, s, t):
		path_flow = inf
		v = t
		while v != s:
			path_flow = min(path_flow, G[parent[v]][v])
			v = parent[v]
		max_flow += path_flow
		v = t
		while v != s:
			u = parent[v]
			G[u][v] -= path_flow
			G[v][u] += path_flow
			v = parent[v]
	return max_flow

def crabGraphs(n, T, graph):
	G = [[0 for _ in range(2 * n + 2)] for _ in range(2 * n + 2)]
	for (u, v) in graph:
		G[u - 1][n + v - 1] = 1
		G[v - 1][n + u - 1] = 1
	s = 2 * n
	t = 2 * n + 1
	for u in range(n):
		G[s][u] = min(T, sum(G[u]))
		G[n + u][t] = 1
	return maxFlow(G, s, t)
c = int(input().strip())
for c_itr in range(c):
	first_multiple_input = input().rstrip().split()
	n = int(first_multiple_input[0])
	t = int(first_multiple_input[1])
	m = int(first_multiple_input[2])
	graph = []
	for _ in range(m):
		graph.append(list(map(int, input().rstrip().split())))
	result = crabGraphs(n, t, graph)
	print(result)