Determine the minimum cost to provide library access to all citizens of HackerLand.  There are $n$ cities numbered from $1$ to $n$. Currently there are no libraries and the cities are not connected.  Bidirectional roads may be built between any city pair listed in $cities$. A citizen has access to a library if:

Their city contains a library.
They can travel by road from their city to a city containing a library.

Example  

The following figure is a sample map of HackerLand where the dotted lines denote possible roads:

$c\_{road}=2$ 

$c\_{lib}=3$ 

$cities=[[1,7],[1,3],[1,2],[2,3],[5,6],[6,8]]$  

The cost of building any road is $c c\_{road}=2$, and the cost to build a library in any city is $c\_lib = 3$.  Build $5$ roads at a cost of $5\times2=10$ and $2$ libraries for a cost of $6$.  One of the available roads in the cycle $1\to2\to3\to1$ is not necessary.   

There are $q$ queries, where each query consists of a map of HackerLand and value of $c\_lib$ and $c\_road$. For each query, find the minimum cost to make libraries accessible to all the citizens.

Function Description

Complete the function roadsAndLibraries in the editor below. 

roadsAndLibraries has the following parameters:

int n: integer, the number of cities  
int c_lib: integer, the cost to build a library  
int c_road: integer, the cost to repair a road  
int cities[m][2]: each $cities[i]$ contains two integers that represent cities that can be connected by a new road  

Returns 

- int:  the minimal cost

Input Format

The first line contains a single integer $q$, that denotes the number of queries. 

The subsequent lines describe each query in the following format: 

- The first line contains four space-separated integers that describe the respective values of $n$, $m$, $c\_lib$ and $c\_road$, the number of cities, number of roads, cost of a library and cost of a road. 

- Each of the next $m$ lines contains two space-separated integers, $u[i]$ and $v[i]$, that describe a bidirectional road that can be built to connect cities $u[i]$ and $v[i]$.

Constraints

$1\leq q\leq10$
$1\leq n\leq10^5$ 
$0\leq m\leq min(10^5,\frac{n\cdot(n-1)}{2})$
$1\leq c\_road,c\_lib\leq10^5$
$1\leq u[i],v[i]\leq n$
Each road connects two distinct cities.

Sample Input
STDIN       Function
-----       --------
2           q = 2
3 3 2 1     n = 3, cities[] size m = 3, c_lib = 2, c_road = 1
1 2         cities = [[1, 2], [3, 1], [2, 3]]
3 1
2 3
6 6 2 5     n = 6, cities[] size m = 6, c_lib = 2, c_road = 5
1 3         cities = [[1, 3], [3, 4],...]
3 4
2 4
1 2
2 3
5 6

Sample Output
4
12

Explanation

Perform the following $q=2$ queries:

HackerLand contains $n=3$ cities and can be connected by $m=3$ bidirectional roads. The price of building a library is $c_{lib}=2$ and the price for repairing a road is $c_{road}=1$. 

The cheapest way to make libraries accessible to all is to:

Build a library in city $1$ at a cost of $x=2$.
Build the road between cities $1$ and $2$ at a cost of $y=1$.
Build the road between cities $2$ and $3$ at a cost of $y=1$.

This gives a total cost of $2+1+1=4$. Note that the road between cities $3$ and $1$ does not need to be built because each is connected to city $2$.  

In this scenario it is optimal to build a library in each city because the cost to build a library is less than the cost to build a road. 

There are $6$ cities, so the total cost is $6\times2=12$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Graph algorithms


Solutions:
from collections import defaultdict
from collections import deque
from math import pi, cos, sin

class graph:

	def __init__(self):
		self.nodes = []
		self.edges = defaultdict(set)

	def clone(self):
		g = graph()
		g.nodes = self.nodes[:]
		for n in self.nodes:
			for e in self.edges[n]:
				g.edges[n].add(e)
		return g

def count_clusters(g):
	nclust = 0
	used = set()
	n = len(g.nodes)
	csize = []
	for node in g.nodes:
		if node in used:
			continue
		used.add(node)
		size = 1
		Q = deque()
		Q.appendleft(node)
		while Q:
			cur = Q.pop()
			for neigh in g.edges[cur]:
				if neigh in used:
					continue
				used.add(neigh)
				Q.appendleft(neigh)
				size += 1
		nclust += 1
		csize.append(size)
	return (nclust, csize)
q = int(input())
for _ in range(q):
	(n, m, clib, croad) = [int(x) for x in input().split()]
	edges = [[int(x) for x in input().split()] for _ in range(m)]
	if clib < croad:
		print(clib * n)
		continue
	g = graph()
	g.nodes = range(1, n + 1)
	for (a, b) in edges:
		g.edges[a].add(b)
		g.edges[b].add(a)
	(nc, cs) = count_clusters(g)
	print(nc * clib + sum(((x - 1) * croad for x in cs)))


from collections import defaultdict, deque
for _ in range(int(input())):
	(n, m, x, y) = map(int, input().split())
	if x <= y:
		print(n * x)
		for _ in range(m):
			input()
	else:
		nbhd = defaultdict(list)
		for _ in range(m):
			(c1, c2) = map(int, input().split())
			nbhd[c1].append(c2)
			nbhd[c2].append(c1)
		new_node = [True] * (n + 1)
		count = 0
		cache = deque()
		for cur in range(1, n + 1):
			if new_node[cur]:
				count += x
				cache.append(cur)
				new_node[cur] = False
				while cache:
					for i in nbhd[cache.popleft()]:
						if new_node[i]:
							cache.append(i)
							new_node[i] = False
							count += y
		print(count)


import sys

def solve(g, plib, proad):

	def region_gen():
		reached = set()
		for node in g:
			if node in reached:
				continue
			reached.add(node)
			(region, candidates) = (set(), set([node]))
			while candidates:
				node = candidates.pop()
				region.add(node)
				for candidate in g[node]:
					if candidate not in region:
						candidates.add(candidate)
			reached |= region
			yield region

	def region_cost(r):
		if plib < proad:
			return len(r) * plib
		return plib + (len(r) - 1) * proad
	rval = 0
	for r in region_gen():
		rval += region_cost(r)
	return rval
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	graph = {}
	for i in range(1, n + 1):
		graph[i] = set()
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		graph[city_1].add(city_2)
		graph[city_2].add(city_1)
	print(solve(graph, x, y))


import sys

def getSets(graph):
	visited = set()
	setList = []

	def addToSet(node, s):
		if node in visited:
			return
		visited.add(node)
		s.add(node)
		for i in graph[node][0]:
			addToSet(i, s)
		for i in graph[node][1]:
			addToSet(i, s)
	for node in range(len(graph)):
		if node in visited:
			continue
		s = set()
		addToSet(node, s)
		setList += [s]
	return setList
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	graph = [[[], []] for i in range(n)]
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		graph[city_1 - 1][1] += [city_2 - 1]
		graph[city_2 - 1][0] += [city_1 - 1]
	groups = getSets(graph)
	cost = 0
	for group in groups:
		cost += min(len(group) * x, x + y * (len(group) - 1))
	print(cost)


import sys
q = int(input().strip())
for a0 in range(q):
	(n, m, clib, croad) = input().strip().split(' ')
	(n, m, clib, croad) = [int(n), int(m), int(clib), int(croad)]
	edges = []
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		edges.append([city_1, city_2])
	if croad >= clib:
		print(clib * n)
		continue
	labels = [0] * n
	lastlabel = 0
	groups = []
	for [c1, c2] in edges:
		(l1, l2) = (labels[c1 - 1], labels[c2 - 1])
		if l1 == 0 and l2 == 0:
			lastlabel += 1
			(labels[c1 - 1], labels[c2 - 1]) = (lastlabel, lastlabel)
		elif l1 == l2:
			pass
		elif l1 == 0 and l2 != 0:
			labels[c1 - 1] = labels[c2 - 1]
		elif l1 != 0 and l2 == 0:
			labels[c2 - 1] = labels[c1 - 1]
		elif l1 != l2:
			foundGroups = []
			for group in groups:
				if l1 in group or l2 in group:
					foundGroups.append(group)
			if len(foundGroups) == 0:
				groups.append({l1, l2})
			elif len(foundGroups) == 1:
				foundGroups[0].add(l1)
				foundGroups[0].add(l2)
			else:
				newGroup = set()
				for foundGroup in foundGroups:
					newGroup = newGroup.union(foundGroup)
					groups.remove(foundGroup)
				groups.append(newGroup)
	redundantlabels = sum([len(s) - 1 for s in groups])
	subgraphs = lastlabel - redundantlabels + len([x for x in labels if x == 0])
	print(subgraphs * clib + n * croad - subgraphs * croad)


import sys

def find_root(roots, city):
	i = roots[city]
	while i != roots[i]:
		i = roots[i]
	return roots[i]
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	root = [x for x in range(n + 1)]
	cost = 0
	if x <= y:
		print(n * x)
		for _ in range(m):
			x = input()
		continue
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		temp1 = find_root(root, city_1)
		temp2 = find_root(root, city_2)
		if temp1 != temp2:
			root[temp1] = temp2
			cost += y
	for i in range(1, n + 1):
		if i == root[i]:
			cost += x
	print(cost)


import sys
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	ntrees = 0
	adjlist = [[] for _ in range(n + 1)]
	visitlist = [False for _ in range(n + 1)]
	queue = set()
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		adjlist[city_1].append(city_2)
		adjlist[city_2].append(city_1)
	for i in range(1, n + 1):
		if not visitlist[i]:
			ntrees += 1
			queue.add(i)
			while len(queue) > 0:
				v = queue.pop()
				visitlist[v] = True
				for w in adjlist[v]:
					if not visitlist[w]:
						queue.add(w)
	if x < y:
		print(x * n)
	else:
		print(x * ntrees + y * (n - ntrees))


from collections import deque
queries = int(input().strip())
for q in range(queries):
	(n, m, clib, croad) = [int(i) for i in input().strip().split(' ')]
	cities = [[] for i in range(n)]
	for i in range(m):
		edge = list(map(int, input().strip().split(' ')))
		cities[edge[0] - 1].append(edge[1] - 1)
		cities[edge[1] - 1].append(edge[0] - 1)
	cost = 0
	if clib <= croad:
		cost = n * clib
	else:
		unvisited = [True for i in range(n)]
		for city in range(n):
			if unvisited[city]:
				unvisited[city] = False
				bfs_queue = deque()
				bfs_queue.append(city)
				cost += clib
				while len(bfs_queue) > 0:
					top_node = bfs_queue.popleft()
					for unvisited_neighbour in filter(lambda e: unvisited[e], cities[top_node]):
						unvisited[unvisited_neighbour] = False
						bfs_queue.append(unvisited_neighbour)
						cost += croad
	print(cost)


import sys

def dfsVisit(key, dictCity, color):
	color[key - 1] = 'B'
	for i in dictCity[key]:
		if color[i - 1] == 'white':
			dfsVisit(i, dictCity, color)

def DFS(n, dictCity):
	color = ['white' for i in range(n)]
	comp = 0
	for key in dictCity.keys():
		if color[int(key) - 1] == 'white':
			dfsVisit(int(key), dictCity, color)
			comp += 1
	return comp
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	dictCity = dict([(i, []) for i in range(1, n + 1)])
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		dictCity[city_1].append(city_2)
		dictCity[city_2].append(city_1)
	if x <= y:
		print(n * x)
	elif m >= n - 1:
		print(x + (n - 1) * y)
	else:
		cmpt = DFS(n, dictCity)
		print(x * cmpt + (n - cmpt) * y)


class Data(object):

	def __init__(self, name):
		self.__name = name
		self.__links = set()

	@property
	def name(self):
		return self.__name

	@property
	def links(self):
		return set(self.__links)

	def add_link(self, other):
		self.__links.add(other)
		other.__links.add(self)

def connected_components(nodes):
	result = []
	nodes = set(nodes)
	while nodes:
		n = nodes.pop()
		group = {n}
		queue = [n]
		while queue:
			n = queue.pop(0)
			neighbors = n.links
			neighbors.difference_update(group)
			nodes.difference_update(neighbors)
			group.update(neighbors)
			queue.extend(neighbors)
		result.append(group)
	return result
q = int(input())
for qq in range(q):
	[n, m, cli, cro] = [int(x) for x in input().strip().split(' ')]
	da = [Data(str(x)) for x in range(n)]
	for mm in range(m):
		[u, v] = [int(x) - 1 for x in input().strip().split(' ')]
		da[u].add_link(da[v])
	if cli <= cro:
		print(cli * n)
	else:
		tc = 0
		number = 1
		for components in connected_components(set(da)):
			tc += cli + cro * (len(components) - 1)
		print(tc)


import sys
from collections import defaultdict

def connected_component(graph, starting_vertex):
	stack = [starting_vertex]
	visited = set()
	while len(stack) > 0:
		vertex = stack.pop()
		if vertex not in visited:
			yield vertex
			visited.add(vertex)
			stack += list(graph[vertex])

def num_connected_components(graph, vertices):
	visited = set()
	res = 0
	for v in vertices:
		if v not in visited:
			res += 1
			visited |= set(connected_component(graph, v))
	return res

def get_data():
	graph = defaultdict(set)
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	for _ in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		graph[city_1].add(city_2)
		graph[city_2].add(city_1)
	return (graph, n, x, y)
for _ in range(int(input())):
	(graph, n_cities, cost_library, cost_road) = get_data()
	if cost_library < cost_road:
		res = cost_library * n_cities
	else:
		n_cc = num_connected_components(graph, range(1, n_cities + 1))
		res = cost_library * n_cc + cost_road * (n_cities - n_cc)
	print(res)


import sys

class V(object):

	def __init__(self, u, *args):
		self.u = u
		self.v = list(args)

def dfs(u, g, c_lib, c_road, used):
	used[u] = True
	cnt = 1
	for v in g[u].v:
		if not used[v]:
			cnt += dfs(v, g, c_lib, c_road, used)
	return cnt

def optimize(g, n, m, c_lib, c_road, cost):
	used = [False] * (n + 1)
	for i in range(1, n + 1):
		if not used[i]:
			verts = dfs(i, g, c_lib, c_road, used)
			road_cost = c_road * (verts - 1)
			lib_cost = c_lib * verts
			if road_cost + c_lib < lib_cost:
				cost = cost + (road_cost + c_lib) - lib_cost
	return cost
q = int(input().strip())
rv = []
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, c_lib, c_road) = [int(n), int(m), int(x), int(y)]
	g = {i: V(i) for i in range(1, n + 1)}
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		g[city_1].v.append(city_2)
		g[city_2].v.append(city_1)
	cost = c_lib * n
	rv.append(optimize(g, n, m, c_lib, c_road, cost))
print('\n'.join(map(str, rv)))


from collections import defaultdict
for _ in range(int(input())):
	(n, m, cl, cr) = map(int, input().split())
	res = 0
	g = defaultdict(list)
	for _ in range(m):
		(x, y) = map(int, input().split())
		(x, y) = (x - 1, y - 1)
		g[x].append(y)
		g[y].append(x)
	vis = [False for _ in range(n)]
	for i in range(n):
		if vis[i]:
			continue
		vis[i] = True
		nodes = 0
		stack = [i]
		while stack:
			curr = stack.pop()
			nodes += 1
			for ne in g[curr]:
				if not vis[ne]:
					stack.append(ne)
					vis[ne] = True
		res += nodes * cl if cl < cr else cl + (nodes - 1) * cr
	print(res)


import sys
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	edges = [[] for i in range(n + 1)]
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		edges[city_1].append(city_2)
		edges[city_2].append(city_1)
	if x <= y:
		print(n * x)
		continue
	total = 0
	visited = [False for i in range(n + 1)]
	for i in range(1, n + 1):
		if not visited[i]:
			stack = []
			stack.append(i)
			num_visited = 1
			visited[i] = True
			while len(stack) > 0:
				city = stack.pop()
				for e in edges[city]:
					if not visited[e]:
						visited[e] = True
						num_visited += 1
						stack.append(e)
			total += x + (num_visited - 1) * y
	print(total)


import sys

class UnionFind:

	def __init__(self):
		self.num_weights = {}
		self.parent_pointers = {}
		self.num_to_objects = {}
		self.objects_to_num = {}
		self.__repr__ = self.__str__

	def insert_objects(self, objects):
		for object in objects:
			self.find(object)

	def find(self, object):
		if not object in self.objects_to_num:
			obj_num = len(self.objects_to_num)
			self.num_weights[obj_num] = 1
			self.objects_to_num[object] = obj_num
			self.num_to_objects[obj_num] = object
			self.parent_pointers[obj_num] = obj_num
			return object
		stk = [self.objects_to_num[object]]
		par = self.parent_pointers[stk[-1]]
		while par != stk[-1]:
			stk.append(par)
			par = self.parent_pointers[par]
		for i in stk:
			self.parent_pointers[i] = par
		return self.num_to_objects[par]

	def union(self, object1, object2):
		o1p = self.find(object1)
		o2p = self.find(object2)
		if o1p != o2p:
			on1 = self.objects_to_num[o1p]
			on2 = self.objects_to_num[o2p]
			w1 = self.num_weights[on1]
			w2 = self.num_weights[on2]
			if w1 < w2:
				(o1p, o2p, on1, on2, w1, w2) = (o2p, o1p, on2, on1, w2, w1)
			self.num_weights[on1] = w1 + w2
			del self.num_weights[on2]
			self.parent_pointers[on2] = on1

	def __str__(self):
		sets = {}
		for i in range(len(self.objects_to_num)):
			sets[i] = []
		for i in self.objects_to_num:
			sets[self.objects_to_num[self.find(i)]].append(i)
		out = []
		for i in sets.values():
			if i:
				out.append(repr(i))
		return ', '.join(out)
q = int(input().strip())
for a0 in range(q):
	(n, m, cl, cr) = input().strip().split(' ')
	(n, m, cl, cr) = [int(n), int(m), int(cl), int(cr)]
	vert = [i for i in range(1, n + 1)]
	edges = []
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		edges.append([city_1, city_2])
	uf = UnionFind()
	uf.insert_objects(vert)
	for e in edges:
		uf.union(e[0], e[1])
	s = eval(str(uf))
	if type(s[0]) == int:
		p = len(s)
		print(min((p - 1) * cr + cl, p * cl))
	else:
		(ucl, ucr) = (0, 0)
		for u in s:
			p = len(u)
			ucr += (p - 1) * cr + cl
			ucl += p * cl
		print(min(ucr, ucl))


import sys

class DisjointSet(object):

	def __init__(self, size):
		self.__size = size
		self.__root = [i for i in range(size)]
		self.__rank = [1] * size

	def root(self, a):
		while self.__root[a] != a:
			b = self.__root[self.__root[a]]
			self.__root[a] = b
			a = b
		return a

	def merge(self, a, b):
		root_a = self.root(a)
		root_b = self.root(b)
		if root_a == root_b:
			return
		if self.__rank[root_a] < self.__rank[root_b]:
			self.__root[root_a] = root_b
			self.__rank[root_b] += self.__rank[root_a]
		else:
			self.__root[root_b] = root_a
			self.__rank[root_a] += self.__rank[root_b]

	def count(self):
		roads_no = 0
		libraries_no = 0
		for i in range(self.__size):
			if self.__root[i] == i:
				libraries_no = libraries_no + 1
				roads_no = roads_no + self.__rank[i] - 1
		return [roads_no, libraries_no]
q = int(input().strip())
for a0 in range(q):
	(n, m, lib_cost, road_cost) = map(int, input().strip().split())
	processor = DisjointSet(n)
	for i in range(m):
		(a, b) = map(int, input().strip().split())
		processor.merge(a - 1, b - 1)
	if road_cost > lib_cost:
		print('{}'.format(n * lib_cost))
	else:
		(road_no, lib_no) = processor.count()
		print('{}'.format(lib_no * lib_cost + road_no * road_cost))


import sys

class City:

	def __init__(self, identifier):
		self.id = identifier
		self.neighbours = []
		self.library = False

	def build_library(self, c_lib, c_road):
		cost = c_lib
		self.library = True

		def repair_roads(city):
			cost = 0
			for neighbour in city.neighbours:
				if not neighbour.library:
					neighbour.library = True
					cost += c_road + repair_roads(neighbour)
			return cost
		cost += repair_roads(self)
		return cost

def make_broken_road(a, b):
	a.neighbours.append(b)
	b.neighbours.append(a)
q = int(input().strip())
for a0 in range(q):
	(n, m, c_lib, c_road) = [int(i) for i in input().strip().split(' ')]
	cities = [City(i) for i in range(n)]
	for a1 in range(m):
		(city_id_1, city_id_2) = [int(i) - 1 for i in input().strip().split(' ')]
		make_broken_road(cities[city_id_1], cities[city_id_2])
	if c_lib <= c_road:
		print(c_lib * n)
		continue
	final_cost = 0
	for (iden, city) in enumerate(cities):
		if city.library:
			continue
		final_cost += city.build_library(c_lib, c_road)
	print(final_cost)


import sys
q = int(input().strip())
for a0 in range(q):
	(n, m, c_lib, c_road) = (int(a) for a in input().strip().split(' '))
	graph = {num + 1: set() for num in range(n)}
	for a1 in range(m):
		(c1, c2) = (int(c) for c in input().strip().split(' '))
		graph[c1].add(c2)
		graph[c2].add(c1)
	if c_lib <= c_road:
		print(c_lib * n)
	else:
		used = set()

		def find_subtree(graph, start):
			used.add(start)
			size = 1
			for neighbor in graph[start]:
				if neighbor not in used:
					size += find_subtree(graph, neighbor)
			return size
		subtrees = []
		for node in graph:
			if node not in used:
				subtrees.append(find_subtree(graph, node))
		cost = c_lib * len(subtrees)
		for tree in subtrees:
			cost += c_road * (tree - 1)
		print(cost)


import sys

def explore(nodes, groups, c, i):
	num_nodes = 0
	arr = list(nodes[i])
	del nodes[i]
	for n in arr:
		if n in nodes:
			num_nodes += 1
			groups[c] += 1
			num_nodes += explore(nodes, groups, c, n)
	return num_nodes
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = [int(a) for a in input().strip().split(' ')]
	hmap = {}
	total_cost = 0
	for a1 in range(m):
		(city_1, city_2) = [int(x) for x in input().strip().split(' ')]
		if city_1 not in hmap:
			hmap[city_1] = set()
		hmap[city_1].add(city_2)
		if city_2 not in hmap:
			hmap[city_2] = set()
		hmap[city_2].add(city_1)
	if x <= y:
		print(n * x)
		continue
	groups = {}
	c = 0
	no_road_access = n
	for i in list(hmap.keys()):
		if i not in hmap:
			continue
		c += 1
		no_road_access -= 1
		groups[c] = 0
		no_road_access -= explore(hmap, groups, c, i)
	total_cost = x * no_road_access
	for k in groups.keys():
		total_cost += x + groups[k] * y
	print(total_cost)


q = int(input())
for i in range(q):
	(n, m, l, r) = [int(x) for x in input().strip().split(' ')]
	nodes = []
	for k in range(n):
		nodes.append({})
	for k in range(m):
		(u, v) = [int(x) for x in input().strip().split(' ')]
		u -= 1
		v -= 1
		nodes[u][v] = True
		nodes[v][u] = True
	if l <= r:
		print(l * n)
		continue
	visited = [False] * n
	q = []
	cluster = 0
	for k in range(n):
		if visited[k]:
			continue
		cluster += 1
		q.append(k)
		while len(q) > 0:
			next = q.pop()
			if visited[next]:
				continue
			visited[next] = True
			for key in nodes[next]:
				q.append(key)
	print(cluster * l + (n - cluster) * r)


import sys
import queue

def getProblem():
	(numCities, numRoads, libCost, roadCost) = map(int, input().split())
	graph = {}
	if libCost <= roadCost:
		for i in range(numRoads):
			input()
	else:
		for i in range(numRoads):
			(city1, city2) = map(int, input().split())
			for city in [city1, city2]:
				if city not in graph:
					graph[city] = []
			graph[city1].append(city2)
			graph[city2].append(city1)
	return (numCities, numRoads, libCost, roadCost, graph)

def solveProblem(numCities, numRoads, libCost, roadCost, graph):
	if libCost <= roadCost:
		return libCost * numCities
	citySet = {i for i in range(1, numCities + 1)}
	curCost = 0
	roadQueue = queue.Queue()
	while len(citySet) != 0:
		curNode = citySet.pop()
		curCost += libCost
		if curNode not in graph:
			continue
		for adjCity in graph[curNode]:
			roadQueue.put(adjCity)
		while not roadQueue.empty():
			curNode = roadQueue.get()
			if curNode not in citySet:
				continue
			citySet.remove(curNode)
			curCost += roadCost
			for adjCity in graph[curNode]:
				roadQueue.put(adjCity)
	return curCost

def main():
	numCases = int(input())
	for i in range(numCases):
		print(solveProblem(*getProblem()))
main()


from collections import defaultdict

def MinSpanTree(G, N):

	def MarkCC(G, start, marks, mark, nroads):
		if marks[start]:
			return (mark, nroads)
		marks[start] = mark
		stack = [start]
		while stack:
			for e in G[stack.pop()]:
				if not marks[e]:
					marks[e] = mark
					stack.append(e)
					nroads += 1
		return (mark + 1, nroads)
	marks = (N + 1) * [0]
	(mark, nroads) = (1, 0)
	for start in range(1, N + 1):
		(mark, nroads) = MarkCC(G, start, marks, mark, nroads)
	return (mark - 1, nroads)
q = int(input())
for _ in range(q):
	(n, m, lib_p, road_p) = map(int, input().split())
	G = defaultdict(set)
	for a1 in range(m):
		(city_1, city_2) = map(int, input().split())
		G[city_1].add(city_2)
		G[city_2].add(city_1)
	if lib_p <= road_p:
		print(n * lib_p)
	else:
		(nlib, nroads) = MinSpanTree(G, n)
		print(nlib * lib_p + nroads * road_p)


import sys
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	edges = []
	for a1 in range(m):
		edge = tuple(map(int, input().strip().split(' ')))
		edges.append(edge)
	if x <= y:
		print(n * x)
	else:
		components = 0
		neighs = [[] for _ in range(n)]
		for (a, b) in edges:
			if a == b:
				continue
			neighs[a - 1].append(b - 1)
			neighs[b - 1].append(a - 1)
		visited = [False for _ in range(n)]
		for a in range(n):
			if visited[a]:
				continue
			components += 1
			destinations = [a]
			while len(destinations) > 0:
				location = destinations.pop()
				if visited[location]:
					continue
				visited[location] = True
				for nb in neighs[location]:
					if not visited[nb]:
						destinations.append(nb)
		print(x * components + (n - components) * y)


import sys

class DisjointSets:

	def __init__(self, x):
		self.lst = [-1] * x

	def find(self, x):
		if self.lst[x] < 0:
			return x
		else:
			root = self.find(self.lst[x])
			self.lst[x] = root
			return root

	def setUnion(self, a, b):
		roota = self.find(a)
		rootb = self.find(b)
		if roota == rootb:
			return
		elif self.lst[roota] < self.lst[rootb]:
			self.lst[roota] += self.lst[rootb]
			self.lst[rootb] = roota
		else:
			self.lst[rootb] += self.lst[roota]
			self.lst[roota] = rootb

	def size(self, a):
		root = self.find(a)
		return -1 * self.lst[root]

	def isRoot(self, a):
		return self.lst[a] < 0
q = int(input().strip())
for a0 in range(q):
	(n, m, clib, croad) = input().strip().split(' ')
	(n, m, clib, croad) = [int(n), int(m), int(clib), int(croad)]
	dsets = DisjointSets(n + 1)
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		dsets.setUnion(city_1, city_2)
	if croad >= clib:
		print(clib * n)
	else:
		cost = 0
		for i in range(1, n + 1):
			if dsets.isRoot(i):
				cost += (dsets.size(i) - 1) * croad + clib
		print(cost)


import sys
from collections import deque

def count_cp(n, edges):
	if n <= 0:
		return 0
	visited = set()
	count = 0
	for node in range(1, n + 1):
		if node in visited:
			continue
		q = deque([node])
		while q:
			cur_node = q.popleft()
			visited.add(cur_node)
			for neighbor_node in edges.get(cur_node, []):
				if neighbor_node not in visited:
					q.append(neighbor_node)
		count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	edges = {}
	if x <= y:
		print(n * x)
		for a1 in range(m):
			(city_1, city_2) = input().strip().split(' ')
		continue
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		if city_1 in edges:
			edges[city_1].append(city_2)
		else:
			edges[city_1] = [city_2]
		if city_2 in edges:
			edges[city_2].append(city_1)
		else:
			edges[city_2] = [city_1]
	num_connected_comp = count_cp(n, edges)
	print(n * y + num_connected_comp * (x - y))


import sys

def connect(i, connected, adj_lists):
	res = 1
	connected[i] = True
	for j in adj_lists[i]:
		if not connected[j]:
			res += connect(j, connected, adj_lists)
	return res
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	adj_lists = [[] for j in range(n)]
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		city_1 -= 1
		city_2 -= 1
		adj_lists[city_1].append(city_2)
		adj_lists[city_2].append(city_1)
	if x < y:
		print(n * x)
	else:
		components = 0
		edges = 0
		connected = [False for x in range(n)]
		for i in range(n):
			if not connected[i]:
				components += 1
				edges += connect(i, connected, adj_lists) - 1
		print(components * x + edges * y)


import sys
q = int(input().strip())

def SPT(visited, city, graph, y):
	visited.add(city)
	que = [city]
	cost = 0
	while len(que) != 0:
		node = que.pop(0)
		for c in graph[node]:
			if c not in visited:
				visited.add(c)
				cost += y
				que.append(c)
	return cost
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	graph = [[] for _ in range(n + 1)]
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		graph[city_1].append(city_2)
		graph[city_2].append(city_1)
	if y > x:
		print(n * x)
		continue
	else:
		visited = set()
		cost = 0
		for i in range(1, n + 1):
			if i not in visited:
				cost += x + SPT(visited, i, graph, y)
	print(cost)


import sys

def recurs(seen, pairs, i):
	if seen[i]:
		return
	seen[i] = True
	for k in pairs[i]:
		recurs(seen, pairs, k)
	return
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	pairs = []
	for i in range(n):
		pairs.append([])
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1) - 1, int(city_2) - 1]
		pairs[city_1].append(city_2)
		pairs[city_2].append(city_1)
	seen = [False] * n
	blocks = 0
	for i in range(n):
		if not seen[i]:
			blocks += 1
			recurs(seen, pairs, i)
	ans = x * blocks + (n - blocks) * min(x, y)
	print(ans)


import sys

class Graph:

	def __init__(self):
		self.graph = {}

	def add_edge(self, c1, c2):
		if not c1 in self.graph:
			self.graph[c1] = []
		if not c2 in self.graph:
			self.graph[c2] = []
		self.graph[c1].append(c2)
		self.graph[c2].append(c1)

	def get_graph_profile(self):
		explored = set()
		clusters = []
		for start in self.graph:
			count = 0
			if start in explored:
				continue
			stack = [start]
			while stack:
				tmp = stack.pop()
				for edge in self.graph[tmp]:
					if not edge in explored:
						count += 1
						stack.append(edge)
						explored.add(edge)
			clusters.append(count)
		return clusters
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	city_network = Graph()
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		city_network.add_edge(city_1, city_2)
	if x <= y:
		print(n * x)
	else:
		network = city_network.get_graph_profile()
		orphans = n - sum(network)
		print(orphans * x + sum([x + y * (cluster - 1) for cluster in city_network.get_graph_profile()]))


q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, clib, croad) = [int(n), int(m), int(x), int(y)]
	cities = list(range(n))
	for a1 in range(m):
		(city_1, city_2) = [int(c) - 1 for c in input().strip().split(' ')]
		for c in [city_1, city_2]:
			p = c
			while cities[p] != p:
				p = cities[p]
			cities[c] = p
		if cities[city_2] > cities[city_1]:
			cities[cities[city_2]] = cities[city_1]
		else:
			cities[cities[city_1]] = cities[city_2]
	if clib < croad:
		print(n * clib)
		continue
	z = len([c for c in range(n) if cities[c] == c])
	print(z * clib + (n - z) * croad)


import sys

class node:

	def __init__(self, data=None):
		self.data = data
		self.par = None
		self.rank = 0

class disjointset:

	def __init__(self):
		self.dic = {}

	def makeset(self, data):
		newNode = node(data)
		newNode.par = newNode
		self.dic[data] = newNode

	def findset(self, Node):
		if Node.par == Node:
			return Node
		Node.par = self.findset(Node.par)
		return Node.par

	def union(self, x, y):
		Node1 = self.dic[x]
		Node2 = self.dic[y]
		rep1 = self.findset(Node1)
		rep2 = self.findset(Node2)
		if rep1.rank > rep2.rank:
			rep2.par = rep1
		else:
			rep1.par = rep2
			if rep1.rank == rep2.rank:
				rep2.rank = rep2.rank + 1
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	edges = []
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		edges.append((int(city_1), int(city_2)))
	if x <= y:
		print(n * x)
	else:
		ds = disjointset()
		for i in range(1, n + 1):
			ds.makeset(i)
		for i in range(0, m):
			ds.union(edges[i][0], edges[i][1])
		rep = []
		for i in range(1, n + 1):
			rep.append(ds.findset(ds.dic[i]).data)
		repdic = {i: 0 for i in rep}
		for i in rep:
			repdic[i] = repdic[i] + 1
		mincost = 0
		for i in repdic.keys():
			mincost = mincost + (repdic[i] - 1) * y + x
		print(mincost)


import sys

def bfs(graph, start):
	queue = [start]
	visited = []
	while queue:
		node = queue.pop()
		for neighbor in graph[node]:
			if neighbor not in visited:
				queue.append(neighbor)
		visited.append(node)
		queue = list(set(queue) - set(visited))
	return visited
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	if x <= y or m == 0:
		for a1 in range(m):
			(city_1, city_2) = input().strip().split(' ')
			(city_1, city_2) = [int(city_1), int(city_2)]
		print(x * n)
	else:
		c = [i + 1 for i in range(n)]
		cities = dict([(key, []) for key in c])
		groups = dict([(key, []) for key in c])
		for a1 in range(m):
			(city_1, city_2) = input().strip().split(' ')
			(city_1, city_2) = [int(city_1), int(city_2)]
			cities[city_1].append(city_2)
			cities[city_2].append(city_1)
		gcount = 0
		for i in groups:
			if groups[i] == []:
				gcount += 1
				groups[i] = gcount
				path = bfs(cities, i)
				for node in path:
					groups[node] = gcount
		print(x * gcount + y * (n - gcount))


import sys

class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.rank = [0 for x in range(n)]

	def find(self, v):
		if not v == self.parent[v]:
			self.parent[v] = self.find(self.parent[v])
		return self.parent[v]

	def union(self, x, y):
		xRoot = self.find(x)
		yRoot = self.find(y)
		if xRoot == yRoot:
			return
		if self.rank[xRoot] > self.rank[yRoot]:
			self.parent[yRoot] = xRoot
		else:
			self.parent[xRoot] = yRoot
			if self.rank[xRoot] == self.rank[yRoot]:
				self.rank[yRoot] += 1

	def printParent(self):
		print('index: ', list(range(9)))
		print('parent: ', self.parent, sep='')
q = int(input().strip())

def kill_remaining(num):
	for i in range(num):
		input().strip().split(' ')
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n_cities, n_roads, cost_lib, cost_road) = [int(n), int(m), int(x), int(y)]
	if cost_lib <= cost_road:
		print(n_cities * cost_lib)
		kill_remaining(n_roads)
		continue
	connected = [None] * (n_cities + 1)
	running_sum = 0
	curr_city = 0
	uf = UnionFind(n_cities)
	for a1 in range(n_roads):
		(city_1_s, city_2_s) = input().strip().split(' ')
		(city_1, city_2) = (int(city_1_s) - 1, int(city_2_s) - 1)
		if uf.find(city_1) != uf.find(city_2):
			uf.union(city_1, city_2)
	myDict = {}
	for node in range(n_cities):
		root = uf.find(node)
		if not root in myDict:
			myDict[root] = set([node])
		else:
			myDict[root].add(node)
	for mySet in myDict.values():
		running_sum += (len(mySet) - 1) * cost_road
	running_sum += len(myDict) * cost_lib
	print(running_sum)


import sys

def count_components(nodes):
	sets = {}
	for node in nodes:
		sets[node[0]] = DisjointSet()
	for node in nodes:
		for vtx in node[1]:
			sets[node[0]].union(sets[vtx])
	return len(set((x.find() for x in sets.values())))

class DisjointSet(object):

	def __init__(self):
		self.parent = None
		self.rank = 0

	def find(self):
		if self.parent is None:
			return self
		return self.parent.find()

	def union(self, other):
		self_root = self.find()
		other_root = other.find()
		if self_root == other_root:
			return
		if self_root.rank < other_root.rank:
			self_root.parent = other_root
		elif self_root.rank > other_root.rank:
			other_root.parent = self_root
		else:
			other_root.parent = self_root
			self_root.rank += 1
q = int(input().strip())
for a0 in range(q):
	(n, m, c_lib, c_road) = input().strip().split(' ')
	(n, m, c_lib, c_road) = [int(n), int(m), int(c_lib), int(c_road)]
	nodes = [[i, []] for i in range(1, n + 1)]
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = (int(city_1), int(city_2))
		nodes[city_1 - 1][1].append(city_2)
		nodes[city_2 - 1][1].append(city_1)
	if c_lib <= c_road:
		print(c_lib * n)
	else:
		num_components = count_components(nodes)
		print(c_lib * num_components + c_road * (n - num_components))


import sys
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	possible_connections = set()
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		possible_connections.add((city_1, city_2))
	adj_list = {}
	for connection in possible_connections:
		if connection[0] in adj_list:
			adj_list[connection[0]].add(connection[1])
		else:
			adj_list[connection[0]] = set([connection[1]])
		if connection[1] in adj_list:
			adj_list[connection[1]].add(connection[0])
		else:
			adj_list[connection[1]] = set([connection[0]])
	if x <= y:
		print(x * n)
		continue
	graphs = []
	while adj_list:
		(start, neighbors) = adj_list.popitem()
		graph = set([start])
		to_visit = neighbors
		while to_visit:
			node = to_visit.pop()
			graph.add(node)
			if node in adj_list:
				new_neighbors = adj_list.pop(node)
				to_visit = to_visit.union(new_neighbors)
		graphs.append(graph)
	num_graphs = len(graphs)
	num_connected_cities = sum((len(graph) for graph in graphs))
	num_unconnected_cities = n - num_connected_cities
	num_libraries = num_graphs + num_unconnected_cities
	num_roads = num_connected_cities - num_graphs
	print(x * num_libraries + y * num_roads)


import sys
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	if x <= y:
		print(x * n)
		for a1 in range(m):
			input()
	else:
		mat = {i: set() for i in range(n)}
		for a1 in range(m):
			(city_1, city_2) = input().strip().split(' ')
			(city_1, city_2) = [int(city_1) - 1, int(city_2) - 1]
			mat[city_1].add(city_2)
			mat[city_2].add(city_1)
		cost = 0
		while mat:
			cost += x
			q = []
			q.append(mat.popitem())
			while q:
				for i in q[0][1]:
					if i in mat:
						q.append((i, mat.pop(i)))
						cost += y
				del q[0]
		print(cost)


import sys
sys.setrecursionlimit(20000)

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

def ri():
	return int(input())

def dfs(u, edges, visited):
	visited.add(u)
	for v in edges[u]:
		if v not in visited:
			dfs(v, edges, visited)

def solve(n, m, clib, croad):
	edges = [[] for _ in range(n)]
	for _ in range(m):
		(u, v) = rints()
		edges[u - 1].append(v - 1)
		edges[v - 1].append(u - 1)
	if croad >= clib:
		return n * clib
	visited = set([])
	prev = 0
	total_cost = 0
	for u in range(n):
		if u not in visited:
			dfs(u, edges, visited)
			total_cost += clib + croad * (len(visited) - prev - 1)
			prev = len(visited)
	return total_cost

def main():
	for q in range(ri()):
		ans = solve(*rints())
		print(ans)
main()


import sys

def construct_edges(vertices, edges_):
	edgeDict = {}
	for edge in edges_:
		if edge[0] not in edgeDict:
			edgeDict[edge[0]] = [edge[1]]
		else:
			edgeDict[edge[0]].append(edge[1])
	for v in vertices:
		if v not in edgeDict:
			edgeDict[v] = []
	return edgeDict

def getRoots(aNeigh):

	def findRoot(aNode, aRoot):
		while aNode != aRoot[aNode][0]:
			aNode = aRoot[aNode][0]
		return (aNode, aRoot[aNode][1])
	myRoot = {}
	for myNode in aNeigh.keys():
		myRoot[myNode] = (myNode, 0)
	for myI in aNeigh:
		for myJ in aNeigh[myI]:
			(myRoot_myI, myDepthMyI) = findRoot(myI, myRoot)
			(myRoot_myJ, myDepthMyJ) = findRoot(myJ, myRoot)
			if myRoot_myI != myRoot_myJ:
				myMin = myRoot_myI
				myMax = myRoot_myJ
				if myDepthMyI > myDepthMyJ:
					myMin = myRoot_myJ
					myMax = myRoot_myI
				myRoot[myMax] = (myMax, max(myRoot[myMin][1] + 1, myRoot[myMax][1]))
				myRoot[myMin] = (myRoot[myMax][0], -1)
	myToRet = {}
	for myI in aNeigh:
		if myRoot[myI][0] == myI:
			myToRet[myI] = []
	for myI in aNeigh:
		myToRet[findRoot(myI, myRoot)[0]].append(myI)
	return myToRet
q = int(input().strip())
for a0 in range(q):
	edges_ = []
	vertices = []
	cost = 0
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		edges_.append((city_1, city_2))
		(city_1, city_2) = [int(city_1), int(city_2)]
	for i in range(1, n + 1):
		vertices.append(str(i))
	edgeDict = construct_edges(vertices, edges_)
	result = getRoots(edgeDict)
	for key in result:
		cost += x + y * (len(result[key]) - 1)
	if cost > len(vertices) * x:
		cost = len(vertices) * x
	print(cost)


import sys
import collections

class UF:

	def __init__(self, n):
		self.id = list(range(n))
		self.sz = [1] * n

	def root(self, x):
		while self.id[x] != x:
			self.id[x] = self.id[self.id[x]]
			x = self.id[x]
		return x

	def union(self, x, y):
		root_x = self.root(x)
		root_y = self.root(y)
		if root_x == root_y:
			return
		if self.sz[root_x] < self.sz[root_y]:
			self.id[root_x] = root_y
			self.sz[root_y] += self.sz[root_x]
		else:
			self.id[root_y] = root_x
			self.sz[root_x] += self.sz[root_y]
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	newUF = UF(n)
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1) - 1, int(city_2) - 1]
		newUF.union(city_1, city_2)
	if y >= x:
		print(n * x)
	else:
		counts = collections.Counter()
		for i in range(n):
			counts[newUF.root(i)] += 1
		ret = 0
		for (key, value) in counts.items():
			ret += x + (value - 1) * y
		print(ret)


import sys

class Node:

	def __init__(self):
		self.parent = None

	def get_root(self):
		if self.parent:
			root = self.parent.get_root()
			self.parent = root
			return root
		else:
			return self

def join(node1, node2):
	root1 = node1.get_root()
	root2 = node2.get_root()
	if root1 is root2:
		return 0
	else:
		root1.parent = root2
		return 1
for _ in range(int(input())):
	(n, m, x, y) = input().split()
	(n, m, x, y) = (int(n), int(m), int(x), int(y))
	node_arr = [Node() for _ in range(n)]
	if x <= y:
		for _ in range(m):
			input()
		print(n * x)
	else:
		road = 0
		for _ in range(m):
			(city_1, city_2) = input().split()
			(city_1, city_2) = (int(city_1) - 1, int(city_2) - 1)
			road += join(node_arr[city_1], node_arr[city_2])
		print((n - road) * x + road * y)


def graphs(graph):
	result = 0
	mark = [False] * len(graph)
	for i in range(len(graph)):
		if not mark[i]:
			result += 1
			mark[i] = True
			stack = [i]
			while len(stack) > 0:
				for j in graph[stack.pop()]:
					if not mark[j]:
						mark[j] = True
						stack.append(j)
	return result
q = int(input())
for i in range(q):
	(n, m, clib, croad) = [int(j) for j in input().split()]
	if clib < croad:
		for j in range(m):
			input()
		print(clib * n)
	else:
		graph = [[] for j in range(n)]
		for j in range(m):
			(u, v) = [int(k) for k in input().split()]
			graph[u - 1].append(v - 1)
			graph[v - 1].append(u - 1)
		g = graphs(graph)
		print(clib * g + croad * (n - g))


import sys

class Graph:

	def __init__(self, n):
		self.n = n
		self.neighbors = {node: [] for node in range(1, n + 1)}

	def connect(self, u, v):
		self.neighbors[u].append(v)
		self.neighbors[v].append(u)

	def connected_components(self):
		visited = set()
		component = 0
		components = {}

		def dfs(node):
			stack = [node]
			while stack:
				n = stack.pop()
				if n in visited:
					continue
				visited.add(n)
				components.setdefault(component, []).append(n)
				for neighbor in self.neighbors.setdefault(n, []):
					if neighbor not in visited:
						stack.append(neighbor)
		for node in range(1, self.n + 1):
			if node in visited:
				continue
			component += 1
			dfs(node)
		return components
q = int(input().strip())
for a0 in range(q):
	(n, m, c_lib, c_road) = map(int, input().strip().split(' '))
	graph = Graph(n)
	for a1 in range(m):
		(city_1, city_2) = map(int, input().strip().split(' '))
		graph.connect(city_1, city_2)
	cost = 0
	for (_, cities) in graph.connected_components().items():
		cities = len(cities)
		roads = cities - 1
		if roads == 0 or cities * c_lib < roads * c_road + c_lib:
			cost += cities * c_lib
		else:
			cost += roads * c_road + c_lib
	print(cost)


import sys

class Data(object):

	def __init__(self, name):
		self.__name = name
		self.__links = set()

	@property
	def name(self):
		return self.__name

	@property
	def links(self):
		return set(self.__links)

	def add_link(self, other):
		self.__links.add(other)
		other.__links.add(self)

def connected_components(nodes):
	result = []
	nodes = set(nodes)
	while nodes:
		n = nodes.pop()
		group = {n}
		queue = [n]
		while queue:
			n = queue.pop(0)
			neighbors = n.links
			neighbors.difference_update(group)
			nodes.difference_update(neighbors)
			group.update(neighbors)
			queue.extend(neighbors)
		result.append(group)
	return result
q = int(input().strip())
for a0 in range(q):
	(num_cities, num_edges, c_lib, c_road) = [int(num) for num in input().strip().split(' ')]
	edges = []
	for a1 in range(num_edges):
		edges.append([int(num) for num in input().strip().split(' ')])
	if c_road >= c_lib:
		print(c_lib * num_cities)
	else:
		nodes = {}
		for i in range(1, num_cities + 1):
			nodes[i] = Data(str(i))
		for (n1, n2) in edges:
			nodes[n1].add_link(nodes[n2])
		nodes = set([nodes[k] for k in nodes])
		clusters = connected_components(nodes)
		cost = len(clusters) * c_lib
		for cluster in clusters:
			cost += (len(cluster) - 1) * c_road
		print(cost)


from collections import defaultdict

class Graph:

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

	def addEdge(self, u, v):
		self.graph[u].append(v)

	def makeVisit(self):
		self.c = 0
		self.visited = {}
		self.length = 0
		for i in self.graph:
			self.visited[i] = False
			self.length += 1

	def DFSUtil(self, v):
		self.visited[v] = True
		self.c += 1
		for i in self.graph[v]:
			if self.visited[i] == False:
				self.DFSUtil(i)

	def DFS(self, v):
		if self.visited[v] == False:
			self.c = 0
			self.DFSUtil(v)
			return self.c
for test in range(int(input())):
	(city, road, clib, croads) = [int(x) for x in input().split()]
	g = Graph()
	for i in range(road):
		x = [int(x) for x in input().split()]
		g.addEdge(x[0], x[1])
		g.addEdge(x[1], x[0])
	if croads >= clib:
		print(city * clib)
		continue
	g.makeVisit()
	_r = 0
	_lib = 0
	for i in g.graph:
		if g.visited[i] == False:
			_r += g.DFS(i) - 1
			_lib += 1
	_lib += city - g.length
	print(_r * croads + _lib * clib)


import sys

def explore(graph, start, visited):
	elements = [start]
	while len(elements) > 0:
		i = elements.pop()
		for next in graph[i]:
			if next not in visited:
				visited.add(next)
				elements.append(next)

def getConnected(graph):
	connected = 0
	visited = set()
	for i in graph.keys():
		if i not in visited:
			visited.add(i)
			connected += 1
			explore(graph, i, visited)
	return connected
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	graph = {i: set() for i in range(n)}
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		graph[city_1 - 1].add(city_2 - 1)
		graph[city_2 - 1].add(city_1 - 1)
	if x <= y:
		print(n * x)
	else:
		c = getConnected(graph)
		print(c * x + (n - c) * y)


import sys

def root(f, n):
	while f[n] >= 0:
		n = f[n]
	return n

def join(f, a, b):
	(i, j) = (-f[a] // 2, 1)
	f[a] += f[b]
	while i and j < len(f) and False:
		if root(f, j) == b:
			f[j] = a
			i -= 0
		j += 1
	f[b] = a
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = [int(i) for i in input().strip().split(' ')]
	forest = [0] + [-1 for i in range(n)]
	for a1 in range(m):
		(city_1, city_2) = [int(city) for city in input().strip().split(' ')]
		if x >= y:
			(a, b) = (root(forest, city_1), root(forest, city_2))
			if a != b:
				(c, d) = (a, b) if forest[a] > forest[b] else (b, a)
				join(forest, c, d)
	if x < y:
		print(x * n)
	else:
		cost = 0
		for i in forest:
			if i < 0:
				cost += x - (i + 1) * y
		print(cost)


import sys
q = int(input().strip())
for a0 in range(q):
	sets = {}
	membership = {}
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	for i in range(1, n + 1):
		sets[i] = set([i])
		membership[i] = i
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		if x > y:
			if membership[city_1] != membership[city_2]:
				sets[membership[city_1]] = sets[membership[city_1]] | sets[membership[city_2]]
				z = membership[city_2]
				for i in sets[membership[city_2]]:
					membership[i] = membership[city_1]
				del sets[z]
	if x <= y:
		print(x * n)
	else:
		print((n - len(sets)) * y + len(sets) * x)


import sys

class UnionFind(object):

	def __init__(self, N):
		self.id = [i for i in range(N)]
		self.size = [1] * N
		self.components = N

	def _validate_range(self, i):
		if not 0 <= i <= len(self.id) - 1:
			raise IndexError('Index out of range')

	def find(self, i):
		self._validate_range(i)
		while i != self.id[i]:
			self.id[i] = self.id[self.id[i]]
			i = self.id[i]
		return i

	def components(self):
		return self.components

	def connected(self, i, j):
		self._validate_range(i)
		self._validate_range(j)
		root_i = self.find(i)
		root_j = self.find(j)
		return root_i == root_j

	def union(self, i, j):
		self._validate_range(i)
		self._validate_range(j)
		(root_i, root_j) = (self.find(i), self.find(j))
		if root_i == root_j:
			return False
		if self.size[root_i] < self.size[root_j]:
			(root_i, root_j) = (root_j, root_i)
		self.id[root_j] = root_i
		self.size[root_i] += self.size[root_j]
		self.size[root_j] = 0
		self.components -= 1
		return True

def solve(inp):
	(nodes, edges, lib_cost, road_cost) = [int(x) for x in inp.readline().strip().split()]
	uf = UnionFind(nodes)
	for line in range(edges):
		(a, b) = [int(x) for x in inp.readline().strip().split()]
		uf.union(a - 1, b - 1)
	if road_cost >= lib_cost:
		return nodes * lib_cost
	return uf.components * lib_cost + (nodes - uf.components) * road_cost

def main(inp=sys.stdin):
	queries = int(inp.readline().strip())
	for query in range(queries):
		print(solve(inp))
main()


import sys

def add_edge(c1, c2, adj):
	if adj.get(c1, None):
		adj[c1].append(c2)
	else:
		adj[c1] = []
		adj[c1].append(c2)
	if adj.get(c2, None):
		adj[c2].append(c1)
	else:
		adj[c2] = []
		adj[c2].append(c1)

def dfs(vertex, visited, adj, attr):
	visited[vertex] = True
	if adj.get(vertex, None):
		for neigh in adj.get(vertex):
			if not visited[neigh]:
				attr = dfs(neigh, visited, adj, attr)
	return attr + 1
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	adj = {}
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		add_edge(city_1, city_2, adj)
	visited = [False for i in range(0, n + 1)]
	cost = 0
	for i in range(1, len(visited)):
		if not visited[i]:
			count = dfs(i, visited, adj, 0)
			if x < y:
				cost = cost + count * x
			elif x == y:
				cost = cost + (count - 1) * x + x
			elif x > y:
				cost = cost + (count - 1) * y + x
	print(cost)


import sys

class Graph(object):

	def edges(self, node, **kwargs):
		return {}

	def nodes(self):
		return []

	def value(self, node):
		return None

	def total_edges(self):
		total = 0
		for node in self.nodes():
			total += len(self.edges(node))
		return total

class DirectedGraph(Graph):

	def __init__(self, G=None):
		G = G or {}
		self.G = {}
		for (a, edges) in G.items():
			for (b, weight) in edges.items():
				self.add_edge(a, b, weight)

	def edges(self, node, **kwargs):
		return self.G.get(node) or {}

	def add_edge(self, a, b, weight=1):
		if not a in self.G:
			self.G[a] = {}
		if not b in self.G:
			self.G[b] = {}
		self.G[a][b] = weight

	def nodes(self):
		return self.G.keys()

	def __str__(self):
		return str(self.G)

	def __repr__(self):
		return '<Directed %s>' % self

class UndirectedGraph(DirectedGraph):

	def __init__(self, G=None):
		super(UndirectedGraph, self).__init__(G)

	def add_edge(self, a, b, weight=1):
		super(UndirectedGraph, self).add_edge(a, b, weight)
		super(UndirectedGraph, self).add_edge(b, a, weight)

	def total_edges(self):
		return super().total_edges() // 2

	def __repr__(self):
		return '<Undirected %s>' % self

def floodfill(graph):
	result = {}
	i = 0
	for node in graph.nodes():
		if node in result:
			continue
		i += 1
		queue = [node]
		result[node] = i
		while queue:
			next = queue.pop()
			for neighbour in graph.edges(next):
				if not neighbour in result:
					queue.append(neighbour)
					result[neighbour] = i
	return (i, result)
q = int(input().strip())
for case in range(q):
	(n, m, library_cost, road_cost) = map(int, input().strip().split(' '))
	graph = UndirectedGraph()
	for i in range(n):
		graph.add_edge(i + 1, i + 1)
	for a1 in range(m):
		(c1, c2) = map(int, input().strip().split(' '))
		graph.add_edge(c1, c2)
	(components, d) = floodfill(graph)
	if library_cost < road_cost:
		result = library_cost * n
	else:
		result = library_cost * components + road_cost * (n - components)
	print(result)


from collections import deque
for _ in range(int(input())):
	(num_cities, num_roads, clib, croad) = [int(x) for x in input().split()]
	roads = [list() for _ in range(num_cities + 1)]
	for _ in range(num_roads):
		[a, b] = [int(x) for x in input().split()]
		roads[a].append(b)
		roads[b].append(a)
	cities = [True for _ in range(num_cities + 1)]
	cost_roads = 0
	todo = deque()
	for i in range(1, num_cities + 1):
		if cities[i]:
			cost_roads += clib - croad
			todo.append(i)
			cities[i] = False
			while todo:
				cost_roads += croad
				j = todo.popleft()
				for k in roads[j]:
					if cities[k]:
						todo.append(k)
						cities[k] = False
	print(min(cost_roads, clib * num_cities))


import sys

def dfs(node, edges, visited):
	visited[node] = True
	for i in edges[node]:
		if len(visited) < i + 1:
			kill()
		if not visited[i]:
			dfs(i, edges, visited)

def kill():
	while True:
		s = 5 + 3
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	n = int(n)
	m = int(m)
	x = int(x)
	y = int(y)
	if x <= y:
		print(n * x)
		for a1 in range(m):
			(city_1, city_2) = input().strip().split(' ')
			(city_1, city_2) = [int(city_1), int(city_2)]
	else:
		edges = [[] for i in range(n)]
		visited = [False for i in range(n)]
		for a1 in range(m):
			(city_1, city_2) = input().strip().split(' ')
			(city_1, city_2) = [int(city_1), int(city_2)]
			if len(edges) < city_1 or len(edges) < city_2:
				kill()
			edges[city_1 - 1].append(city_2 - 1)
			edges[city_2 - 1].append(city_1 - 1)
		libraries = 0
		for i in range(n):
			if len(visited) < i + 1:
				kill()
			if not visited[i]:
				libraries += 1
				dfs(i, edges, visited)
		print(x * libraries + y * (n - libraries))


def ret_set(graph, visited, node):
	if node in visited:
		return []
	visited.add(node)
	res = [node]
	for e in graph[node]:
		res += ret_set(graph, visited, e)
	return res
import sys
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	cost = 0
	found = False
	graph = {}
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		if city_1 or city_2 in graph:
			if city_1 in graph:
				graph[city_1].add(city_2)
			else:
				graph[city_1] = set()
				graph[city_1].add(city_2)
			if city_2 in graph:
				graph[city_2].add(city_1)
			else:
				graph[city_2] = set()
				graph[city_2].add(city_1)
	graphs_set = []
	visited = set()
	for key in graph:
		if key not in visited:
			ret = ret_set(graph, visited, key)
			graphs_set.append(ret)
			for e in ret:
				visited.add(e)
	length = 0
	for s in graphs_set:
		length += len(s)
	if length < n:
		cost += (n - length) * x
	for s in graphs_set:
		cost += min((len(s) - 1) * y + x, len(s) * x)
	print(cost)


def read_input(n, m):
	land = {city: set() for city in range(1, n + 1)}
	singlies = {i + 1 for i in range(n)}
	if m == 0:
		return (land, singlies)
	for a1 in range(m):
		(city_1, city_2) = map(int, input().split())
		singlies.discard(city_1)
		singlies.discard(city_2)
		land[city_1].add(city_2)
		land[city_2].add(city_1)
	return (land, singlies)
q = int(input().strip())
for a0 in range(q):
	(n, m, clib, croad) = map(int, input().split())
	(land, singlies) = read_input(n, m)
	un_cities = set([i + 1 for i in range(n)]) - singlies
	subgraphs = []
	while un_cities:
		temp = un_cities.pop()
		cities = land[temp]
		if not cities:
			land[temp] = set()
			continue
		else:
			count = 1
			nun_cities = cities
			while nun_cities:
				city = nun_cities.pop()
				un_cities.discard(city)
				count += 1
				new_cities = land[city].intersection(un_cities)
				nun_cities.update(new_cities)
			subgraphs.append(count)
	print(min(clib * n, sum([croad * (i - 1) + clib for i in subgraphs]) + clib * len(singlies)))


import sys
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	if x <= y:
		print(n * x)
		for a1 in range(m):
			(city_1, city_2) = input().strip().split(' ')
	else:
		sets = {i: set([i]) for i in range(1, n + 1)}
		ptrs = [i for i in range(1, n + 1)]
		for a1 in range(m):
			(city_1, city_2) = input().strip().split(' ')
			(city_1, city_2) = [int(city_1), int(city_2)]
			if ptrs[city_1 - 1] != ptrs[city_2 - 1]:
				unioncities = sets[ptrs[city_1 - 1]] | sets[ptrs[city_2 - 1]]
				del sets[ptrs[city_2 - 1]]
				sets[ptrs[city_1 - 1]] = unioncities
				for c in unioncities:
					ptrs[c - 1] = ptrs[city_1 - 1]
		print(len(sets) * x + sum([len(s) - 1 for s in sets.values()]) * y)


from queue import Queue
q = int(input().strip())

def comp_size(node, visited, adj):
	visited.add(node)
	consider = [node]
	while len(consider) != 0:
		curr = consider.pop()
		for i in adj[curr]:
			if i not in visited:
				visited.add(i)
				consider.append(i)
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	visited = set()
	adj = [set() for i in range(n + 1)]
	for a1 in range(m):
		(c1, c2) = input().strip().split(' ')
		(c1, c2) = [int(c1), int(c2)]
		adj[c1].add(c2)
		adj[c2].add(c1)
	if all([n * x <= k * x + (n - k) * y for k in range(1, n)]):
		print(n * x)
		continue
	comp = 0
	for i in range(1, n + 1):
		if i not in visited:
			comp_size(i, visited, adj)
			comp += 1
	print(comp * x + (n - comp) * y)


import sys

def root(arr, i):
	while arr[i] != i:
		i = arr[i]
	return i

def find(par_arr, a, b):
	if root(par_arr, a) == root(par_arr, b):
		return True
	else:
		return False

def union(par_arr, size_arr, a, b):
	root_a = root(par_arr, a)
	root_b = root(par_arr, b)
	if size_arr[root_a] > size_arr[root_b]:
		size_arr[root_a] += 1
		par_arr[root_b] = par_arr[root_a]
	else:
		size_arr[root_b] += 1
		par_arr[root_a] = par_arr[root_b]
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	siz_arr = [1] * (n + 1)
	par_arr = [i for i in range(0, n + 1)]
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		union(par_arr, siz_arr, city_1, city_2)
	if x <= y:
		print(n * x)
	else:
		cc = set()
		for i in range(1, n + 1):
			par_arr[i] = root(par_arr, i)
			cc.add(par_arr[i])
		len_cc = len(cc)
		print(len_cc * x + (n - len_cc) * y)


import sys
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	if y >= x or m == 0:
		print(n * x)
		for _ in range(m):
			input()
	else:
		cc = {i + 1: set((i + 1,)) for i in range(n)}
		for _ in range(m):
			(c1, c2) = input().strip().split(' ')
			(c1, c2) = sorted([int(c1), int(c2)])
			if c1 != c2 and cc[c1] != cc[c2]:
				cc[c1] |= cc[c2]
				for c in cc[c1]:
					cc[c] = cc[c1]
		print(sum((x + y * (len(s) - 1) for s in set((frozenset(cc[c]) for c in cc)) if len(s) > 0)))


import sys
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, cost_l, cost_r) = [int(n), int(m), int(x), int(y)]
	if cost_l <= cost_r:
		print(cost_l * n)
		for a1 in range(m):
			(city_1, city_2) = input().strip().split(' ')
			(city_1, city_2) = [int(city_1), int(city_2)]
	else:

		def find_component(graph):
			visited = set()

			def component(node):
				nodes = set([node])
				while nodes:
					node = nodes.pop()
					visited.add(node)
					nodes.update(graph[node] - visited)
					yield node
			for node in graph:
				if node not in visited:
					yield component(node)
		connected = {}
		nodes = [node for node in range(1, n + 1)]
		for a1 in range(m):
			(city_1, city_2) = input().strip().split(' ')
			(city_1, city_2) = [int(city_1), int(city_2)]
			if city_1 not in connected:
				connected[city_1] = set()
				connected[city_1].add(city_1)
			connected[city_1].add(city_2)
			if city_2 not in connected:
				connected[city_2] = set()
				connected[city_2].add(city_2)
			connected[city_2].add(city_1)
		for node in nodes:
			if node not in connected:
				connected[node] = set()
		result = 0
		for component in find_component(connected):
			current = set(component)
			if len(current) == 1:
				result += cost_l
			else:
				result += cost_l + (len(current) - 1) * cost_r
		print(result)


import sys

class node(object):

	def __init__(self):
		self.score = 0
		self.parent = self
		self.count = 0

def find_set(nodes_list, i):
	temp = nodes_list[i - 1]
	while temp.parent != temp:
		temp = temp.parent
	return temp

def union(nodes_list, i, j):
	if find_set(nodes_list, i).score > find_set(nodes_list, j).score:
		root = find_set(nodes_list, i)
		find_set(nodes_list, j).parent = root
	elif find_set(nodes_list, i).score < find_set(nodes_list, j).score:
		root = find_set(nodes_list, j)
		find_set(nodes_list, i).parent = root
	else:
		root = find_set(nodes_list, j)
		find_set(nodes_list, i).parent = root
		root.score += 1
q = int(input().strip())
for a0 in range(q):
	edges = []
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		edges.extend([(int(city_1), int(city_2))])
	if x <= y:
		print(n * x)
	else:
		cost = 0
		nodes_list = [node() for _ in range(n)]
		for i in edges:
			if find_set(nodes_list, i[0]) != find_set(nodes_list, i[1]):
				union(nodes_list, i[0], i[1])
		for i in range(len(nodes_list)):
			find_set(nodes_list, i + 1).count += 1
		for i in range(len(nodes_list)):
			if nodes_list[i].parent == nodes_list[i]:
				cost = cost + (nodes_list[i].count - 1) * y + x
		print(cost)


import sys

def connected_components(cities):
	result = []
	while cities:
		c = cities.pop()
		group = {c}
		queue = [c]
		while queue:
			c = queue.pop(0)
			neighbors = roadNet[c]
			neighbors.difference_update(group)
			cities.difference_update(neighbors)
			group.update(neighbors)
			queue.extend(neighbors)
		result.append(group)
	return result
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	if x <= y:
		print(x * n)
		for a1 in range(m):
			(city_1, city_2) = input().strip().split(' ')
			(city_1, city_2) = [int(city_1), int(city_2)]
		continue
	roadNet = dict()
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		if city_1 in roadNet:
			roadNet[city_1].add(city_2)
		else:
			roadNet[city_1] = {city_2}
		if city_2 in roadNet:
			roadNet[city_2].add(city_1)
		else:
			roadNet[city_2] = {city_1}
	unisolated_cities = set(roadNet.keys())
	isolated_citiesNum = n - len(unisolated_cities)
	cities_forest = connected_components(unisolated_cities)
	cost = isolated_citiesNum * x
	for i in range(len(cities_forest)):
		cost += (len(cities_forest[i]) - 1) * y + x
	print(cost)


import sys

def visit(i, l, notvisited, tovisit):
	tovisit |= set([x for x in l[i] if x in notvisited])

def comp(l):
	notvisited = set(range(len(l)))
	comps = 0
	tovisit = set()
	while len(notvisited) > 0:
		start = notvisited.pop()
		visit(start, l, notvisited, tovisit)
		while len(tovisit) > 0:
			i = tovisit.pop()
			notvisited.remove(i)
			visit(i, l, notvisited, tovisit)
		comps += 1
	return comps
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	l = list()
	for i in range(n):
		l.append(list())
	cities = set(range(n))
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1) - 1, int(city_2) - 1]
		l[city_1].append(city_2)
		l[city_2].append(city_1)
	if x < y:
		print(x * n)
	else:
		components = comp(l)
		print(components * x + y * (n - components))


import sys

def solve(clib, croad, city):
	if city.hasLibrary:
		return 0
	libraries = 1
	roads = 0
	stack = [city]
	while stack:
		vertex = stack.pop()
		if vertex.hasLibrary:
			continue
		vertex.hasLibrary = True
		if vertex != city:
			if clib < croad:
				libraries += 1
			else:
				roads += 1
		for neighbour in vertex.neighbours:
			if neighbour.hasLibrary:
				continue
			stack.append(neighbour)
	return libraries * clib + roads * croad

class City:

	def __init__(self, n):
		self.neighbours = set()
		self.hasLibrary = False

	def addNeighbour(self, n):
		self.neighbours.add(n)
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, clib, croad) = [int(n), int(m), int(x), int(y)]
	cities = [City(x) for x in range(n)]
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1) - 1, int(city_2) - 1]
		cities[city_1].addNeighbour(cities[city_2])
		cities[city_2].addNeighbour(cities[city_1])
	output = 0
	for i in range(n):
		output += solve(clib, croad, cities[i])
	print(output)


import sys
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	graph = {city + 1: set() for city in range(n)}
	cities_to_connect = {k: 1 for k in graph}
	connected_cities = {}
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		graph[city_1].add(city_2)
		graph[city_2].add(city_1)
	total_cost = 0
	while cities_to_connect:
		current_city = cities_to_connect.popitem()[0]
		total_cost += x
		adjacent_list = list(graph[current_city])
		while adjacent_list:
			current_adjacent = adjacent_list.pop()
			if current_adjacent in cities_to_connect:
				adjacent_list.extend(list(graph[current_adjacent]))
				cities_to_connect.pop(current_adjacent, 0)
				total_cost += min(x, y)
	print(total_cost)


import sys
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	f = list(range(n))
	siz = [1 for i in f]

	def Find(a):
		ff = f[a]
		if ff == a:
			return ff
		ff = Find(ff)
		f[a] = ff
		return ff

	def Union(a, b):
		aa = Find(a)
		bb = Find(b)
		if aa != bb:
			f[aa] = bb
			siz[bb] += siz[aa]
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		Union(city_1 - 1, city_2 - 1)
	sep = []
	for i in range(n):
		if f[i] == i:
			sep.append(siz[i])
	ans = 0
	for s in sep:
		if y > x:
			ans += s * x
		else:
			ans += x + (s - 1) * y
	print(ans)


import sys

def input_to_numbers():
	return [int(x) for x in input().strip().split(' ')]

def dfs(graph, start):
	(visited, stack) = (set(), [start])
	while stack:
		vertex = stack.pop()
		if vertex not in visited:
			visited.add(vertex)
			stack.extend(graph[vertex] - visited)
	return visited

def add_street(g, a, b):
	connected_cities = g.get(a, set())
	connected_cities.add(b)
	g[a] = connected_cities
q = int(input().strip())

def solve():
	for a1 in range(m):
		(city_1, city_2) = input_to_numbers()
		add_street(graph, city_1, city_2)
		add_street(graph, city_2, city_1)
	visited = set()
	libs = 0
	streets = 0
	for i in range(1, n + 1):
		if i not in graph:
			libs += 1
			visited.add(i)
		elif i not in visited:
			group_visited = dfs(graph, i)
			visited.update(group_visited)
			libs += 1
			streets += len(group_visited) - 1
	return x * libs + y * streets

def min_solve():
	for a1 in range(m):
		input()
	return n * x
for a0 in range(q):
	graph = dict()
	(n, m, x, y) = input_to_numbers()
	print(solve() if x > y else min_solve())


import sys
from collections import defaultdict, deque

def get_clusters(n, roads):
	clusters = {}
	total_visited = set()
	for i in range(1, n + 1):
		if i not in total_visited:
			clusters[i] = bfs(i, roads)
			total_visited |= clusters[i]
	return clusters

def bfs(root, roads):
	queue = deque([root])
	visited = set()
	if root not in roads:
		return set([root])
	while queue:
		node = queue.popleft()
		if node not in roads:
			continue
		for next_node in roads[node].keys():
			if next_node not in visited:
				visited.add(next_node)
				queue.append(next_node)
	return visited
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, c_lib, c_road) = [int(n), int(m), int(x), int(y)]
	roads = defaultdict(dict)
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		roads[city_1][city_2] = True
		roads[city_2][city_1] = True
	if c_lib <= c_road:
		total = n * c_lib
	else:
		clusters = get_clusters(n, roads)
		values = [(len(cluster) - 1) * c_road for cluster in clusters.values()]
		total = len(clusters) * c_lib
		if values:
			total += sum(values)
	print(total)


import sys
import collections
q = int(input().strip())
for a0 in range(q):
	edges = []
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		edges.append([city_1 - 1, city_2 - 1])

	def find(v):
		if grp[v] != v:
			grp[v] = find(grp[v])
		return grp[v]
	grp = list(range(n))
	for (u, v) in edges:
		grp[find(u)] = find(v)
	area = collections.Counter(map(find, grp))
	print(min(len(area) * x + (n - len(area)) * y, n * x))


from collections import defaultdict

def count_children(node, g, v):
	v.add(node)
	return sum((1 + count_children(child, g, v) for child in g[node] if child not in v))
for _ in range(int(input().strip())):
	(n, m, clib, croad) = [int(x) for x in input().strip().split(' ')]
	graph = defaultdict(set)
	for _ in range(m):
		(u, v) = [int(x) for x in input().strip().split(' ')]
		graph[u].add(v)
		graph[v].add(u)
	if clib <= croad:
		print(clib * n)
	else:
		visited = set()
		cost = sum((clib + croad * count_children(node, graph, visited) for node in graph if node not in visited))
		cost += clib * (n - len(graph))
		print(cost)


import sys
import collections

def connected_components(edges):
	adj = collections.defaultdict(set)
	for (u, v) in edges:
		adj[u].add(v)
		adj[v].add(u)
	sizes = []
	visited = set()
	for i in adj.keys():
		if i in visited:
			continue
		size = 0
		agenda = {i}
		while agenda:
			v = agenda.pop()
			visited.add(v)
			size += 1
			agenda.update(adj[v] - visited)
		sizes.append(size)
	return sizes

def main():
	q = int(input().strip())
	for i in range(q):
		(cities, roads, lC, rC) = input().strip().split(' ')
		(cities, roads, lC, rC) = [int(cities), int(roads), int(lC), int(rC)]
		routes = []
		for x in range(roads):
			(city_1, city_2) = input().strip().split(' ')
			(city_1, city_2) = [int(city_1), int(city_2)]
			routes.append([city_1, city_2])
		graph = connected_components(routes)
		res1 = cities * lC
		res2 = 0
		cityCount = 0
		for x in range(len(graph)):
			if graph[x] > 0:
				res2 += (graph[x] - 1) * rC + lC
				cityCount += graph[x]
		res2 += lC * (cities - cityCount)
		print(min(res1, res2))
main()


import collections

class City:

	def __init__(self, num):
		self.num = num
		self.visited = False
		self.neighbors = []

	def __str__(self):
		return str(self.num)

	def __repr__(self):
		return 'City{%s, %s, %s}' % (self.num, self.visited, [str(n) for n in self.neighbors])

	def add_neighbor(self, other):
		self.neighbors.append(other)

def run_bfs(start_city):
	q = collections.deque()
	q.append(start_city)
	while q:
		city = q.popleft()
		if city.visited:
			continue
		city.visited = True
		q.extend(city.neighbors)

def num_connected_components(cities):
	result = 0
	for city in cities:
		if not city.visited:
			result += 1
			run_bfs(city)
	return result

def min_cost(cities, cost_lib, cost_road):
	if cost_lib <= cost_road:
		return cost_lib * len(cities)
	else:
		components = num_connected_components(cities)
		return cost_lib * components + cost_road * (len(cities) - components)
num_queries = int(input().strip())
for _ in range(num_queries):
	(num_cities, num_roads, cost_lib, cost_road) = list(map(int, input().strip().split(' ')))
	cities = [City(i) for i in range(1, num_cities + 1)]
	for _ in range(num_roads):
		(src_num, dst_num) = input().strip().split(' ')
		src = cities[int(src_num) - 1]
		dst = cities[int(dst_num) - 1]
		src.add_neighbor(dst)
		dst.add_neighbor(src)
	print(min_cost(cities, cost_lib, cost_road))


import sys

def dfs(a, current, visited):
	visited[current] = True
	for i in a[current]:
		if i not in visited:
			dfs(a, i, visited)

def DFSTraversal(a):
	visited = {}
	p = 0
	for i in a:
		if i not in visited:
			dfs(a, i, visited)
			p += 1
	return p
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	a = {}
	for i in range(1, n + 1):
		a[i] = []
	for i in range(m):
		(c1, c2) = input().strip().split(' ')
		(c1, c2) = [int(c1), int(c2)]
		a[c1].append(c2)
		a[c2].append(c1)
	if x < y:
		print(n * x)
		continue
	p = DFSTraversal(a)
	print((n - p) * y + p * x)


from collections import defaultdict, Counter

class Graph:

	def __init__(self, numCity, libCost, roadCost):
		self.numCity = numCity
		self.libCost = libCost
		self.roadCost = roadCost
		self.roadConnections = defaultdict(list)
		self.forest = [x for x in range(numCity + 1)]

	def addConnection(self, source, dest):
		self.roadConnections[source].append(dest)
		self.roadConnections[dest].append(source)

	def rank(self):
		stack = []
		for cur in range(1, self.numCity + 1):
			if self.forest[cur] == cur:
				for neighbor in self.roadConnections[cur]:
					stack.append(neighbor)
				while len(stack) != 0:
					node = stack.pop()
					if self.forest[node] < node:
						continue
					self.forest[node] = cur
					for neighbor in self.roadConnections[node]:
						if self.forest[neighbor] == cur or neighbor in stack:
							continue
						stack.append(neighbor)
for _ in range(int(input())):
	(numCity, numRoad, libCost, roadCost) = map(int, input().split())
	graph = Graph(numCity, libCost, roadCost)
	for _ in range(numRoad):
		(source, destination) = map(int, input().split())
		graph.addConnection(source, destination)
	if graph.libCost <= graph.roadCost:
		print(graph.libCost * graph.numCity)
	else:
		graph.rank()
		counter = Counter(graph.forest)
		rankSum = 0
		for (k, v) in counter.items():
			if k == 0:
				continue
			rankSum += graph.libCost + graph.roadCost * (v - 1)
		print(rankSum)


import sys

def dfs(node, check, graph, flag):
	if check[node] != None:
		return
	check[node] = flag
	if node in graph:
		for i in graph[node]:
			dfs(i, check, graph, flag)
	return
q = int(input().strip())
for a0 in range(q):
	(n, m, clib, croad) = map(int, input().strip().split(' '))
	graph = {}
	for path in range(m):
		(u, v) = map(int, input().split())
		try:
			graph[u].append(v)
		except KeyError:
			graph[u] = [v]
		try:
			graph[v].append(u)
		except KeyError:
			graph[v] = [u]
	if clib <= croad:
		print(n * clib)
	else:
		check = [None for i in range(n + 1)]
		flag = 0
		for i in range(1, n + 1):
			if check[i] == None:
				flag += 1
				dfs(i, check, graph, flag)
		ans = 0
		counter = {}
		for i in range(1, flag + 1):
			counter[i] = 0
		for i in range(1, n + 1):
			counter[check[i]] += 1
		for i in range(1, flag + 1):
			ans += clib + croad * counter[i] - croad
		print(ans)


import sys

def dfs_mark(start, gid, edj):
	n = len(gid)
	for e in edj[start]:
		if gid[e] == 0:
			gid[e] = gid[start]
			dfs_mark(e, gid, edj)
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	L = x
	R = y
	if L <= R:
		for a1 in range(m):
			(city_1, city_2) = input().strip().split(' ')
		print(L * n)
		continue
	edj = [[] for x in range(0, n)]
	gid = [0 for x in range(0, n)]
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1) - 1, int(city_2) - 1]
		edj[city_1].append(city_2)
		edj[city_2].append(city_1)
	acc = 1
	for i in range(0, n):
		if gid[i] == 0:
			gid[i] = acc
			acc += 1
			dfs_mark(i, gid, edj)
	acc -= 1
	print(L * acc + (n - acc) * R)


from collections import defaultdict
import sys

def dfs(v, visited, edges):
	st = [v]
	visited.add(v)
	res = 0
	while st:
		v = st.pop()
		res += 1
		for i in edges[v]:
			if i not in visited:
				st.append(i)
				visited.add(i)
	return res
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	edges = defaultdict(list)
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1) - 1, int(city_2) - 1]
		edges[city_1].append(city_2)
		edges[city_2].append(city_1)
	visited = set()
	ans = 0
	for i in range(n):
		if i not in visited:
			r = dfs(i, visited, edges)
			ans += min((r - 1) * y + x, r * x)
	print(ans)


import sys

def browse(g, v, a):
	res = [a]
	v[a] = 1
	s = g[a]
	while len(s) > 0:
		a = s.pop()
		if not v[a]:
			v[a] = 1
			res.append(a)
			s.extend(g[a])
	return res

def solve(g, n, m, lib, road):
	res = 0
	v = [0 for _ in range(n + 1)]
	disj = []
	for a in g:
		if not v[a]:
			disj.append(browse(g, v, a))
	for sg in disj:
		res = res + lib + (len(sg) - 1) * road
	return res
q = int(input().strip())
for a0 in range(q):
	(n, m, lib, road) = map(int, input().strip().split(' '))
	g = {i: [] for i in range(1, n + 1)}
	for a1 in range(m):
		(a, b) = map(int, input().strip().split(' '))
		g[a].append(b)
		g[b].append(a)
	res = 0
	if road >= lib:
		res = lib * n
	else:
		res = solve(g, n, m, lib, road)
	print(res)


import collections
import sys

def readline_ints(stdinp):
	return map(int, stdinp.readline().split())

def main(sinp=sys.stdin, sout=sys.stdout):
	q = int(sinp.readline())
	for query in range(q):
		roads = collections.defaultdict(list)
		(n, m, c_lib, c_road) = readline_ints(sinp)
		for _ in range(m):
			(u, v) = readline_ints(sinp)
			roads[u].append(v)
			roads[v].append(u)
		if c_lib <= c_road:
			result = n * c_lib
		else:
			visited = [False] * (n + 1)
			cluster_no = 0
			result = 0
			for i in range(1, n + 1):
				if not visited[i]:
					cluster_no += 1
					to_do = [i]
					city_no = 0
					while to_do:
						current_city = to_do.pop()
						if not visited[current_city]:
							visited[current_city] = True
							city_no += 1
							for city in roads[current_city]:
								if not visited[city]:
									to_do.append(city)
					result += (city_no - 1) * c_road
			result += cluster_no * c_lib
		print(result, file=sout)
main()


import sys
import collections

def get_groups(edges):
	neighbors = collections.defaultdict(set)
	for (u, v) in edges:
		neighbors[u].add(v)
		neighbors[v].add(u)
	sizes = []
	visited = set()
	for u in neighbors.keys():
		if u in visited:
			continue
		size = 0
		agenda = {u}
		while agenda:
			v = agenda.pop()
			visited.add(v)
			size += 1
			agenda.update(neighbors[v] - visited)
		sizes.append(size)
	return sizes
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	comp = n * x
	temp = []
	dic = {}
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		if city_1 not in dic:
			dic[city_1] = 0
		if city_2 not in dic:
			dic[city_2] = 0
		temp.append([city_1, city_2])
	result = get_groups(temp)
	total = 0
	for i in result:
		total += min(x + (i - 1) * y, x * i)
	if len(dic) != n:
		total += (n - len(dic)) * x
	print(min(total, comp))


import sys

def danhdau(k):
	if c[k] == 0:
		c[k] = 1
	for i in range(len(lienthong[k])):
		if c[lienthong[k][i]] == 0:
			danhdau(lienthong[k][i])
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	lienthong = [[] for i in range(n)]
	c = [0 for i in range(n)]
	lt = 0
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		lienthong[city_1 - 1].append(city_2 - 1)
		lienthong[city_2 - 1].append(city_1 - 1)
	if x > y:
		for i in range(n):
			if c[i] == 0:
				lt += 1
				danhdau(i)
		print(lt * x + (n - lt) * y)
	else:
		print(n * x)


import sys

class Graph:
	order = 1

	def __init__(self, n):
		self.order = n
		self.edge_list = dict()
		for x in range(n):
			self.edge_list[x] = set()

	def add_edge(self, a, b):
		self.edge_list[a].add(b)
		self.edge_list[b].add(a)

	def component(self, a):
		stack = []
		stack.append(a)
		closed = set()
		while stack:
			node = stack.pop()
			if node in closed:
				continue
			closed.add(node)
			nbrs = self.edge_list[node]
			for nbr in nbrs:
				if nbr not in closed:
					stack.append(nbr)
		return closed

	def component_list(self):
		closed = set()
		comp_list = []
		for x in range(self.order):
			if x in closed:
				continue
			comp = self.component(x)
			for node in comp:
				closed.add(node)
			comp_list.append(len(comp))
		return comp_list
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	g = Graph(n)
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		g.add_edge(city_1 - 1, city_2 - 1)
	if x <= y:
		print(n * x)
		continue
	comp_list = g.component_list()
	num_libs = len(comp_list)
	num_roads = sum(comp_list) - num_libs
	print(num_libs * x + num_roads * y)


import sys
from collections import defaultdict
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	d = defaultdict(set)
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		d[city_1].add(city_2)
		d[city_2].add(city_1)
	if x <= y:
		print(n * x)
	else:
		total = 0
		visited = [False] * n
		start = 1
		while True:
			key = 0
			for i in range(start, n + 1):
				if not visited[i - 1]:
					key = i
					break
			if not key:
				break
			visited[key - 1] = True
			(c, city) = (d[key].copy(), set())
			city.add(key)
			start = key + 1
			while len(c) > 0:
				temp = c.pop()
				if visited[temp - 1]:
					continue
				city.add(temp)
				visited[temp - 1] = True
				c |= d[temp]
			total += (len(city) - 1) * y + x
		print(total)


import sys

def add_edge(g, n_1, n_2):
	if n_1 not in g:
		g[n_1] = []
	g[n_1].append(n_2)

def solver(n_s_num, e_s_num, c_n, c_e, e_s):
	node_sector_map = {}
	s_id = 0
	for n in range(1, n_s_num + 1):
		if n not in node_sector_map:
			s_id += 1
			if n not in e_s:
				node_sector_map[n] = s_id
			else:
				stack = [] + e_s[n]
				while len(stack) > 0:
					nn = stack.pop()
					if nn not in node_sector_map:
						node_sector_map[nn] = s_id
						if nn in e_s:
							stack = stack + e_s[nn]
	sectors_lengths = [0] * s_id
	for n in node_sector_map:
		sectors_lengths[node_sector_map[n] - 1] += 1
	sum = 0
	for s_l in sectors_lengths:
		if c_e > c_n:
			sum += s_l * c_n
		else:
			sum += (s_l - 1) * c_e + c_n
	return sum
q = int(input().strip())
for a0 in range(q):
	edges = {}
	(n, m, x, y) = list(map(int, input().strip().split(' ')))
	for a1 in range(m):
		(city_1, city_2) = list(map(int, input().strip().split(' ')))
		add_edge(edges, city_1, city_2)
		add_edge(edges, city_2, city_1)
	print(solver(n, m, x, y, edges))


import sys

def add_connection(connections, a, b):
	graph_delta = 0
	if a in connections and b not in connections:
		connections[a].append(b)
		connections[b] = connections[a]
	elif a not in connections and b in connections:
		connections[b].append(a)
		connections[a] = connections[b]
	elif a not in connections and b not in connections:
		connections[a] = [a, b]
		connections[b] = connections[a]
		graph_delta = 1
	elif connections[a] != connections[b]:
		kept = connections[a]
		kept.extend(connections[b])
		for city in connections[b]:
			connections[city] = kept
		graph_delta = -1
	return graph_delta

def count_subgraphs(connections):
	count = 0
	left = [city for city in connections]
	while left:
		current = left.pop()
		for city in connections[current]:
			try:
				left.remove(city)
			except ValueError:
				pass
		count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(n, m, c_lib, c_road) = input().strip().split(' ')
	(n, m, c_lib, c_road) = [int(n), int(m), int(c_lib), int(c_road)]
	connections = dict()
	sub_graphs = 0
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		sub_graphs += add_connection(connections, city_1, city_2)
	if c_road >= c_lib:
		lib_qty = n
		road_qty = 0
	else:
		lonely_cities = n - len(connections)
		lib_qty = sub_graphs + lonely_cities
		road_qty = n - lib_qty
	print(c_lib * lib_qty + c_road * road_qty)


import sys

def findComponents(graph):
	visited = set()
	stack = []
	result = []
	for u in range(len(graph)):
		if u in visited:
			continue
		stack.append(u)
		current = 0
		while len(stack) > 0:
			v = stack.pop()
			if v in visited:
				continue
			current += 1
			visited.add(v)
			adjacents = list(filter(lambda x: x not in visited, graph[v]))
			stack.extend(adjacents)
		result.append(current)
	return result
q = int(input().strip())
for _ in range(q):
	(n, m, clib, croad) = list(map(int, input().strip().split()))
	if clib <= croad or m == 0:
		for _ in range(m):
			input()
		print(clib * n)
		continue
	graph = [[] for _ in range(n)]
	for _ in range(m):
		(u, v) = list(map(int, input().strip().split()))
		u -= 1
		v -= 1
		graph[u].append(v)
		graph[v].append(u)
	components = findComponents(graph)
	cost = 0
	for component in components:
		nodes = component
		cost += clib
		cost += (nodes - 1) * croad
	print(cost)


import sys

def find_connected(adj):

	def dfs(n, adj, visited):
		res = list()
		if n in visited:
			return res
		visited.add(n)
		res.append(n)
		for nei in adj[n]:
			if nei not in visited:
				res.extend(dfs(nei, adj, visited))
		return res
	N = len(adj)
	visited = set()
	clusters = list()
	for n in range(N):
		if n in visited:
			continue
		new_cluster = dfs(n, adj, set())
		for x in new_cluster:
			visited.add(x)
		clusters.append(new_cluster)
	return clusters

def solve(c_lib, c_road, adj):
	if c_lib <= c_road:
		return len(adj) * c_lib
	N = len(adj)
	clusters = find_connected(adj)
	cost = 0
	for c in clusters:
		cost += min((len(c) - 1) * c_road + c_lib, len(c) * c_lib)
	return cost
q = int(input())
for _ in range(q):
	(num_nodes, num_roads, clib, croad) = map(int, input().split())
	adj = {n: list() for n in range(num_nodes)}
	for _ in range(num_roads):
		(n1, n2) = map(lambda x: int(x) - 1, input().split())
		adj[n1].append(n2)
		adj[n2].append(n1)
	print(solve(clib, croad, adj))


import sys

def solve(n, m, c_lib, c_road, Emap):
	if c_road >= c_lib:
		return n * c_lib
	U = set(range(1, n + 1))
	S = set()
	ans = 0
	while U:
		y = U.pop()
		ans += c_lib
		Q = set(Emap[y])
		while Q:
			x = Q.pop()
			if x in U:
				ans += c_road
				U.remove(x)
				Q |= Emap[x]
	return ans
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	Emap = [set() for i in range(n + 1)]
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		Emap[city_1].add(city_2)
		Emap[city_2].add(city_1)
	print(solve(n, m, x, y, Emap))


import sys
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	total_cost = n * x
	root_city = list(range(n + 1))
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		if x > y:
			target_city = city_1
			root_1 = root_city[city_1]
			while root_1 != target_city:
				target_city = root_1
				root_1 = root_city[target_city]
			target_city = city_2
			root_2 = root_city[city_2]
			while root_2 != target_city:
				target_city = root_2
				root_2 = root_city[target_city]
			if root_1 != root_2:
				if root_1 > root_2:
					root_city[root_1] = root_2
				else:
					root_city[root_2] = root_1
				total_cost -= x - y
	print(total_cost)


import sys

def dfs(graph, start):
	explored = set([start])
	vstack = [start]
	while len(vstack) != 0:
		cnode = vstack[-1]
		bnext = False
		for node in graph[cnode]:
			if bnext:
				break
			if node not in explored:
				vstack.append(node)
				explored.add(node)
				bnext = True
		if not bnext:
			vstack.pop()
	return explored

def connected_components(graph):
	explored = set()
	ccomp = []
	for node in graph:
		if node in explored:
			continue
		component = dfs(graph, node)
		ccomp.append(component)
		explored |= component
	return ccomp
q = int(input().strip())
for _ in range(q):
	(n, m, clib, croad) = [int(val) for val in input().strip().split(' ')]
	if clib <= croad or m == 0:
		for _ in range(m):
			input()
		print(clib * n)
	else:
		graph = {}
		for node in range(1, n + 1):
			graph[node] = []
		for _ in range(m):
			(city_1, city_2) = [int(val) for val in input().strip().split(' ')]
			graph[city_1].append(city_2)
			graph[city_2].append(city_1)
		nCC = len(connected_components(graph))
		cost = nCC * clib + croad * (n - nCC)
		print(min(clib * n, cost))


import sys
from collections import defaultdict

def mincost(n_cities, n_roads, c_lib, c_rd, roads):
	if n_cities == 0:
		return 0
	if c_lib < c_rd or n_roads == 0:
		return n_cities * c_lib
	seen = set()
	cost = 0
	for i in range(1, n_cities + 1):
		if i in seen:
			continue
		cost += c_lib - c_rd
		stack = [i]
		while stack:
			j = stack.pop()
			if j in seen:
				continue
			seen.add(j)
			cost += c_rd
			stack.extend([k for k in roads[j] if k not in seen])
	return cost
q = int(input().strip())
for a0 in range(q):
	(n_cities, n_roads, c_lib, c_rd) = list(map(int, input().strip().split(' ')))
	roads = defaultdict(set)
	for _ in range(n_roads):
		(u, v) = list(map(int, input().strip().split(' ')))
		roads[u].add(v)
		roads[v].add(u)
	print(str(mincost(n_cities, n_roads, c_lib, c_rd, roads)))


from collections import defaultdict

def readInts():
	return map(int, input().strip().split())

def best_repair_price(n, r, l, g):
	if l <= r:
		return n * l
	out = 0
	for x in get_connected_sizes(n, g):
		out += l + (x - 1) * r
	return out

def get_connected_sizes(n, g):
	visited = [False for _ in range(n)]
	out = []
	for start_node in range(n):
		if visited[start_node]:
			continue
		remain = [start_node]
		count = 0
		while remain:
			node = remain.pop()
			if visited[node]:
				continue
			visited[node] = True
			count += 1
			for o_n in g[node]:
				if visited[o_n]:
					continue
				remain.append(o_n)
		out.append(count)
	return out
(q,) = readInts()
for _ in range(q):
	(n, m, cl, cr) = readInts()
	g = defaultdict(list)
	for _ in range(m):
		(nf, nt) = readInts()
		(nf, nt) = (nf - 1, nt - 1)
		g[nf].append(nt)
		g[nt].append(nf)
	print(best_repair_price(n, cr, cl, g))


import sys
from collections import defaultdict

def getInt():
	return int(input().strip())

def getIntArray():
	return list(map(int, input().strip().split()))

class DJNode:

	def __init__(self, value):
		self.value = value
		self.next = None

class DJSet:

	def __init__(self):
		self.head = None
		self.tail = None
		self.size = 0

	def add(self, node):
		self.size += 1
		if not self.head:
			self.head = node
		if not self.tail:
			self.tail = node
		else:
			self.tail.next = node
			self.tail = node

	def remove(self, value):
		prev = None
		cur = self.head
		while cur != None:
			if cur.value == value:
				if prev:
					prev.next = cur.next
				if cur == self.head:
					self.head = cur.next
				if cur == self.tail:
					self.tail = prev
				self.size -= 1
				return
			prev = cur
			cur = cur.next

	def find(self, value):
		cur = self.head
		while cur != None:
			if cur.value == value:
				return True
			cur = cur.next
		return False

	def union(self, set2):
		self.tail.next = set2.head
		self.tail = set2.tail
		self.size += set2.size

	def printValues(self):
		cur = self.head
		if cur:
			print('[', end='')
			while cur.next != None:
				print(cur.value, end='-->')
				cur = cur.next
			print(cur.value, end=']\n')
		else:
			print('[]')

class DisjointSet:

	def __init__(self):
		self.sets = defaultdict(int)

	def addSet(self, index):
		if not self.sets[index]:
			self.sets[index] = DJSet()
		else:
			print('Set ' + str(index) + ' already exists!')

	def addToSet(self, index, value):
		if self.sets[index]:
			self.sets[index].add(DJNode(value))
		else:
			print('Set ' + str(index) + ' does not exist')
			del self.sets[index]

	def union(self, set1, set2):
		if self.sets[set1] and self.sets[set2]:
			self.sets[set1].union(self.sets.pop(set2))
		elif self.sets[set1] and (not self.sets[set2]):
			print('Set ' + str(set2) + ' does not exist')
			del self.sets[set2]
		elif self.sets[set2] and (not self.sets[set1]):
			print('Set ' + str(set1) + ' does not exist')
			del self.sets[set1]
		else:
			print('Neither set ' + str(set1) + ' nor set ' + str(set2) + ' exist')
			del self.sets[set1]
			del self.sets[set2]

	def find(self, value):
		for (k, v) in self.sets.items():
			if v.find(value):
				return k
		return None

	def printSets(self):
		for (k, v) in self.sets.items():
			print('Set ' + str(k) + ': ', end='')
			v.printValues()

	def removeSet(self, index):
		del self.sets[index]

	def getSize(self, index):
		if self.sets[index]:
			return self.sets[index].size
		else:
			print('Set ' + str(index) + ' does not exist')
			del self.sets[index]

	def getTotalSize(self):
		size = 0
		for (k, v) in self.sets.items():
			size += self.getSize(k)
		return size
q = getInt()
for a0 in range(q):
	(num_cities, num_roads, cost_lib, cost_road) = getIntArray()
	seen_map = [0] * (num_cities + 1)
	sets = DisjointSet()
	set_num = 1
	for i in range(num_roads):
		(c1, c2) = getIntArray()
		set1 = seen_map[c1]
		set2 = seen_map[c2]
		if set1 and set2 and (set1 != set2):
			cur = sets.sets[set2].head
			while cur is not None:
				seen_map[cur.value] = set1
				cur = cur.next
			sets.union(set1, set2)
		elif set1 and (not set2):
			sets.addToSet(set1, c2)
			seen_map[c2] = set1
		elif set2 and (not set1):
			sets.addToSet(set2, c1)
			seen_map[c1] = set2
		elif not set1 and (not set2):
			sets.addSet(set_num)
			sets.addToSet(set_num, c1)
			sets.addToSet(set_num, c2)
			seen_map[c1] = seen_map[c2] = set_num
			set_num += 1
	cost = 0
	for i in range(num_cities - sets.getTotalSize()):
		cost += cost_lib
	for key in sets.sets:
		size = sets.getSize(key)
		if cost_lib <= cost_road:
			cost += size * cost_lib
		else:
			cost += cost_lib + (size - 1) * cost_road
	print(cost)


def adj(n, edges):
	M = [[] for _ in range(n)]
	for (n1, n2) in edges:
		M[n1].append(n2)
		M[n2].append(n1)
	return M

def componentSizes(M):
	visited = [False] * len(M)
	sizes = []
	for (n, v) in enumerate(visited):
		if not v:
			visited[n] = True
			queue = [n]
			size = 1
			while queue:
				current = queue.pop(0)
				for adj in M[current]:
					if not visited[adj]:
						visited[adj] = True
						queue.append(adj)
						size += 1
			sizes.append(size)
	return sizes

def minCost(n, edges, cLib, cEdge):
	if cLib <= cEdge:
		return n * cLib
	M = adj(n, edges)
	components = componentSizes(M)
	return cEdge * sum((n - 1 for n in components)) + cLib * len(components)
q = int(input())
for _ in range(q):
	(n, m, cLib, cRoad) = map(int, input().split(' '))
	edges = tuple((tuple(map(lambda x: int(x) - 1, input().split(' '))) for _ in range(m)))
	print(minCost(n, edges, cLib, cRoad))


from collections import deque
q = int(input().strip())
for qi in range(q):
	(n, m, c_lib, c_road) = list(map(int, input().strip().split(' ')))
	adj = [[] for _ in range(n)]
	for a1 in range(m):
		(city_1, city_2) = list(map(int, input().strip().split(' ')))
		adj[city_1 - 1].append(city_2 - 1)
		adj[city_2 - 1].append(city_1 - 1)
	visited = [False] * n
	que = deque()

	def bfs(s):
		visited[s] = True
		count = 1
		que.append(s)
		while len(que) > 0:
			cur = que.popleft()
			for i in adj[cur]:
				if not visited[i]:
					visited[i] = True
					count += 1
					que.append(i)
		return count
	cost = 0
	for i in range(n):
		if not visited[i]:
			connected_cities = bfs(i)
			cost += min((connected_cities - 1) * c_road + c_lib, connected_cities * c_lib)
	print(cost)


import sys
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	if x <= y:
		print(n * x)
		for a1 in range(m):
			input()
	else:
		in_region = [-1] * (n + 1)
		regions = {}
		num_c_region = {}
		isolated_cities = n
		visited_cities = [0] * n
		new_region = 1
		for a1 in range(m):
			(city_1, city_2) = input().strip().split(' ')
			(city_1, city_2) = [int(city_1), int(city_2)]
			if visited_cities[city_1 - 1] == 0:
				isolated_cities -= 1
				visited_cities[city_1 - 1] = 1
			if visited_cities[city_2 - 1] == 0:
				isolated_cities -= 1
				visited_cities[city_2 - 1] = 1
			if in_region[city_1] > 0 and in_region[city_2] < 0:
				region = in_region[city_1]
				in_region[city_2] = region
				regions[region].append(city_2)
				num_c_region[region] += 1
			elif in_region[city_2] > 0 and in_region[city_1] < 0:
				region = in_region[city_2]
				in_region[city_1] = region
				regions[region].append(city_1)
				num_c_region[region] += 1
			elif in_region[city_1] == -1 and in_region[city_2] == -1:
				in_region[city_1] = new_region
				in_region[city_2] = new_region
				regions[new_region] = [city_1, city_2]
				num_c_region[new_region] = 2
				new_region += 1
			elif not in_region[city_1] == in_region[city_2]:
				region1 = in_region[city_1]
				region2 = in_region[city_2]
				num_c_region[region1] = num_c_region[region1] + num_c_region[region2]
				num_c_region[region2] = 0
				for c in regions[region2]:
					in_region[c] = region1
				regions[region1] = regions[region1] + regions[region2]
				regions[region2] = []
		cost = isolated_cities * x
		for region in num_c_region:
			if num_c_region[region] > 0:
				cost += x
				cost += y * (num_c_region[region] - 1)
		print(cost)


import sys
from collections import defaultdict

def groupLinkedNodes(nodes, links):
	groups = [n for n in range(max(nodes) + 1)]
	contains = defaultdict(list)
	for n in nodes:
		contains[groups[n]].append(n)
	for link in links:
		oldGroup = groups[link[1]]
		newGroup = groups[link[0]]
		if oldGroup != newGroup:
			groups[link[1]] = newGroup
			for i in contains[oldGroup]:
				groups[i] = newGroup
			contains[newGroup].extend(contains[oldGroup])
			contains.pop(oldGroup)
	return [len(contains[k]) for k in contains.keys()]
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	roads = list()
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		roads.append((city_1, city_2))
	if x <= y:
		print(x * n)
		continue
	cost = 0
	nodeGroups = groupLinkedNodes([n for n in range(1, n + 1)], roads)
	for g in nodeGroups:
		cost += x + (g - 1) * y
	print(cost)


import sys
nodes = []

class Node:

	def __init__(self, val):
		self.value = val
		self.connected = []
		self.node_status = 0

	def __repr__(self):
		return '  Node:' + str(self.value) + ' Connections:' + str(self.connected)

def num_connected_nodes(j):
	if nodes[j].node_status == 1:
		return 0
	nodes[j].node_status = 1
	result = 1
	for i in nodes[j].connected:
		result += num_connected_nodes(i)
	return result
q = int(input().strip())
for a0 in range(q):
	(n, m, x, y) = input().strip().split(' ')
	(n, m, x, y) = [int(n), int(m), int(x), int(y)]
	nodes = [Node(i) for i in range(n + 1)]
	for a1 in range(m):
		(city_1, city_2) = input().strip().split(' ')
		(city_1, city_2) = [int(city_1), int(city_2)]
		nodes[city_1].connected.append(city_2)
		nodes[city_2].connected.append(city_1)
	if x < y:
		print(n * x)
		continue
	cost = 0
	for i in range(n):
		j = i + 1
		if nodes[j].node_status == 0:
			cost += y * (num_connected_nodes(j) - 1) + x
	print(cost)