Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

Chefland consists of $N$ provinces (numbered $1$ through $N$) connected by $M$ bidirectional roads (numbered $1$ through $M$). For each valid $i$, the $i$-th road connects provinces $U_{i}$ and $V_{i}$. It is possible to travel from each province to any other province using these roads.

For each valid $i$, the annual income of the $i$-th province is $A_{i}$ and its population is $B_{i}$. The per-capita income of some provinces is lower than that of some other provinces. For this reason, the king of Chefland wants to choose one or more provinces to keep in his kingdom and abandon the rest, in such a way that the per-capita income of the whole resulting kingdom, i.e. the sum of annual incomes of the chosen provinces divided by the sum of their populations, would be maximum possible. However, it should also be possible to travel from each of the chosen provinces to any other chosen province without visiting any of the abandoned provinces. Among all such ways to form the new kingdom, the king would prefer the number of chosen provinces to be as large as possible.

Can you help the king choose which provinces should form the new kingdom? If there are multiple solutions that maximise the per-capita income, you should choose one with the maximum number of chosen provinces. If there are still multiple solutions, you may choose any one.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $M$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.
The third line contains $N$ space-separated integers $B_{1}, B_{2}, \ldots, B_{N}$.
$M$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $U_{i}$ and $V_{i}$.

------  Output ------
Print two lines.
The first of these lines should contain a single integer $K$ denoting the number of provinces the king should choose.
The second line should contain $K$ space-separated integers denoting these provinces.

------  Constraints ------
$1 ≤ T ≤ 5$
$1 ≤ N, M ≤ 2 \cdot 10^{5}$
$1 ≤ U_{i}, V_{i} ≤ N$ for each valid $i$
$U_{i} \neq V_{i}$ for each valid $i$
there is at most one road between each pair of provinces
$0 ≤ A_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ B_{i} ≤ 10^{9}$ for each valid $i$

----- Sample Input 1 ------ 
1

3 3

10 1 2

5 1 1 

1 2

2 3

1 3
----- Sample Output 1 ------ 
2

1 3
----- explanation 1 ------ 
If the king chooses provinces $1$ and $3$, then the per-capita income is $\frac{10 + 2}{5 + 1} = 2$. This is the only optimal solution.

Source: codechef | Difficulty: HARD
Tags: Graph algorithms

Data structures

Graph traversal

Mathematics


Solutions:
T = int(input())
for i in range(T):
	l = []
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for j in range(n):
		l.append([])
	for k in range(m):
		(x, y) = map(int, input().split())
		l[x - 1].append(y - 1)
		l[y - 1].append(x - 1)
	r = [a[i] / b[i] for i in range(n)]
	m = max(r)
	final = []
	visited = [0] * n
	for i in range(n):
		if r[i] == m:
			if visited[i] == 0:
				visited[i] = 1
				temp = [i + 1]
				q = [i]
				while len(q):
					t = q.pop(0)
					for j in l[t]:
						if r[j] == m and visited[j] == 0:
							visited[j] = 1
							temp.append(j + 1)
							q.append(j)
				if len(temp) > len(final):
					final = temp.copy()
	print(len(final))
	for i in final:
		print(i, end=' ')


from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

def dfs(p):
	v[p] = True
	x.append(p)
	for i in child[p]:
		if mx == a[i - 1] / b[i - 1] and (not v[i]):
			dfs(i)
for T in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	mx = 0
	for i in range(n):
		mx = max(mx, a[i] / b[i])
	child = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, input().split())
		child[u].append(v)
		child[v].append(u)
	(pro, x) = ([], [])
	v = [False] * (n + 1)
	for i in range(n):
		if mx == a[i] / b[i] and (not v[i + 1]):
			dfs(i + 1)
			if len(x) > len(pro):
				pro = x[:]
			x = []
	print(len(pro))
	print(*pro)


import sys
sys.setrecursionlimit(int(1000000.0))

def func(ver, A, B, graph, vis, mex, pci, lst):
	vis.add(ver)
	lst.append(ver)
	tot = 0
	for neigh in graph[ver]:
		if neigh not in vis:
			if pci[neigh - 1] == mex:
				tot += 1 + func(neigh, A, B, graph, vis, mex, pci, lst)
	return tot
for t in range(int(input())):
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	from collections import defaultdict
	graph = defaultdict(list)
	for i in range(m):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
	pci = [None for i in range(n)]
	for i in range(n):
		pci[i] = A[i] // B[i]
	mex = -sys.maxsize
	for i in range(n):
		if A[i] // B[i] > mex:
			mex = A[i] // B[i]
			ver = i + 1
	nls = []
	for (i, j) in enumerate(pci):
		if j == mex:
			nls.append(i)
	flis = []
	flen = 0
	vis = set()
	for ver in nls:
		if ver not in vis:
			lst = []
			lnlis = 1 + func(ver + 1, A, B, graph, vis, mex, pci, lst)
			if lnlis > flen:
				flen = lnlis
				flis = lst[:]
	print(flen)
	print(*flis)


def root(component, u):
	while component[u][0] != u:
		u = component[u][0]
	return u

def union(component, u, v):
	u_root = root(component, u)
	v_root = root(component, v)
	if u_root != v_root:
		if component[u_root][1] < component[v_root][1]:
			component[u_root][0] = component[v_root][0]
			component[v_root][1] += component[u_root][1]
		else:
			component[v_root][0] = component[u_root][0]
			component[u_root][1] += component[v_root][1]
for _ in range(int(input())):
	(n, m) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	b = list(map(int, input().strip().split()))
	maxcapita = -1
	for i in range(n):
		capita = a[i] / b[i]
		if capita > maxcapita:
			maxcapita = capita
	component = {}
	for i in range(n):
		if maxcapita == a[i] / b[i]:
			component[i] = [i, 1]
	for i in range(m):
		(u, v) = map(int, input().strip().split())
		if a[u - 1] / b[u - 1] == maxcapita and a[v - 1] / b[v - 1] == maxcapita:
			union(component, u - 1, v - 1)
	max_city = None
	max_component_size = 1
	for key in component.keys():
		if component[key][1] >= max_component_size:
			max_city = key
			max_component_size = component[key][1]
	print(max_component_size)
	ans = []
	for key in component.keys():
		if root(component, key) == max_city:
			ans.append(key + 1)
	print(*ans)


import sys
sys.setrecursionlimit(100000)

class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V)]

	def DFSUtil(self, temp, v, visited):
		visited[v] = True
		temp.append(v)
		for i in self.adj[v]:
			if visited[i] == False:
				temp = self.DFSUtil(temp, i, visited)
		return temp

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.adj[w].append(v)

	def connectedComponents(self):
		visited = []
		cc = []
		for i in range(self.V):
			visited.append(False)
		for v in range(self.V):
			if visited[v] == False:
				temp = []
				cc.append(self.DFSUtil(temp, v, visited))
		return cc
t = int(input())
for _ in range(t):
	(n, m) = list(map(lambda x: int(x), input().split()))
	a = list(map(lambda x: int(x), input().split()))
	b = list(map(lambda x: int(x), input().split()))
	hashmap = {}
	total_a = sum(a)
	total_b = sum(b)
	total_pc = total_a / total_b
	pc = []
	for i in range(len(a)):
		pc.append((a[i] / b[i], i, (total_a - a[i]) / (total_b - b[i])))
	maximum = max(pc, key=lambda x: x[0])[0]
	nodes_to_consider = set()
	for i in range(0, len(pc)):
		if pc[i][0] == maximum:
			nodes_to_consider.add(pc[i][1])
	nodes_vs_id = {node: i for (i, node) in enumerate(nodes_to_consider)}
	id_vs_node = {v: k for (k, v) in nodes_vs_id.items()}
	g = Graph(len(nodes_to_consider) + 1)
	for _ in range(m):
		(u, v) = list(map(lambda x: int(x), input().split()))
		if u - 1 in nodes_to_consider and v - 1 in nodes_to_consider:
			g.addEdge(nodes_vs_id[u - 1], nodes_vs_id[v - 1])
	components = sorted(g.connectedComponents(), key=lambda x: len(x), reverse=True)
	print(len(components[0]))
	for node in components[0]:
		print(id_vs_node[node] + 1, end=' ')
	print()


import collections
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

def dfs(p):
	visited.add(p)
	temp.add(p + 1)
	for node in road[p]:
		if node not in visited and selected[node]:
			dfs(node)
	return temp
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	income = list(map(int, input().split()))
	population = list(map(int, input().split()))
	road = collections.defaultdict(list)
	for __ in range(m):
		(a, b) = map(int, input().split())
		road[a - 1].append(b - 1)
		road[b - 1].append(a - 1)
	i = income[0]
	p = population[0]
	for x in range(1, n):
		if i * population[x] < p * income[x]:
			i = income[x]
			p = population[x]
	selected = [False] * n
	for x in range(n):
		if population[x] * i == income[x] * p:
			selected[x] = True
	visited = set()
	ans = set()
	for each in range(n):
		if each not in visited and selected[each]:
			temp = set()
			dfs(each)
			if len(temp) > len(ans):
				ans = temp
	print(len(ans))
	for ele in ans:
		print(ele, end=' ')


from sys import stdin, stdout
T = int(stdin.readline().strip())
for _ in range(T):
	(N, M) = map(int, stdin.readline().strip().split())
	A = list(map(int, stdin.readline().strip().split()))
	B = list(map(int, stdin.readline().strip().split()))
	per_capita = [A[i] / B[i] for i in range(N)]
	max_pci = max(per_capita)
	cities = {i + 1 for i in range(N) if per_capita[i] == max_pci}
	roads = dict()
	for city in cities:
		roads[city] = []
	for _ in range(M):
		(u, v) = map(int, stdin.readline().strip().split())
		if u in cities and v in cities:
			roads[u].append(v)
			roads[v].append(u)
	visited = [False for _ in range(N + 1)]
	max_kingdom = []
	while len(cities) != 0:
		vert = cities.pop()
		if visited[vert]:
			continue
		stack = set([vert])
		kingdom = set([vert])
		while len(stack) != 0:
			node = stack.pop()
			if visited[node]:
				continue
			while roads[node] != []:
				x = roads[node].pop(0)
				if visited[x]:
					continue
				else:
					stack.add(x)
					kingdom.add(x)
			visited[node] = True
		if len(max_kingdom) < len(kingdom):
			max_kingdom = kingdom & kingdom
	print(len(max_kingdom))
	print(*max_kingdom, sep=' ')


import sys
input = sys.stdin.readline
from collections import defaultdict, deque
from bisect import bisect_right
for T in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = defaultdict(list)
	for i in range(m):
		(u, v) = list(map(int, input().split()))
		d[u].append(v)
		d[v].append(u)
	c = []
	for i in range(n):
		c.append((a[i] // b[i], i + 1))
	c.sort(key=lambda x: x[0], reverse=True)
	mx = c[0][0]
	ind = 1
	for i in range(n):
		if c[i][0] != mx:
			ind = i
			break
	if ind == 1 and c[ind][0] == mx:
		print(n)
		for i in c:
			print(i[1], end=' ')
		print('\n', end='')
		continue
	node = []
	di = {}
	for i in range(ind):
		node.append(c[i][1])
		di[c[i][1]] = 1
	vis = [False] * (n + 1)
	dis = defaultdict(list)
	mx_len = 0
	for i in range(len(node)):
		if vis[node[i]] == False:
			q = deque()
			q.append(node[i])
			while q:
				p = q.popleft()
				vis[p] = True
				for j in d[p]:
					if di.get(j, 0) and vis[j] == False:
						vis[j] = True
						q.append(j)
						dis[node[i]].append(j)
						mx_len = max(mx_len, len(dis[node[i]]))
	for j in dis:
		if len(dis[j]) == mx_len:
			print(mx_len + 1)
			print(j, end=' ')
			print(*dis[j])
			break


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)

class Graph:

	def __init__(self):
		self.edges = defaultdict(list)

	def addedge(self, u, v):
		self.edges[u].append(v)
		self.edges[v].append(u)

	def dfs(self, visited, a, u):
		a.append(u)
		visited[u] = True
		for v in self.edges[u]:
			if not visited[v]:
				self.dfs(visited, a, v)
t = int(input())
for _ in range(t):
	(N, M) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	(a, b) = (A[0], B[0])
	for i in range(N):
		if a * B[i] < A[i] * b:
			(a, b) = (A[i], B[i])
	province = [False] * (N + 1)
	for i in range(N):
		if a * B[i] == b * A[i]:
			province[i + 1] = True
	g = Graph()
	for i in range(M):
		(u, v) = map(int, input().split())
		if province[u] and province[v]:
			g.addedge(u, v)
	c = []
	visited = [False] * (N + 1)
	for i in range(1, N + 1):
		if province[i] and (not visited[i]):
			a = []
			g.dfs(visited, a, i)
			c.append(a[:])
	p = max(c, key=len)
	print(len(p))
	print(' '.join(map(str, p)))


from collections import defaultdict
limit = 3 * pow(10, 5)

def get_parent(dsu, e):
	while dsu[e] > -1:
		e = dsu[e]
	return e

def get_ans(n, m, inc, popu, arr):
	max_pci = 0
	max_prov = set()
	for i in range(n):
		tmp = inc[i] / popu[i]
		if tmp > max_pci:
			max_prov.clear()
			max_prov.add(i)
			max_pci = tmp
		elif tmp == max_pci:
			max_prov.add(i)
	dsu = [-1] * n
	for i in range(m):
		(j, k) = arr[i]
		j -= 1
		k -= 1
		if j not in max_prov:
			dsu[j] = limit
		if k not in max_prov:
			dsu[k] = limit
		if j in max_prov and k in max_prov:
			par_j = get_parent(dsu, j)
			par_k = get_parent(dsu, k)
			if par_j == j and par_k == k or par_j != par_k:
				if dsu[par_j] < dsu[par_k]:
					dsu[par_j] += dsu[par_k]
					dsu[par_k] = par_j
				else:
					dsu[par_k] += dsu[par_j]
					dsu[par_j] = par_k
	for i in max_prov:
		tmp = get_parent(dsu, i)
		if tmp != i:
			dsu[i] = tmp
	max_len = -float('inf')
	ans_key = 0
	ans_dic = defaultdict(list)
	for i in range(n):
		if dsu[i] != limit:
			if dsu[i] < 0 and abs(dsu[i]) > max_len:
				max_len = abs(dsu[i])
				ans_key = i
				ans_dic[i].append(i + 1)
			else:
				ans_dic[dsu[i]].append(i + 1)
	print(max_len)
	print(*ans_dic[ans_key], sep=' ')
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	inc = list(map(int, input().split()))
	popu = list(map(int, input().split()))
	arr = []
	for _ in range(m):
		arr.append(list(map(int, input().split())))
	get_ans(n, m, inc, popu, arr)


from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

def dfs(u):
	if vis[u]:
		return
	vis[u] = True
	p.append(u + 1)
	for v in g[u]:
		dfs(v)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = [a[i] // b[i] for i in range(n)]
	g = [[] for _ in range(n)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		g[u].append(v)
		g[v].append(u)
	p = []
	maxi = max(c)
	vis = [False] * n
	for i in range(n):
		if c[i] != maxi:
			vis[i] = True
	ans = []
	for u in range(n):
		if not vis[u]:
			dfs(u)
			if len(p) > len(ans):
				ans = p
			p = []
	print(len(ans))
	print(*ans)


from collections import defaultdict

def bfs(src):
	v[src] = 1
	q = []
	q.append(src)
	while q:
		s = q.pop(0)
		for i in d[s]:
			if i in v and v[i] == 0:
				v[i] = 1
				q.append(i)
				d1[src].append(i)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = defaultdict(list)
	for i in range(m):
		(u, v) = map(int, input().split())
		d[u].append(v)
		d[v].append(u)
	l1 = []
	for i in range(n):
		l1.append(a[i] / b[i])
	z = max(l1)
	l = []
	for i in range(n):
		if l1[i] == z:
			l.append(i + 1)
	v = {}
	for i in range(len(l)):
		v[l[i]] = 0
	d1 = defaultdict(list)
	(cnt, z) = (0, -1)
	for i in range(len(l)):
		if v[l[i]] == 0:
			bfs(l[i])
			d1[l[i]].append(l[i])
			if len(d1[l[i]]) > cnt:
				cnt = len(d1[l[i]])
				z = l[i]
	print(cnt)
	print(*d1[z])


from collections import defaultdict
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

def dfs(edges, temp, visited, src, A, B, max_per_capita):
	visited[src] = True
	for i in range(len(edges[src])):
		if visited[edges[src][i]] == False and A[edges[src][i]] / B[edges[src][i]] == max_per_capita:
			temp.append(edges[src][i])
			dfs(edges, temp, visited, edges[src][i], A, B, max_per_capita)

def main():
	T = int(input())
	for _ in range(T):
		(N, M) = map(int, input().split())
		A = list(map(int, input().split()))
		B = list(map(int, input().split()))
		edges = defaultdict(list)
		for _ in range(M):
			(u, v) = map(int, input().split())
			edges[u - 1].append(v - 1)
			edges[v - 1].append(u - 1)
		max_per_capita = 0
		max_inc_provinces = []
		for i in range(N):
			if max_per_capita < A[i] / B[i]:
				max_per_capita = A[i] / B[i]
				max_inc_provinces = [i]
			elif max_per_capita == A[i] / B[i]:
				max_inc_provinces.append(i)
		visited = [False] * N
		finalProvinces = []
		for i in range(len(max_inc_provinces)):
			if visited[max_inc_provinces[i]] == False:
				temp = [max_inc_provinces[i]]
				dfs(edges, temp, visited, max_inc_provinces[i], A, B, max_per_capita)
				if len(temp) > len(finalProvinces):
					finalProvinces = temp
		print(len(finalProvinces))
		for val in finalProvinces:
			print(val + 1, end=' ')
main()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def dfs(n, vis, adj, temp):
	vis[n] = 1
	temp += [n]
	for i in adj[n]:
		if vis[i] == 0:
			vis[i] = 1
			dfs(i, vis, adj, temp)
	return temp
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	adj = [[] for i in range(n + 1)]
	vis = [0] * (n + 1)
	mx = 0
	for i in range(0, n):
		mx = max(mx, a[i] // b[i])
	fg = 0
	for i in range(m):
		(c, d) = map(int, input().split())
		if a[c - 1] // b[c - 1] == mx and a[d - 1] // b[d - 1] == mx:
			adj[c].append(d)
			adj[d].append(c)
			fg = 1
	if fg == 0:
		print(1)
		for i in range(0, n):
			if a[i] // b[i] == mx:
				print(i)
				break
	else:
		ans = []
		mxcc = 0
		for i in range(0, n):
			if vis[i] == 0:
				tmp = dfs(i, vis, adj, [])
			if len(tmp) > mxcc:
				ans = tmp[:]
				mxcc = len(tmp)
		print(mxcc)
		print(*ans)


from collections import deque
import sys
inp = iter(sys.stdin.read().split('\n'))
input = lambda : next(inp)

def bfs(node, m):
	visited[node] = True
	q = deque([node])
	count = 1
	li = [node]
	while len(q) > 0:
		v = q.popleft()
		for i in graph[v]:
			if dic[i][0] == m and (not visited[i]):
				visited[i] = True
				count += 1
				li.append(i)
				q.append(i)
	return [count, li]
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	dic = {}
	graph = {}
	ma = 0
	for i in range(n):
		dic[i + 1] = [a[i] / b[i], a[i], b[i]]
		ma = max(ma, a[i] / b[i])
		graph[i + 1] = []
	for x in range(m):
		(a, b) = map(int, input().split())
		graph[a].append(b)
		graph[b].append(a)
	visited = [False] * (n + 1)
	ans = 0
	ans2 = []
	for i in range(1, n):
		if dic[i][0] == ma and (not visited[i]):
			temp = bfs(i, ma)
			if ans < temp[0]:
				ans = temp[0]
				ans2 = temp[1]
	print(ans)
	print(*ans2)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	E = []
	for i in range(m):
		(x, y) = map(int, input().split())
		E.append([x, y])
	ab = [0] * n
	for i in range(n):
		ab[i] = A[i] / B[i]
	ma = max(ab)
	graph = {}
	unvisited = set()
	visited = {}
	for i in range(n):
		if ab[i] == ma:
			unvisited.add(i)
			visited[i] = -1
			graph[i] = []
	for i in range(m):
		(x, y) = (E[i][0], E[i][1])
		if ab[x - 1] == ab[y - 1] == ma:
			graph[x - 1].append(y - 1)
			graph[y - 1].append(x - 1)
	ans = 0
	arr1 = []
	while unvisited:
		source = unvisited.pop()
		queue = [source]
		visited[source] = 1
		count = 1
		arr2 = []
		arr2.append(source + 1)
		while queue:
			head = queue.pop()
			for neigh in graph[head]:
				if visited[neigh] == -1:
					count += 1
					visited[neigh] = 1
					unvisited.remove(neigh)
					arr2.append(neigh + 1)
					queue.append(neigh)
		if ans < count:
			ans = count
			arr1 = arr2[:]
	print(ans)
	print(*arr1)


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)
t = int(input())

def dfs(v, adj, visit, res):
	visit[v] = 1
	res.append(v + 1)
	for i in adj[v]:
		if visit[i] == 0:
			dfs(i, adj, visit, res)
	return res
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	mx = -1
	start = -1
	for i in range(n):
		if a[i] / b[i] > mx:
			mx = a[i] / b[i]
			start = i
	adj = defaultdict(lambda : [])
	flag = 0
	for i in range(m):
		(x, y) = map(int, input().split())
		if a[x - 1] / b[x - 1] == mx and a[y - 1] / b[y - 1] == mx:
			adj[x - 1].append(y - 1)
			adj[y - 1].append(x - 1)
			flag = 1
	if flag == 0:
		print(1)
		print(start + 1)
	else:
		visit = [0 for i in range(n)]
		mxans = 0
		final = []
		for i in range(n):
			if visit[i] == 0:
				temp = dfs(i, adj, visit, [])
				n1 = len(temp)
				if n1 > mxans:
					mxans = n1
					final = temp
		print(mxans)
		print(*final)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return int(input())

def dfs(adj, node, vi, traversal):
	traversal += [node]
	vi[node] = 1
	for j in adj[node]:
		if vi[j] == 0:
			vi[j] = 1
			dfs(adj, j, vi, traversal)
	return traversal
try:
	for _ in range(inin()):
		(n, m) = cin()
		A = ain()
		B = ain()
		maxPerCapInc = 0
		for i in range(n):
			maxPerCapInc = max(maxPerCapInc, A[i] // B[i])
		adj = [[] for i in range(n + 1)]
		visited = [0] * (n + 1)
		graphExists = 0
		for i in range(m):
			(u, v) = cin()
			if A[u - 1] // B[u - 1] == maxPerCapInc and A[v - 1] // B[v - 1] == maxPerCapInc:
				adj[u].append(v)
				adj[v].append(u)
				graphExists = 1
		if graphExists == 0:
			print(1)
			for i in range(n):
				if A[i] // B[i] == maxPerCapInc:
					print(i + 1)
					break
		else:
			maxLenDfs = []
			Len = 0
			for node in range(n + 1):
				if visited[node] == 0:
					ans = dfs(adj, node, visited, [])
				if len(ans) > Len:
					Len = len(ans)
					maxLenDfs = ans
			print(Len)
			print(*maxLenDfs)
except:
	pass


import sys
import bisect as b
import math
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
mo = 10 ** 9 + 7

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return int(input())

def dfs(adj, node, vi, ans):
	vi[node] = 1
	ans += [node]
	for j in adj[node]:
		if vi[j] == 0:
			vi[j] = 1
			dfs(adj, j, vi, ans)
	return ans
for i in range(inin()):
	(n, m) = cin()
	vi = [0] * (n + 1)
	adj = [[] for i in range(n + 1)]
	a = ain()
	b = ain()
	ma = 0
	f = 0
	for i in range(n):
		ma = max(a[i] // b[i], ma)
	for i in range(m):
		(u, v) = cin()
		if a[u - 1] // b[u - 1] == ma and a[v - 1] // b[v - 1] == ma:
			adj[u].append(v)
			adj[v].append(u)
			f = 1
	if not f:
		print(1)
		for i in range(n):
			if a[i] // b[i] == ma:
				print(i + 1)
				break
	else:
		maxcc = 0
		ans = []
		for i in range(n + 1):
			if vi[i] == 0:
				temp = dfs(adj, i, vi, [])
			if len(temp) > maxcc:
				maxcc = len(temp)
				ans = temp
		print(maxcc)
		print(*ans)


def dfs(u, temp, dom, v):
	stack = []
	stack.append(u)
	v[u] = True
	temp.append(u + 1)
	while stack:
		e = stack.pop()
		for i in dom[e]:
			if not v[i]:
				stack.append(i)
				v[i] = True
				temp.append(i + 1)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	hest = 0
	for i in range(n):
		tmp = a[i] / b[i]
		if tmp > hest:
			hest = tmp
	dom = {}
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		if a[u] / b[u] < hest or a[v] / b[v] < hest:
			continue
		if u not in dom:
			dom[u] = []
		dom[u].append(v)
		if v not in dom:
			dom[v] = []
		dom[v].append(u)
	v = [False] * n
	longest = []
	for i in dom:
		if not v[i]:
			temp = []
			dfs(i, temp, dom, v)
			if len(temp) > len(longest):
				longest = temp
	print(len(longest))
	print(*longest, sep=' ')


import collections
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

def fun(node):
	if visited[node]:
		return
	p.append(node + 1)
	visited[node] = True
	for j in g[node]:
		fun(j)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append(a[i] / b[i])
	g = collections.defaultdict(list)
	for i in range(m):
		(u, v) = map(int, input().split())
		g[u - 1].append(v - 1)
		g[v - 1].append(u - 1)
	p = []
	ans = []
	mx = max(l)
	visited = [False] * n
	for i in range(n):
		if l[i] != mx:
			visited[i] = True
	for i in range(n):
		if not visited[i]:
			fun(i)
			if len(p) > len(ans):
				ans = p
			p = []
	print(len(ans))
	print(*ans)


from sys import setrecursionlimit
import collections
setrecursionlimit(10 ** 9)
co = 0

class graph:

	def goodnodes(self, roads, good, n):
		king = collections.defaultdict(list)
		for (u, v) in roads:
			if good[u - 1] == 1 and good[v - 1] == 1:
				king[u].append(v)
				king[v].append(u)

		def dfs(node, visited, te):
			if visited[node] == 0:
				visited[node] = 1
				te.append(node)
				global co
				co = co + 1
				if node in king:
					for nei in king[node]:
						if visited[nei] == 0:
							dfs(nei, visited, te)
			return te
		visited = [0] * (n + 1)
		fina = []
		m = 0
		for j in range(0, n):
			if good[j] == 1 and visited[j + 1] != 1:
				te = []
				global co
				co = 0
				fi = dfs(j + 1, visited, te)
				if co > m:
					fina = fi[:]
					m = co
		return fina
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = [int(v) for v in input().split()]
	b = [int(v) for v in input().split()]
	roads = []
	for j in range(m):
		tem = [int(v) for v in input().split()]
		roads.append(tem)
	c = []
	ma = 0
	for j in range(n):
		c.append(a[j] / b[j])
		ma = max(a[j] / b[j], ma)
	good = [0] * n
	for j in range(n):
		if c[j] == ma:
			good[j] = 1
			x = j + 1
	g = graph()
	fin = []
	final = g.goodnodes(roads, good, n)
	print(len(final))
	print(' '.join(map(str, final)))


t = int(input())
while t:
	t = t - 1
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	G = {}
	while m:
		m = m - 1
		(u, v) = map(int, input().split())
		u = u - 1
		v = v - 1
		if u in G:
			G[u].append(v)
		else:
			G[u] = [v]
		if v in G:
			G[v].append(u)
		else:
			G[v] = [u]
	PC = [A[i] / B[i] for i in range(n)]
	max_pc = max(PC)
	in_ans = []
	for x in PC:
		if x == max_pc:
			in_ans.append(1)
		else:
			in_ans.append(0)
	vis = [False for x in range(n)]
	which_part = [-1 for x in range(n)]
	part = 0
	for i in range(n):
		if vis[i] == False and in_ans[i] == 1:
			part = part + 1
			q = [i]
			which_part[i] = part
			vis[i] = True
			while len(q) > 0:
				top = q.pop(0)
				for x in G[top]:
					if vis[x] == False and in_ans[x] == 1:
						q.append(x)
						vis[x] = True
						which_part[x] = part
	nu = {}
	ans = []
	for i in range(n):
		x = which_part[i]
		if x != -1:
			if x in nu:
				nu[x].append(i + 1)
			else:
				nu[x] = [i + 1]
			if len(ans) < len(nu[x]):
				ans = nu[x]
	print(len(ans))
	for x in ans:
		print(x, end=' ')
	print()


from collections import deque

def bfs(graph, node, visited):
	q = deque()
	q.append(node)
	c = 0
	elements = []
	visited[node] = True
	while q != deque([]):
		a = q.popleft()
		c += 1
		elements.append(a)
		for i in graph[a]:
			if not visited[i]:
				q.append(i)
				visited[i] = True
	elements.append(c)
	return elements
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	brr = [int(i) for i in input().split()]
	graph = []
	for i in range(m):
		(a, b) = map(int, input().split())
		graph.append((a - 1, b - 1))
	income = []
	for i in range(n):
		income.append(arr[i] / brr[i])
	large = max(income)
	visited = {}
	for i in range(n):
		if income[i] == large:
			visited[i] = False
	new = []
	for i in range(m):
		a = graph[i]
		if a[0] in visited and a[1] in visited:
			new.append(a)
	graph = [[] for i in range(n)]
	for i in new:
		graph[i[0]].append(i[1])
		graph[i[1]].append(i[0])
	ans = []
	c = 0
	for i in visited:
		if not visited[i]:
			temp = bfs(graph, i, visited)
			if temp[-1] > c:
				ans = temp[:-1]
				c = temp[-1]
	print(c)
	for i in ans:
		print(i + 1, end=' ')
	print()


from collections import defaultdict

class DSU:

	def __init__(self, n):
		self.p = list(range(n))

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

	def union(self, x, y):
		self.p[self.find(x)] = self.find(y)
t = int(input())
while t:
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	dsu = DSU(n)
	ratio = [a[i] / b[i] for i in range(n)]
	maxx = max(ratio)
	choose = set()
	for i in range(n):
		if ratio[i] == maxx:
			choose.add(i)
	graph = defaultdict(list)
	for _ in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		if u in choose and v in choose:
			graph[u].append(v)
			graph[v].append(u)
			dsu.union(u, v)
	freq = [0] * n
	for x in choose:
		freq[dsu.find(x)] += 1
	leader = freq.index(max(freq))
	ans = []
	for x in choose:
		if dsu.find(x) == leader:
			ans.append(x + 1)
	print(len(ans))
	print(*ans)
	t -= 1


from sys import stdin, stdout
import sys
sys.setrecursionlimit(10 ** 6)
import math, queue, heapq
fastinput = stdin.readline
fastout = stdout.write
t = int(fastinput())

class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V)]

	def DFSUtil(self, temp, v, visited):
		visited[v] = True
		temp.append(v)
		for i in self.adj[v]:
			if visited[i] == False:
				temp = self.DFSUtil(temp, i, visited)
		return temp

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.adj[w].append(v)

	def connectedComponents(self):
		visited = [False] * self.V
		cc = []
		last = []
		for v in range(self.V):
			if visited[v] == False:
				temp = []
				last = self.DFSUtil(temp, v, visited)
				if len(last) > len(cc):
					cc = last
		return cc
while t:
	t -= 1
	(n, m) = map(int, fastinput().split())
	a = [0] + list(map(int, fastinput().split()))
	j = 1
	for i in fastinput().split():
		a[j] /= int(i)
		j += 1
	mal = 0
	for i in range(1, n + 1):
		mal = max(mal, a[i])
	g = Graph(n + 1)
	for _ in range(m):
		(x, y) = map(int, fastinput().split())
		if mal == a[x] and mal == a[y]:
			g.addEdge(x, y)
	cc = g.connectedComponents()
	print(len(cc))
	print(*cc)


from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

def dfs(i):
	if not num1[i]:
		return
	num1[i] = 0
	p.append(i)
	for v in ll[i]:
		dfs(v)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(l, l1) = ([], [a[0] / b[0]])
	for i in range(m):
		l.append(list(map(int, input().split())))
	(x, f) = (a[0] / b[0], 0)
	l1 = [0, x]
	for i in range(1, n):
		l1.append(a[i] / b[i])
		if a[i] / b[i] > x:
			x = a[i] / b[i]
			f = i + 1
	(l3, num1) = ([], [0] * (n + 1))
	for i in l:
		if l1[i[0]] == x and l1[i[1]] == x:
			l3.append(i)
			(num1[i[0]], num1[i[1]]) = (1, 1)
	if l3:
		ll = [[] for i in range(n + 1)]
		for i in l3:
			ll[i[0]].append(i[1])
			ll[i[1]].append(i[0])
		(p, num) = ([], [])
		for i in range(n + 1):
			if num1[i]:
				dfs(i)
				if len(p) > len(num):
					num = p
				p = []
		print(len(num))
		print(*num)
	else:
		print(1)
		print(f)


from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

def dfs(i):
	if not num1[i]:
		return
	num1[i] = 0
	p.append(i + 1)
	for v in l[i]:
		dfs(v)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = [[] for i in range(n)]
	for i in range(m):
		(x, y) = map(int, input().split())
		l[x - 1].append(y - 1)
		l[y - 1].append(x - 1)
	l1 = []
	for i in range(n):
		l1.append(a[i] // b[i])
	num1 = [0] * n
	m = max(l1)
	for i in range(n):
		if l1[i] == m:
			num1[i] = 1
	(p, num) = ([], [])
	for i in range(n):
		if num1[i]:
			dfs(i)
			if len(p) > len(num):
				num = p
			p = []
	print(len(num))
	print(*num)


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(id, ph, ss):
	vis[id] = 1
	ss.add(id)
	for i in range(len(ph[id])):
		if vis[ph[id][i]] != 1:
			dfs(ph[id][i], ph, ss)
for _ in range(int(input())):
	(n, c) = map(int, input().split())
	arr = list(map(int, input().split()))
	ppl = list(map(int, input().split()))
	di = []
	for i in range(n):
		di.append(arr[i] // ppl[i])
	mx = max(di)
	ans = set()
	for i in range(n):
		if di[i] == mx:
			ans.add(i + 1)
	path = [[] for i in range(n + 1)]
	for i in range(c):
		(u, v) = map(int, input().split())
		if u in ans and v in ans:
			path[u].append(v)
			path[v].append(u)
	vis = [0] * (n + 1)
	x = 0
	fs = set()
	for i in ans:
		ss = set()
		if vis[i] != 1:
			dfs(i, path, ss)
		if x < len(ss):
			x = len(ss)
			fs = ss
	print(x)
	print(*fs)


def find(st, u):
	st[u] = u if st[u] == u else find(st, st[u])
	return st[u]
T = int(input().rstrip())
for tt in range(T):
	(N, M) = list(map(int, input().rstrip().split(' ')))
	A = list(map(int, input().rstrip().split(' ')))
	B = list(map(int, input().rstrip().split(' ')))
	prov = list(zip(A, B))
	mx = max(prov, key=lambda x: x[0] / x[1])
	st = [i for i in range(N)]
	sz = [1] * N
	for i in range(M):
		(u, v) = list(map(int, input().rstrip().split(' ')))
		u -= 1
		v -= 1
		if A[u] * mx[1] == B[u] * mx[0] and A[v] * mx[1] == B[v] * mx[0]:
			if find(st, u) != find(st, v):
				sz[find(st, u)] += sz[find(st, v)]
				st[find(st, v)] = find(st, u)
	root = max(range(N), key=lambda x: sz[x])
	print(sz[root])
	print(' '.join(map(lambda x: str(x + 1), filter(lambda x: find(st, x) == root, range(N)))))


from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

def dfs(u):
	if v[u]:
		return
	v[u] = True
	p.append(u + 1)
	for x in graph[u]:
		dfs(x)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	cap = list(map(int, input().split()))
	pop = list(map(int, input().split()))
	ratio = [cap[i] // pop[i] for i in range(n)]
	graph = [[] for _ in range(n)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		graph[u - 1].append(v - 1)
		graph[v - 1].append(u - 1)
	maxratio = max(ratio)
	v = [True for i in range(n)]
	for i in range(n):
		if ratio[i] == maxratio:
			v[i] = False
	ans = []
	p = []
	for u in range(n):
		if not v[u]:
			dfs(u)
			if len(p) > len(ans):
				ans = p
			p = []
	print(len(ans))
	print(*ans)


from collections import defaultdict

def dfs(node):
	vis[node] = 0
	path.append(node)
	pq = [node]
	while len(pq) != 0:
		cur = pq.pop()
		for i in d[cur]:
			if vis[i]:
				pq.append(i)
				path.append(i)
				vis[i] = 0
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	inc = list(map(int, input().split()))
	pop = list(map(int, input().split()))
	ma = -1
	d = defaultdict(list)
	for i in range(n):
		ma = max(ma, inc[i] // pop[i])
	vis = [0] * (n + 1)
	for i in range(m):
		(u, v) = map(int, input().split())
		d[u].append(v)
		d[v].append(u)
	for i in range(1, n + 1):
		if inc[i - 1] // pop[i - 1] == ma:
			vis[i] = 1
	ma = -1
	for i in range(1, n + 1):
		if vis[i]:
			path = []
			dfs(i)
			if len(path) > ma:
				ma = len(path)
				p = path
	print(ma)
	print(*p)


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)

def dfs(node):
	vis[node] = 0
	path.append(node)
	for i in d[node]:
		if vis[i]:
			dfs(i)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	inc = list(map(int, input().split()))
	pop = list(map(int, input().split()))
	ma = -1
	d = defaultdict(list)
	for i in range(n):
		ma = max(ma, inc[i] // pop[i])
	vis = [0] * (n + 1)
	for i in range(m):
		(u, v) = map(int, input().split())
		d[u].append(v)
		d[v].append(u)
	for i in range(1, n + 1):
		if inc[i - 1] // pop[i - 1] == ma:
			vis[i] = 1
	ma = -1
	p = []
	for i in range(1, n + 1):
		if vis[i]:
			path = []
			dfs(i)
			if len(path) > ma:
				ma = len(path)
				p = path
	print(ma)
	print(*p)


def solve():
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	max = 0
	for i in range(n):
		if a[i] / b[i] > max:
			max = a[i] / b[i]
	graph = {}
	visited = [False for _ in range(n)]
	for _ in range(m):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		if a[x] / b[x] == max:
			if x not in graph:
				graph[x] = []
			if a[y] / b[y] == max:
				graph[x].append(y)
		if a[y] / b[y] == max:
			if y not in graph:
				graph[y] = []
			if a[x] / b[x] == max:
				graph[y].append(x)
	sol = []
	for i in graph:
		if visited[i] == False:
			curSol = []
			stack = [i]
			visited[i] = True
			while len(stack):
				node = stack.pop()
				curSol.append(node + 1)
				for j in graph[node]:
					if not visited[j]:
						visited[j] = True
						stack.append(j)
			if len(curSol) > len(sol):
				sol = curSol[:]
	print(len(sol))
	print(*sol, sep=' ', end='\n')
T = int(input())
for _ in range(T):
	solve()


import sys
import math
import collections
from sys import stdin, stdout, setrecursionlimit
import bisect as bs
setrecursionlimit(2 ** 20)
M = 10 ** 9 + 7

def solve():
	(n, m) = list(map(int, stdin.readline().split()))
	income = list(map(int, stdin.readline().split()))
	population = list(map(int, stdin.readline().split()))
	percapita = [0] * n
	adj = []
	for i in range(n):
		adj.append([])
	for i in range(m):
		(x, y) = list(map(int, stdin.readline().split()))
		adj[x - 1].append(y - 1)
		adj[y - 1].append(x - 1)
	max_percapita = -1
	d = {}
	for i in range(n):
		percapita[i] = income[i] // population[i]
		max_percapita = max(max_percapita, percapita[i])
		if percapita[i] not in d:
			d[percapita[i]] = []
		d[percapita[i]].append(i)
	vis = [0] * n
	mark = [-1] * n
	ans = 0
	final_mark = -1
	for i in d[max_percapita]:
		if vis[i] == 0:
			stack = [i]
			vis[i] = 1
			cnt = 1
			while len(stack) != 0:
				s = stack.pop()
				mark[s] = i
				for j in adj[s]:
					if vis[j] == 0 and percapita[j] == max_percapita:
						vis[j] = 1
						cnt += 1
						stack.append(j)
			if cnt >= ans:
				ans = cnt
				final_mark = i
	ans1 = []
	for i in range(n):
		if mark[i] == final_mark:
			ans1.append(i + 1)
	print(ans)
	print(*ans1)
t = 1
t = int(stdin.readline())
for _ in range(t):
	solve()


import sys
sys.setrecursionlimit(1000000)

def DFS(v, visited, k, conn):
	visited[v] = 1
	k.append(v + 1)
	for i in conn[v]:
		if visited[i] == 0:
			DFS(i, visited, k, conn)

def solve(visited, conn):
	q = {}
	k = []
	for i in d:
		if visited[i] == 0:
			DFS(i, visited, k, conn)
			q[len(k)] = k
			k = []
	return q
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = []
	r = 0
	for i in range(n):
		q = a[i] / b[i]
		l.append(q)
		r = max(r, q)
	d = {}
	for i in range(n):
		if l[i] == r:
			d[i] = 1
	conn = [[] for i in range(n)]
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		if u in d:
			if v in d:
				conn[u].append(v)
				conn[v].append(u)
	visited = [0 for i in range(n)]
	kk = solve(visited, conn)
	s = 0
	j = max(kk)
	print(j)
	print(*kk[j])


for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	l1 = input().split()
	l2 = input().split()
	ma = -1
	coll = []
	num = [0 for i in range(n + 1)]
	tra = [[] for i in range(n + 1)]
	for i in range(n):
		x = int(l1[i]) / int(l2[i])
		if x > ma:
			coll = []
			ma = x
			coll.append(i + 1)
		elif x == ma:
			coll.append(i + 1)
	for i in coll:
		num[i] = 1
	for i in range(m):
		(x, y) = [int(kk) for kk in input().split()]
		if num[x] == 1 and num[y] == 1:
			tra[x].append(y)
			tra[y].append(x)
	numd = [0 for i in range(n + 1)]
	dub1 = []
	for i in coll:
		if numd[i] == 0:
			l = 0
			dub2 = [i]
			numd[i] = 1
			while l < len(dub2):
				for k in tra[dub2[l]]:
					if numd[k] == 0:
						dub2.append(k)
						numd[k] = 1
				l += 1
			if len(dub2) > len(dub1):
				dub1 = dub2[:]
	print(len(dub1))
	print(*dub1)


import sys
sys.setrecursionlimit(1000000)
d = {}

def dfs(r, vis, l):
	for i in range(0, len(d[r])):
		if vis[d[r][i]] != 1:
			l.append(d[r][i])
			vis[d[r][i]] = 1
			dfs(d[r][i], vis, l)
t = int(input())
while t:
	(n, p) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = []
	max = -1.0
	for i in range(n):
		d[i] = []
		m = a[i] / b[i]
		if max < m:
			max = m
		c.append(a[i] / b[i])
	m = []
	f = [0] * n
	for i in range(n):
		if max == c[i]:
			f[i] = 1
			m.append(i)
	for i in range(p):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		if f[u] == 1 and f[v] == 1:
			d[u].append(v)
			d[v].append(u)
	visited = [0] * n
	l = []
	b = []
	mx = -1
	pos = -1
	for i in range(len(m)):
		if visited[m[i]] == 0:
			l.append(m[i])
			visited[m[i]] = 1
			x = dfs(m[i], visited, l)
			if len(l) > mx:
				mx = len(l)
				pos = m[i]
			l = []
	v = [0] * n
	b.append(pos)
	v[pos] = 1
	x = dfs(pos, v, b)
	print(len(b))
	for i in range(len(b)):
		print(b[i] + 1, end=' ')
	print()
	t -= 1


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(u, path, possible):
	vis[u] = 1
	possible.add(u)
	for i in range(0, len(path[u])):
		if not vis[path[u][i]]:
			dfs(path[u][i], path, possible)
t = int(input())
for _ in range(0, t):
	(n, m) = map(int, input().split())
	aa = [int(i) for i in input().split()]
	bb = [int(i) for i in input().split()]
	mx = -1
	for i in range(0, n):
		mx = max(mx, aa[i] / bb[i])
	s = set()
	for i in range(0, n):
		if mx == aa[i] / bb[i]:
			s.add(i + 1)
	path = [[] for i in range(0, n + 1)]
	for _ in range(0, m):
		(u, v) = map(int, input().split())
		if u in s and v in s:
			path[u].append(v)
			path[v].append(u)
	vis = [0] * (n + 1)
	ans = []
	for i in s:
		possible = set()
		if not vis[i]:
			dfs(i, path, possible)
		if len(possible) > len(ans):
			ans = list(possible)
	print(len(ans))
	print(*sorted(ans))


from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

def dfs(graph, visited, p, i):
	if visited[i] == True:
		return
	visited[i] = True
	p.append(i + 1)
	for v in graph[i]:
		dfs(graph, visited, p, v)
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	per = []
	ma = 0
	for i in range(n):
		per.append(a[i] / b[i])
		ma = max(ma, a[i] / b[i])
	visited = [False] * n
	for i in range(n):
		if per[i] != ma:
			visited[i] = True
	g = [[] for i in range(n)]
	for i in range(m):
		(u, v) = list(map(int, input().split()))
		u -= 1
		v -= 1
		g[u].append(v)
		g[v].append(u)
	ans = []
	p = []
	for i in range(n):
		if visited[i] != True:
			dfs(g, visited, p, i)
			if len(p) > len(ans):
				ans = p
			p = []
	print(len(ans))
	print(*ans)


import sys
import math
import collections
from sys import stdin, stdout, setrecursionlimit
import bisect as bs
setrecursionlimit(2 ** 20)
M = 10 ** 9 + 7
T = int(stdin.readline())
for _ in range(T):
	(n, M) = list(map(int, stdin.readline().split()))
	a = list(map(int, stdin.readline().split()))
	b = list(map(int, stdin.readline().split()))
	g = []
	exp = [False] * (n + 1)
	for i in range(n + 1):
		g.append([])
	arr = []
	for i in range(n):
		arr.append(a[i] / b[i])
	mx = max(arr)
	d = {}
	for i in range(n):
		if arr[i] == mx:
			d[i + 1] = True
	for i in range(M):
		(x, y) = list(map(int, stdin.readline().split()))
		g[x].append(y)
		g[y].append(x)
	ml = 0
	fin = []
	for k in d:
		if exp[k]:
			continue
		a = [k]
		exp[k] = True
		tmp = [k]
		while a:
			u = a.pop()
			for v in g[u]:
				if v not in d:
					continue
				if not exp[v]:
					tmp.append(v)
					exp[v] = True
					a.append(v)
		if len(tmp) > ml:
			fin = tmp.copy()
			ml = len(tmp)
	print(len(fin))
	for h in fin:
		print(h, end=' ')
	print('')


import sys
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict as dft

def dfs(nd, s):
	s.append(nd)
	vis[nd] = 1
	for lnk in dct[nd]:
		if choose[lnk] and vis[lnk] == 0:
			dfs(lnk, s)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	mx = 0
	choose = [0] * (n + 1)
	num = a[0]
	deno = b[0]
	for i in range(n):
		if a[i] * deno > b[i] * num:
			(num, deno) = (a[i], b[i])
	for i in range(1, n + 1):
		if a[i - 1] * deno == b[i - 1] * num:
			choose[i] = 1
	dct = dft(list)
	for i in range(m):
		(u, v) = map(int, input().split())
		dct[u].append(v)
		dct[v].append(u)
	vis = [0] * (n + 1)
	res = []
	for x in range(1, n + 1):
		if choose[x] and (not vis[x]):
			s = []
			dfs(x, s)
			if len(s) > len(res):
				res = s[:]
	print(len(res))
	print(*res)


import math as mt
import sys, string
input = sys.stdin.readline
print = sys.stdout.write
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())
from collections import defaultdict
d = [0] * (2 * 10 ** 5)
vis = [0] * (2 * 10 ** 5)
t = I()
for _ in range(t):
	(n, m) = M()
	l = L()
	x = L()
	adj = []
	for i in range(n):
		adj.append([])
	mi = 0
	for i in range(n):
		g = mt.gcd(l[i], x[i])
		l[i] //= g
		x[i] //= g
		mi = max(mi, l[i] / x[i])
	v = []
	for i in range(n):
		if l[i] / x[i] == mi:
			d[i] = 1
			v.append(i)
	for i in range(m):
		(a, b) = M()
		if d[b - 1] == 1 and d[a - 1] == 1:
			adj[b - 1].append(a - 1)
			adj[a - 1].append(b - 1)
	ans = 0
	req = []
	for i in v:
		if vis[i] == 0:
			c = 1
			result = []
			x = [i]
			result.append(i + 1)
			while len(x) != 0:
				y = x.pop(0)
				vis[y] = 1
				for j in adj[y]:
					if vis[j] == 0:
						c += 1
						vis[j] = 1
						x.append(j)
						result.append(j + 1)
		if c > ans:
			ans = c
			req = result[:]
	for i in v:
		d[i] = 0
		vis[i] = 0
	print(str(len(req)) + '\n')
	for i in req:
		print(str(i) + ' ')
	print('\n')


import sys, io, os, time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect, math, heapq
alphabet = 'abcdefghijklmnopqrstuvwxyz'
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def dfs(node, g, path, nvisited):
	path.append(node)
	nvisited[node] = False
	for nei in g[node]:
		if nvisited[nei]:
			dfs(nei, g, path, nvisited)
for ii in range(int(input())):
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	g = defaultdict(list)
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		g[u].append(v)
		g[v].append(u)
	nvisited = [False] * (n + 1)
	maxCapita = -1
	for i in range(n):
		maxCapita = max(maxCapita, A[i] / B[i])
	for i in range(n):
		if A[i] / B[i] == maxCapita:
			nvisited[i] = True
	res = []
	for i in range(n):
		if nvisited[i]:
			path = []
			dfs(i, g, path, nvisited)
			if len(path) > len(res):
				res = path
	print(len(res))
	for i in res:
		print(i + 1, end=' ')
	print()


from collections import defaultdict, deque
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	money = list(map(int, input().split()))
	population = list(map(int, input().split()))
	avg = []
	check = [False]
	for i in range(n):
		avg.append((money[i] / population[i], i + 1))
		check.append(False)
	avg.sort(reverse=True)
	maxi = avg[0][0]
	start = avg[0][1]
	starts = []
	for i in range(n):
		if avg[i][0] == maxi:
			check[avg[i][1]] = True
			starts.append(avg[i][1])
			start = avg[i][1]
	if start == avg[0][1]:
		print(1)
		print(*starts)
	else:
		arr = [[] for i in range(n + 1)]
		for i in range(m):
			(x, y) = map(int, input().split())
			arr[x].append(y)
			arr[y].append(x)
		dic = defaultdict(list)
		vis = [False] * (n + 1)
		mx_len = 0
		for i in starts:
			if vis[i] == False:
				q = deque()
				q.append(i)
				while q:
					p = q.popleft()
					vis[p] = True
					for j in arr[p]:
						if check[j] and vis[j] == False:
							vis[j] = True
							q.append(j)
							dic[i].append(j)
							mx_len = max(mx_len, len(dic[i]))
		for i in dic:
			if len(dic[i]) == mx_len:
				print(mx_len + 1)
				print(i, *dic[i])
				break


import sys
import random

class DSU:

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

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

	def getSize(self, x):
		return self.size[self.FIND(x)]

	def UNION(self, x, y):
		xRoot = self.FIND(x)
		yRoot = self.FIND(y)
		if xRoot != yRoot:
			self.comps -= 1
			if random.randint(1, 100) & 1:
				self.parent[xRoot] = yRoot
				self.size[yRoot] += self.size[xRoot]
			else:
				self.parent[yRoot] = xRoot
				self.size[xRoot] += self.size[yRoot]
			return 1
		return 0
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	income = [int(x) for x in input().split()]
	population = [int(x) for x in input().split()]
	edges = []
	for x in range(m):
		(u, v) = map(int, input().split())
		edges.append([u, v])
	best = [0]
	for x in range(1, n):
		j = best[0]
		if income[j] * population[x] < income[x] * population[j]:
			best = [x]
		elif income[j] * population[x] == income[x] * population[j]:
			best.append(x)
	consider = [None for x in range(n)]
	for item in best:
		consider[item] = 1
	dsu = DSU(n)
	for (u, v) in edges:
		u -= 1
		v -= 1
		if consider[u] and consider[v]:
			dsu.UNION(u, v)
	parents = {}
	for item in best:
		p = dsu.FIND(item)
		if p in parents:
			parents[p].append(str(item + 1))
		else:
			parents[p] = [str(item + 1)]
	p = max(parents, key=lambda k: len(parents[k]))
	print(len(parents[p]))
	print(' '.join(parents[p]))


from collections import defaultdict
t = int(input())
while t:
	(n, m) = map(int, input().split())
	incomes = list(map(int, input().split()))
	pop = list(map(int, input().split()))
	graph = defaultdict(list)
	seen = set()
	choose = set()
	(num, den) = (incomes[0], pop[0])
	res = []
	for i in range(1, n):
		if incomes[i] // pop[i] > num // den:
			num = incomes[i]
			den = pop[i]
	for i in range(n):
		if incomes[i] // pop[i] == num // den:
			choose.add(i)
	for _ in range(m):
		(u, v) = map(int, input().split())
		if u - 1 in choose and v - 1 in choose:
			graph[u - 1].append(v - 1)
			graph[v - 1].append(u - 1)
	for i in range(n):
		if i in choose and i not in seen:
			provinces = [i + 1]
			stack = [i]
			seen.add(i)
			while stack:
				node = stack.pop()
				for nei in graph[node]:
					if nei not in seen:
						seen.add(nei)
						provinces.append(nei + 1)
						stack.append(nei)
			if len(provinces) > len(res):
				res = provinces
	print(len(res))
	print(*res)
	t -= 1


import sys
sys.setrecursionlimit(1000000000)
import math
from sys import stdin, stdout
from collections import deque, defaultdict
from math import ceil, floor, inf, sqrt, factorial, gcd, log2
from copy import deepcopy
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
mod = 1000000007

def dfs(u):
	if vis[u]:
		return
	vis[u] = True
	local_sol.append(u + 1)
	for v in graph[u]:
		dfs(v)

def takeinput(n, q):
	graph = [[] for i in range(n)]
	for i in range(q):
		(u, v) = iia()
		graph[v - 1].append(u - 1)
		graph[u - 1].append(v - 1)
	return graph
t = ii1()
for _ in range(t):
	(n, q) = iia()
	A = iia()
	B = iia()
	C = [A[i] // B[i] for i in range(n)]
	graph = takeinput(n, q)
	maxi = max(C)
	vis = [False] * n
	for i in range(n):
		if C[i] != maxi:
			vis[i] = True
	local_sol = []
	global_sol = []
	for u in range(n):
		if vis[u] == False:
			dfs(u)
			if len(local_sol) > len(global_sol):
				global_sol = local_sol
			local_sol = []
	print(len(global_sol))
	print(*global_sol)