There are $2\times N$ nodes in an undirected graph, and a number of edges connecting some nodes.  In each edge, the first value will be between $1$ and $N$, inclusive.  The second node will be between $N+1$ and $2\times N$, inclusive.  Given a list of edges, determine the size of the smallest and largest connected components that have $2$ or more nodes.  A node can have any number of connections.  The highest node value will always be connected to at least $1$ other node.    

Note
Single nodes should not be considered in the answer. 

Example 

$bg=[[1,5],[1,6],[2,4]]$

The smaller component contains $2$ nodes and the larger contains $3$.  Return the array $[2,3]$.    

Function Description 

Complete the connectedComponents function in the editor below.  

connectedComponents has the following parameter(s): 

-   int bg[n][2]: a 2-d array of integers that represent node ends of graph edges

Returns 

-   int[2]: an array with 2 integers, the smallest and largest component sizes  

Input Format

The first line contains an integer $n$, the size of $bg$. 

Each of the next $n$ lines contain two space-separated integers, $bg[i][0]$ and $bg[i][1]$.   

Constraints

$1\leq number of{nodesN}\leq15000$  
$1\leq bg[i][0]\leq N$  
$N+1\le bg[i][1]\le2N$  

Sample Input
STDIN   Function
-----   --------
5       bg[] size n = 5
1 6     bg = [[1, 6],[2, 7], [3, 8], [4,9], [2, 6]]
2 7
3 8
4 9
2 6

Sample Output
2 4

Explanation

Since the component with node $5$ contains only one node, it is not considered.  

The number of vertices in the smallest connected component in the graph is $2$ based on either $(3,8)$ or $(4,9)$.  

The number of vertices in the largest connected component in the graph is $4$ i.e. $1-2-6-7$.

Difficulty: MEDIUM
Tags: Spanning trees

Starter code:

Solutions:
class UF:

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

	def _parent(self, a):
		while self.parent[a] != a:
			self.parent[a] = self.parent[self.parent[a]]
			a = self.parent[a]
		return a

	def _size(self, a):
		return self.size[self._parent(a)]

	def merge(self, a, b):
		(a, b) = (self._parent(a), self._parent(b))
		if a != b:
			if self._size(a) < self._size(b):
				(a, b) = (b, a)
			self.parent[b] = a
			self.size[a] += self.size[b]

	def __repr__(self):
		return self.parent.__str__() + '\n' + self.size.__str__()
T = int(input())
uf = UF(T * 2)
for _ in range(T):
	uf.merge(*map(int, input().split()))
print(min((sz for (node, sz) in zip(range(T * 2 + 1), uf.size) if sz != 1 and node == uf._parent(node))), end=' ')
print(max(uf.size))


from collections import deque, defaultdict

def bfs(g, s):
	visited = set()
	q = deque([s])
	while q:
		v = q.popleft()
		visited.add(v)
		for adj in g[v]:
			if adj not in visited and adj not in q:
				q.append(adj)
	return visited

def con_components(g):
	visited = set()
	components = []
	for s in g.keys():
		if s not in visited:
			nodes = bfs(g, s)
			visited |= nodes
			components.append(nodes)
	return components
n = int(input())
g = defaultdict(list)
for _ in range(n):
	(a, b) = map(int, input().split())
	g[a].append(b)
	g[b].append(a)
c = con_components(g)
lens = list(map(len, c))
print(min(lens), max(lens))


from sys import stderr

def join(who1, who2, parent, pop):
	who1 = flatten(who1, parent, pop)
	who2 = flatten(who2, parent, pop)
	if who1 == who2:
		return
	if who1 > who2:
		(who1, who2) = (who2, who1)
	parent[who2] = who1
	pop[who1] += pop[who2]

def flatten(who, parent, pop):
	start = who
	li = [who]
	while parent[who] is not None:
		who = parent[who]
		li.append(who)
	ans = who
	for (who, dad) in zip(li[:-2], li[1:]):
		pop[dad] -= pop[who]
		parent[who] = ans
	return ans
n = int(input())
parent = [None] * (2 * n)
pop = [1] * (2 * n)
seen = set()
for _ in range(n):
	(g, b) = [int(fld) - 1 for fld in input().split()]
	seen.add(g)
	seen.add(b)
	join(g, b, parent, pop)
component = [pop1 for (i, (par1, pop1)) in enumerate(zip(parent, pop)) if i in seen and par1 is None]
print(min(component), max(component))


import sys
sys.setrecursionlimit(30000)
N = int(input())
adjList = [[] for i in range(2 * N + 1)]
for i in range(N):
	L = input().split()
	u = int(L[0])
	v = int(L[1])
	adjList[u].append(v)
	adjList[v].append(u)

def connected(G, N):
	marked = [False for i in range(2 * N + 1)]

	def dfs(G, s):
		nonlocal marked
		nonlocal count
		marked[s] = True
		count += 1
		for v in G[s]:
			if not marked[v]:
				dfs(G, v)
	cc = []
	count = 0
	for v in range(1, 2 * N + 1):
		if not marked[v]:
			count = 0
			dfs(G, v)
			if count != 1:
				cc.append(count)
	return cc
L = connected(adjList, N)
print(min(L), max(L))


from collections import Counter

class UF:

	def __init__(self, N):
		self.__elements = [x for x in range(N)]
		self.__sz = [1 for x in range(N)]

	def __root(self, i):
		while i != self.__elements[i]:
			self.__elements[i] = self.__elements[self.__elements[i]]
			i = self.__elements[i]
		return i

	def union(self, p, q):
		i = self.__root(p)
		j = self.__root(q)
		if i != j:
			if self.__sz[i] < self.__sz[j]:
				self.__elements[i] = j
				self.__sz[j] += self.__sz[i]
			else:
				self.__elements[j] = i
				self.__sz[i] += self.__sz[j]

	def connected(self, p, q):
		return self.__root(p) == self.__root(q)

	def solve(self):
		roots = []
		for i in range(len(self.__elements)):
			if self.__root(i) == i:
				roots.append(i)
		res = sorted(list(set([self.__sz[i] for i in roots])))
		if res[0] == 1:
			res = res[1:]
		assert len(res) > 0
		print(res[0], res[-1])
N = int(input())
uf = UF(2 * N)
for _ in range(N):
	(p, q) = [int(x) for x in input().split()]
	uf.union(p - 1, q - 1)
uf.solve()


class Ufds(object):

	def __init__(self, n):
		self.p = [i for i in range(0, n + 1)]
		self.r = [0] * (n + 1)

	def findSet(self, i):
		if self.p[i] == i:
			return i
		else:
			self.p[i] = self.findSet(self.p[i])
			return self.p[i]

	def isSameSet(self, i, j):
		return self.findSet(i) == self.findSet(j)

	def unionSet(self, i, j):
		if self.r[i] == 0:
			self.r[i] = 1
		if self.r[j] == 0:
			self.r[j] = 1
		if not self.isSameSet(i, j):
			x = self.findSet(i)
			y = self.findSet(j)
			if self.r[x] > self.r[y]:
				self.p[y] = x
				self.r[x] += self.r[y]
			else:
				self.p[x] = y
				self.r[y] += self.r[x]
n = int(input())
ufds = Ufds(n * 2)
for i in range(n):
	(x, y) = map(int, input().split())
	ufds.unionSet(x, y)
max_rank = 0
min_rank = n * 2 + 1
for i in range(1, n * 2 + 1):
	if ufds.p[i] == i and ufds.r[i] > 0:
		max_rank = max(max_rank, ufds.r[i])
		min_rank = min(min_rank, ufds.r[i])
print(min_rank, max_rank)


import sys
inp = sys.stdin.read()
lines = inp.splitlines()
N = int(lines.pop(0))

class Node:

	def __init__(self, identity):
		self.children = set()
		self._id = identity

	def add(self, other):
		self.children.add(other)

	def __eq__(self, other):
		return other._id == self._id

	def __hash__(self):
		return self._id

def dfs(node, visited):
	initial = len(visited)
	to_visit = []
	to_visit.append(node)
	while to_visit:
		dfs_visit(to_visit.pop(), visited, to_visit)
	return len(visited) - initial

def dfs_visit(node, visited, to_visit):
	visited[node] = 1
	for child in node.children:
		if child not in visited:
			to_visit.append(child)
nodes = [Node(i) for i in range(1, 2 * N + 1)]
for line in lines:
	(Gn, Bn) = [int(x) for x in line.split()]
	nodes[Gn - 1].add(nodes[Bn - 1])
	nodes[Bn - 1].add(nodes[Gn - 1])
sizes = set()
visited = {}
for node in nodes:
	if node.children and node not in visited:
		sizes.add(dfs(node, visited))
print(str(min(sizes)) + ' ' + str(max(sizes)))


class Node(object):

	def __init__(self, idx, count=1, parent=None):
		self.idx = idx
		self.count = count
		self.parent = parent

	def root(self):
		r = self
		while r.parent:
			r = r.parent
		return r

def merge(rootlist, a, b):
	ra = a.root()
	rb = b.root()
	if ra == rb:
		return
	if ra.count < rb.count:
		ra.parent = rb
		rb.count += ra.count
		i = ra.idx
		rootlist[i] = rootlist[-1]
		rootlist[i].idx = i
		rootlist.pop()
	else:
		rb.parent = ra
		ra.count += rb.count
		i = rb.idx
		rootlist[i] = rootlist[-1]
		rootlist[i].idx = i
		rootlist.pop()
n = int(input())
rootlist = [Node(i) for i in range(n * 2 + 1)]
nodelist = rootlist[:]
for _ in range(n):
	(g, b) = map(int, input().split())
	merge(rootlist, nodelist[g], nodelist[b])
n_min = min((r.count for r in rootlist if r.count > 1))
n_max = max((r.count for r in rootlist))
print(n_min, n_max)


import sys

class disjoint:

	def __init__(self, size):
		self.parent = {}
		self.size = {}

	def root(self, p):
		while p != self.parent[p]:
			p = self.parent[p]
		return p

	def connect(self, p, q):
		if p not in self.parent:
			self.parent[p] = p
			self.size[p] = 1
		if q not in self.parent:
			self.parent[q] = q
			self.size[q] = 1
		if self.isconnected(p, q):
			return
		i = self.root(p)
		j = self.root(q)
		if self.size[i] < self.size[j]:
			self.parent[i] = j
			self.size[j] += self.size[i]
		else:
			self.parent[j] = i
			self.size[i] += self.size[j]

	def isconnected(self, p, q):
		return self.root(p) == self.root(q)
n = int(sys.stdin.readline())
dis = disjoint(2 * n)
for line in sys.stdin:
	comps = line.split(' ')
	(p, q) = tuple(map(int, comps))
	dis.connect(p, q)
print('{0} {1}'.format(min([dis.size[i] for i in dis.size.keys() if dis.parent[i] == i]), max(dis.size.values())))


N = int(input().strip())
GB = [set([i]) for i in range(N * 2 + 1)]
for i in range(N):
	(g, b) = list(map(int, input().strip().split()))
	GB[g].add(b)
	GB[b].add(g)
res = []
idx = 1
visited = set()
minS = float('inf')
maxS = float('-inf')
while idx <= N:
	while idx in visited:
		idx += 1
	curr = set([idx])
	visited.add(idx)
	q = GB[idx]
	while q:
		newQ = set()
		curr |= q
		for one in q - visited:
			newQ |= GB[one]
		visited |= q
		q = newQ
	if len(curr) > 1:
		res.append(curr)
		minS = min(minS, len(curr))
		maxS = max(maxS, len(curr))
	idx += 1
print(' '.join(map(str, [minS, maxS])))


class DisjointSet:

	def __init__(self):
		self.parent = self
		self.rank = 0
		self.size = 1

def Union(x, y):
	xRoot = Find(x)
	yRoot = Find(y)
	if xRoot == yRoot:
		return
	elif xRoot.rank < yRoot.rank:
		xRoot.parent = yRoot
		yRoot.size += xRoot.size
	elif xRoot.rank > yRoot.rank:
		yRoot.parent = xRoot
		xRoot.size += yRoot.size
	else:
		yRoot.parent = xRoot
		xRoot.rank = xRoot.rank + 1
		xRoot.size += yRoot.size

def Find(x):
	if x.parent != x:
		x.parent = Find(x.parent)
	return x.parent
N = int(input())
persons = [DisjointSet() for i in range(N + N)]
for i in range(N):
	(a, b) = tuple([int(x) - 1 for x in input().split()])
	Union(persons[a], persons[b])
(min_size, max_size) = (float('inf'), 0)
for person in persons:
	min_size = min(min_size, Find(person).size if Find(person).size > 1 else float('inf'))
	max_size = max(max_size, Find(person).size)
print('{} {}'.format(min_size, max_size))


n = int(input())
g = [[] for _ in range(2 * n)]
for _ in range(n):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	g[u].append(v)
	g[v].append(u)
a = 2 * n
b = 0
d = [True for _ in range(2 * n)]
for v in range(2 * n):
	if d[v]:
		s = [v]
		d[v] = False
		c = 0
		while len(s) > 0:
			x = s.pop()
			c += 1
			for y in g[x]:
				if d[y]:
					s.append(y)
					d[y] = False
		if c > 1:
			a = min(a, c)
			b = max(b, c)
print(a, b)


class disjointset:

	class Node:

		def __init__(self, data):
			self.data = data
			self.parent = None
			self.rank = 0
			self.size = 1

		def __repr__(self):
			return 'N({}:r{}:p{})'.format(self.data, self.rank, self.parent.data)

	def __init__(self):
		self.m = dict()
		self.s = set()

	def makeset(self, data):
		node = self.Node(data)
		node.parent = node
		node.rank = 0
		self.m[data] = node
		self.s.add(node)

	def find(self, data):
		if isinstance(data, self.Node):
			p = data.parent
			if p is data:
				return p
			else:
				data.parent = self.find(data.parent)
				self.s.discard(data)
				return data.parent
		else:
			return self.find(self.m[data]).data

	def union(self, d1, d2):
		n1 = self.m[d1]
		n2 = self.m[d2]
		p1 = self.find(n1)
		p2 = self.find(n2)
		if p1.data == p2.data:
			return
		if p1.rank >= p2.rank:
			p1.rank = p1.rank + (1 if p1.rank == p2.rank else 0)
			p2.parent = p1
			self.s.discard(p2)
			p2.rank = 0
			p1.size += p2.size
		else:
			p1.parent = p2
			self.s.discard(p1)
			p1.rank = 0
			p2.size += p1.size

	def size(self, data):
		return self.find(self.m[data]).size

	def contains(self, data):
		return self.__contains__(data)

	def __contains__(self, data):
		return data in self.m
n = int(input())
dj = disjointset()
for _ in range(n):
	(b, g) = map(int, input().split())
	if b not in dj:
		dj.makeset(b)
	if g not in dj:
		dj.makeset(g)
	dj.union(b, g)
s = sorted([x.size for x in dj.s])
print(s[0], s[-1])


from collections import Counter

class Node(object):

	def __init__(self, val):
		self.val = val
		self.parent = self
		self.rank = 0

def find(x):
	if x.parent == x:
		return x
	else:
		return find(x.parent)

def union(x, y):
	xRoot = find(x)
	yRoot = find(y)
	if xRoot.rank < yRoot.rank:
		xRoot.parent = yRoot
	elif yRoot.rank < xRoot.rank:
		yRoot.parent = xRoot
	else:
		xRoot.parent = yRoot
		yRoot.rank += 1
N = int(input().strip())
Nodes = []
for i in range(1, 2 * N + 1):
	Node_i = Node(i)
	Nodes.append(Node_i)
for i in range(N):
	(G, B) = list(map(int, input().strip().split()))
	G = G - 1
	B = B - 1
	union(Nodes[G], Nodes[B])
Roots = [find(x) for x in Nodes]
CC_size = Counter()
for root in Roots:
	CC_size[root] += 1
max_size = 0
min_size = 2 * N
for key in CC_size:
	size = CC_size[key]
	if size == 1:
		continue
	max_size = max(max_size, size)
	min_size = min(min_size, size)
print(min_size, max_size)


class DisjointSet(object):

	class Node(object):

		def __init__(self, data, parent=None, rank=0):
			self.data = data
			self.parent = parent if parent else self
			self.rank = rank
			self.elements = 1

	def __init__(self):
		self.parent = {}
		self.max_component = None

	def make_set(self, data):
		node = self.Node(data)
		self.parent[data] = node

	def union(self, data1, data2):
		node1 = self.parent[data1]
		node2 = self.parent[data2]
		parent1 = self.find_set(node1)
		parent2 = self.find_set(node2)
		if parent1.data == parent2.data:
			return
		if parent1.rank >= parent2.rank:
			parent1.rank = parent1.rank + 1 if parent1.rank == parent2.rank else parent1.rank
			parent2.parent = parent1
			parent1.elements += parent2.elements
			if not self.max_component or parent1.elements > self.max_component:
				self.max_component = parent1.elements
		else:
			parent1.parent = parent2
			parent2.elements += parent1.elements
			if not self.max_component or parent2.elements > self.max_component:
				self.max_component = parent2.elements

	def find_set(self, node):
		parent = node.parent
		if parent == node:
			return parent
		node.parent = self.find_set(node.parent)
		return node.parent

	def get_min_component(self):
		min_c = None
		for node in self.parent.values():
			parent = self.find_set(node)
			if parent.elements != 1:
				if not min_c or parent.elements < min_c:
					min_c = parent.elements
		return min_c

	def answer(self):
		print(self.get_min_component(), self.max_component)
n = int(input())
ds = DisjointSet()
for i in range(1, 2 * n + 1):
	ds.make_set(i)
for _ in range(n):
	(a, b) = [int(x) for x in input().split()]
	ds.union(a, b)
ds.answer()


def Find(uf, u):
	while u != uf[u]:
		uf[u] = uf[uf[u]]
		u = uf[u]
	return u

def Unify(uf, sz, u, v):
	label_u = Find(uf, u)
	label_v = Find(uf, v)
	if label_u != label_v:
		if sz[label_u] < sz[label_v]:
			uf[label_u] = label_v
			sz[label_v] += sz[label_u]
		else:
			uf[label_v] = label_u
			sz[label_u] += sz[label_v]
N = int(input())
uf = list(range(2 * N + 1))
sz = [1] * (2 * N + 1)
for _ in range(N):
	(u, v) = map(int, input().split())
	Unify(uf, sz, u, v)
sz = [sz[i] for i in range(1, 2 * N + 1) if uf[i] == i and sz[i] > 1]
print(min(sz), max(sz))


def make_set(x):
	parent[x] = x
	rank[x] = 0
	sizes[x] = 1

def find_set(x):
	if x != parent[x]:
		parent[x] = find_set(parent[x])
	return parent[x]

def link(x, y):
	if x == y:
		return
	if rank[x] > rank[y]:
		parent[y] = x
		sizes[x] += sizes[y]
		return
	parent[x] = y
	sizes[y] += sizes[x]
	if rank[x] == rank[y]:
		rank[y] += 1

def union(x, y):
	link(find_set(x), find_set(y))
n = int(input())
parent = [0] * (2 * n)
rank = [0] * (2 * n)
sizes = [0] * (2 * n)
cmax = 0
cmin = n * n
for i in range(len(parent)):
	make_set(i)
for i in range(n):
	els = input().split(' ')
	a = int(els[0])
	b = int(els[1])
	union(a - 1, b - 1)
for i in range(len(parent)):
	reprs = find_set(i)
	if sizes[reprs] > cmax:
		cmax = sizes[reprs]
	if sizes[reprs] < cmin and sizes[reprs] != 1:
		cmin = sizes[reprs]
print(cmin, cmax, sep=' ')


def find(x):
	while uf[x] >= 0:
		if uf[uf[x]] >= 0:
			uf[x] = uf[uf[x]]
		x = uf[x]
	return x
n = int(input())
uf = [-1] * (2 * n)
for i in range(n):
	(x, y) = map(int, input().split())
	(x, y) = (find(x - 1), find(y - 1))
	if x != y:
		if uf[x] > uf[y]:
			(x, y) = (y, x)
		uf[x] += uf[y]
		uf[y] = x
(mn, mx) = (2 * n, 0)
for i in range(2 * n):
	if uf[i] < -1:
		mn = min(mn, -uf[i])
		mx = max(mx, -uf[i])
print(mn, mx)


lookups = {}

def make_set(n):
	lookups[n] = {'key': n, 'next': None}
	n_list = {'size': 1, 'head': lookups[n], 'tail': lookups[n]}
	lookups[n]['overlist'] = n_list

def find_representative(n):
	return lookups[n]['overlist']['head']['key']

def union(m, n):
	if find_representative(m) != find_representative(n):
		m_list = lookups[m]['overlist']
		n_list = lookups[n]['overlist']
		if m_list['size'] > n_list['size']:
			concat_lists(m_list, n_list)
		else:
			concat_lists(n_list, m_list)

def concat_lists(a_list, b_list):
	a_list['size'] = a_list['size'] + b_list['size']
	a_list['tail']['next'] = b_list['head']
	a_list['tail'] = b_list['tail']
	current_node = b_list['head']
	while True:
		current_node['overlist'] = a_list
		if current_node['next'] is None:
			break
		else:
			current_node = current_node['next']
edge_count = int(input())
vertices = set()
for i in range(edge_count):
	(source, target) = map(int, input().split())
	if source not in vertices:
		vertices.add(source)
		make_set(source)
	if target not in vertices:
		vertices.add(target)
		make_set(target)
	union(source, target)
maximum = 0
minimum = edge_count * 100
for vertex in vertices:
	size = lookups[vertex]['overlist']['size']
	if size > maximum:
		maximum = size
	if size < minimum:
		minimum = size
print(' '.join([str(minimum), str(maximum)]))


class Node:

	def __init__(self, val):
		self.value = val
		self.p = self
		self.rank = 0

	def find_represenative(self):
		if self.p.value != self.value:
			self.p = self.p.find_represenative()
		return self.p

	def __str__(self):
		return str(self.value) + str(self.p.value)

class DisjointSet:

	def __init__(self):
		self.values = []
		self.length = []

	def insert(self, val):
		k = Node(val)
		self.values.append(k)
		self.length.append(1)

	def union(self, val1, val2):
		k1 = self.values[val1 - 1]
		k2 = self.values[val2 - 1]
		val1 = k1.find_represenative().value
		val2 = k2.find_represenative().value
		k1 = self.values[val1 - 1]
		k2 = self.values[val2 - 1]
		if k1 == k2:
			return
		if k1.rank < k2.rank:
			k1.p = k2
			self.length[val2 - 1] += self.length[val1 - 1]
			self.length[val1 - 1] = 0
		elif k2.rank < k1.rank:
			k2.p = k1
			self.length[val1 - 1] += self.length[val2 - 1]
			self.length[val2 - 1] = 0
		else:
			k2.p = k1
			self.length[val1 - 1] += self.length[val2 - 1]
			self.length[val2 - 1] = 0
			k1.rank += 1
d = DisjointSet()
N = int(input())
for i in range(1, 2 * N + 1):
	d.insert(i)
for i in range(N):
	(x, y) = map(int, input().split())
	d.union(x, y)
l = list(d.length)
l.sort()
for i in l:
	if i is not 0 and i is not 1:
		print(i, end=' ')
		break
print(l[-1])


class DisjointSet:

	def __init__(self, n):
		self.v = [[k, 1] for k in range(2 * n + 1)]

	def root(self, a):
		st = [a]
		while self.v[st[-1]][0] != st[-1]:
			st.append(self.v[st[-1]][0])
		r = st[-1]
		for x in st:
			self.v[x][0] = r
		return r

	def merge(self, a, b):
		a_root = self.root(a)
		b_root = self.root(b)
		if a_root != b_root:
			self.v[b_root][1] += self.v[a_root][1]
			self.v[a_root][0] = b_root
n = int(input())
g = DisjointSet(n)
for i in range(n):
	(x, y) = map(int, input().split())
	g.merge(x, y)
(m, ma) = (30000, 0)
for k in range(1, n + 1):
	u = g.v[g.root(k)][1]
	if u < m and u > 1:
		m = u
	if u > ma and u > 1:
		ma = u
print(m, ma)


class UFNode(object):

	def __init__(self, v):
		self.val = v
		self.parent = self
		self.rank = 0

class UnionFind(object):

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

	def find(self, x):
		if not isinstance(x, UFNode):
			if x not in self.nodes:
				self.nodes[x] = UFNode(x)
				return self.nodes[x]
			x = self.nodes[x]
		if x.parent != x:
			x.parent = self.find(x.parent)
		return x.parent

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

	def getMaxMin(self):
		max = -1
		min = 99999999999999
		counts = {}
		for node in self.nodes.values():
			root = self.find(node)
			counts[root] = counts.get(root, 0) + 1
		for count in counts.values():
			if count < min and count != 1:
				min = count
			if count > max:
				max = count
		return (min, max)
n = int(input())
uf = UnionFind()
for i in range(n):
	(x, y) = map(int, input().split())
	uf.union(x, y)
print(' '.join(map(str, uf.getMaxMin())))


import sys
sys.setrecursionlimit(100000)

def dfs(current):
	visited[current] = count
	compcount[count] += 1
	for node in adjlist[current]:
		if visited[node] == -1:
			dfs(node)
n = int(input())
adjlist = [list() for x in range(2 * n + 1)]
visited = [-1 for x in range(2 * n + 1)]
compcount = [0 for x in range(2 * n + 1)]
count = -1
for i0 in range(n):
	[u, v] = [int(x) for x in input().split()]
	adjlist[u].append(v)
	adjlist[v].append(u)
for origin in range(1, n + 1):
	if visited[origin] == -1:
		count += 1
		dfs(origin)
outarr = [x for x in compcount if x != 0 and x != 1]
print(min(outarr), max(outarr))


from collections import defaultdict

class Components:

	def __init__(self, graph):
		self.graph = graph
		self.num_vertices = len(graph)
		self.visited = {vertex: False for vertex in graph}

	def breadth_first_search(self, starting_vertex):
		count = 1
		queue = [starting_vertex]
		self.visited[starting_vertex] = True
		while queue:
			vertex = queue.pop(0)
			for adjacent_vertex in self.graph[vertex]:
				if not self.visited[adjacent_vertex]:
					self.visited[adjacent_vertex] = True
					queue.append(adjacent_vertex)
					count += 1
		return count

	def min_max_components(self):
		sizes = {'min_size': float('inf'), 'max_size': 0}
		for vertex in self.graph:
			if not self.visited[vertex]:
				component_size = self.breadth_first_search(vertex)
				if component_size != 1:
					if component_size < sizes['min_size']:
						sizes['min_size'] = component_size
					if component_size > sizes['max_size']:
						sizes['max_size'] = component_size
		return sizes
num = int(input())
graph = defaultdict(list)
for n in range(num):
	(G, B) = [int(x) for x in input().split()]
	graph[G].append(B)
	graph[B].append(G)
components = Components(graph)
sizes = components.min_max_components()
print('%d %d' % (sizes['min_size'], sizes['max_size']))


import collections as c
import random as rnd
import sys

def read(typ=int):
	return typ(sys.stdin.readline().strip())

def read_list(typ=int):
	return list(map(typ, sys.stdin.readline().strip().split(' ')))

def main():
	pass

class Graph(object):

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

	def add_edge(self, s, d):
		self.edges[s].append(d)
		self.edges[d].append(s)

	def neighbors(self, n):
		return self.edges[n]

	@property
	def size(self):
		return len(self.edges)

def bfs(root, g, visited):
	q = [root]
	subg = Graph()
	while len(q):
		cur = q.pop(0)
		if cur in visited:
			continue
		visited.add(cur)
		for nbr in g.neighbors(cur):
			subg.add_edge(cur, nbr)
			q.append(nbr)
	return subg

def find_ccs(g):
	ccs = []
	visited = set()
	for root in g.edges:
		if root in visited:
			continue
		subg = bfs(root, g, visited)
		ccs.append(subg)
	return ccs
n = read(int)
g = Graph()
for _ in range(n):
	(s, d) = read_list(int)
	g.add_edge(s, d)
ccs = find_ccs(g)
mx = max(ccs, key=lambda x: x.size)
mn = min(ccs, key=lambda x: x.size)
print('{} {}'.format(mn.size, mx.size))


class DisjointSet:

	def __init__(self):
		self.members = {}
		self.sizes = {}

	def create_set(self, v):
		self.members[v] = v
		self.sizes[v] = 1

	def merge(self, a, b):
		old_parent = self.find_parent(a)
		new_parent = self.find_parent(b)
		self.members[self.find_parent(a)] = new_parent
		if old_parent != new_parent:
			self.sizes[new_parent] += self.sizes[old_parent]
			self.sizes[old_parent] = 0

	def find_parent(self, v):
		if self.members[v] == v:
			return v
		self.members[v] = self.find_parent(self.members[v])
		return self.members[v]
N = int(input())
ds = DisjointSet()
for i in range(1, 2 * N + 1):
	ds.create_set(i)
for _ in range(N):
	(g, b) = [int(x) for x in input().split()]
	ds.merge(g, b)
maxsize = 0
minsize = 30000
for size in ds.sizes.values():
	if size > maxsize:
		maxsize = size
	if 1 < size < minsize:
		minsize = size
print('{} {}'.format(minsize, maxsize))


parents = {}
weights = {}

def add_item(parents, weights, a):
	if a not in parents:
		parents[a] = a
		weights[a] = 1

def get_item(parents, a):
	path = [a]
	root = parents[a]
	while path[-1] != root:
		path.append(root)
		root = parents[root]
	for ancestor in path:
		parents[ancestor] = root
	return root

def union(parents, weights, a, b):
	root_a = get_item(parents, a)
	root_b = get_item(parents, b)
	if root_a != root_b:
		(light, heavy) = sorted((root_a, root_b))
		if heavy != get_item(parents, heavy):
			print(light)
		parents[light] = parents[heavy]
		weights[heavy] += weights[light]
		weights[light] = None
n = int(input())
for i in range(1, 2 * n + 1):
	add_item(parents, weights, i)
for _ in range(n):
	(a, b) = [int(x) for x in input().strip().split()]
	union(parents, weights, a, b)
print(min((v for v in weights.values() if v is not None and v > 1)), max((v for v in weights.values() if v is not None)))


def find(x):
	while uf[x] >= 0:
		if uf[uf[x]] >= 0:
			uf[x] = uf[uf[x]]
		x = uf[x]
	return x
n = int(input())
uf = [-1] * (2 * n)
for i in range(n):
	(x, y) = map(int, input().split())
	(x, y) = (find(x - 1), find(y - 1))
	if x != y:
		if uf[x] > uf[y]:
			(x, y) = (y, x)
		uf[x] += uf[y]
		uf[y] = x
(mn, mx) = (2 * n, 0)
for i in range(2 * n):
	if uf[i] < -1:
		mn = min(mn, -uf[i])
		mx = max(mx, -uf[i])
print(mn, mx)


class Node:

	def __init__(self, label):
		self.label = label

	def __str__(self):
		return self.label

def MakeSet(x):
	x.parent = x
	x.rank = 0
	x.length = 1

def Find(x):
	if x.parent != x:
		x.parent = Find(x.parent)
	return x.parent

def Union(x, y):
	xRoot = Find(x)
	yRoot = Find(y)
	xLength = xRoot.length
	yLength = yRoot.length
	if xRoot.rank > yRoot.rank:
		yRoot.parent = xRoot
		xRoot.length = xLength + yLength
	elif xRoot.rank < yRoot.rank:
		xRoot.parent = yRoot
		yRoot.length = xLength + yLength
	elif xRoot != yRoot:
		yRoot.parent = xRoot
		xRoot.length = xLength + yLength
		xRoot.rank = xRoot.rank + 1
n = int(input())
graph = []
for i in range(2 * n):
	x = Node(i + 1)
	MakeSet(x)
	graph.append(x)
parents = []
for _ in range(n):
	info = input().split(' ')
	(g, b) = (int(info[0]), int(info[1]))
	Union(graph[g - 1], graph[b - 1])
mini = 1000000
maxi = 2
for y in graph:
	x = Find(y)
	if x.length > 1 and x.length < mini:
		mini = x.length
	if x.length > maxi:
		maxi = x.length
print(mini, maxi)


N = int(input())
(C, CountHash) = ({}, {})
for i in range(N):
	(x, y) = input().strip().split(' ')
	if x not in C:
		C[x] = {}
	if y not in C:
		C[y] = {}
	C[x][y] = True
	C[y][x] = True
CountValues = []

def countSet(node):
	if node in CountHash:
		return CountValues[CountHash[node]]
	CountValues.append(0)
	index = len(CountValues) - 1
	subHistory = {node: True}
	states = [node]
	while len(states) > 0:
		s = states.pop()
		CountValues[index] += 1
		CountHash[s] = index
		for friend in C[s]:
			if friend not in subHistory:
				subHistory[friend] = True
				states.append(friend)
	CountHash[node] = index
	return CountValues[index]
(out1, out2) = (None, None)
for node in C:
	ret = countSet(node)
	if out1 == None:
		out1 = ret
		out2 = ret
	else:
		out1 = min(out1, ret)
		out2 = max(out2, ret)
print(out1, out2)


from sys import stdin

class UnionGraph:

	def __init__(self):
		self.num_edges = int(stdin.readline())
		self.num_nodes = 2 * self.num_edges
		self.parent = [x for x in range(self.num_nodes)]
		self.component_size = [1 for _ in self.parent]
		for _ in range(self.num_edges):
			line = stdin.readline()
			(x, y) = (int(num) - 1 for num in line.split())
			self.merge(x, y)

	def find_min_max_comp(self):
		max_comp_size = 0
		min_comp_size = self.num_nodes
		for idx in range(self.num_nodes):
			if self.parent[idx] == idx and self.component_size[idx] != 1:
				max_comp_size = max(max_comp_size, self.component_size[idx])
				min_comp_size = min(min_comp_size, self.component_size[idx])
		return (min_comp_size, max_comp_size)

	def merge(self, x, y):
		x_comp_root = self.find_comp_root(x)
		y_comp_root = self.find_comp_root(y)
		if x_comp_root != y_comp_root:
			if self.component_size[x_comp_root] < self.component_size[y_comp_root]:
				self.parent[x_comp_root] = y_comp_root
				self.component_size[y_comp_root] += self.component_size[x_comp_root]
			else:
				self.parent[y_comp_root] = x_comp_root
				self.component_size[x_comp_root] += self.component_size[y_comp_root]

	def find_comp_root(self, node):
		if self.parent[node] == node:
			return node
		else:
			return self.find_comp_root(self.parent[node])
my_graph = UnionGraph()
(min_comp, max_comp) = my_graph.find_min_max_comp()
print('{} {}'.format(min_comp, max_comp))


n = int(input())
Node = object

class Node(object):

	def __init__(self, uid) -> None:
		self.uid = uid
		self.parent = uid
		self.size = 1

	def __gt__(self, other: Node) -> bool:
		return self.size > other.size

	def grow(self, other: Node) -> None:
		self.size += other.size

	def update_parent(self, other: Node) -> None:
		self.parent = other.parent

	def is_root(self) -> bool:
		return self.uid == self.parent

class DisjointSetForest(object):

	def __init__(self, node_count):
		self.nodes = self._init_nodes(node_count)

	def __getitem__(self, uid) -> Node:
		return self.nodes[uid - 1]

	def __iter__(self):
		return iter(self.nodes)

	@staticmethod
	def _init_nodes(node_count) -> object:
		nodes = []
		for i in range(1, node_count + 1):
			nodes.append(Node(i))
		return nodes

	def community_size(self, uid):
		return self.root(uid).size

	def root(self, uid: int) -> Node:
		node = self[uid]
		while not node.is_root():
			node = self[self[node.parent].parent]
		return node

	def connect(self, uid_1, uid_2):
		node_i = self.root(uid_1)
		node_j = self.root(uid_2)
		if node_i is not node_j:
			if node_i > node_j:
				self._connect(node_i, node_j)
			else:
				self._connect(node_j, node_i)

	@staticmethod
	def _connect(greater_node: Node, lesser_node: Node):
		greater_node.grow(lesser_node)
		lesser_node.update_parent(greater_node)
forest = DisjointSetForest(2 * n + 1)
for _ in range(n):
	(node_a, node_b) = map(int, input().split())
	forest.connect(node_a, node_b)
max_vertex_count = forest[0].size
min_vertex_count = 300000
for node in forest:
	size = forest.community_size(node.uid)
	if size > max_vertex_count:
		max_vertex_count = size
	if size > 1 and size < min_vertex_count:
		min_vertex_count = size
print('{} {}'.format(min_vertex_count, max_vertex_count))


def union(self, x, y):
	while self.tree[x] > 0:
		x = self.tree[x]
	while self.tree[y] > 0:
		y = self.tree[y]
	if x == y:
		return
	if -self.tree[x] >= -self.tree[y]:
		self.tree[x] += self.tree[y]
		self.tree[y] = x
	else:
		self.tree[y] += self.tree[x]
		self.tree[x] = y

def show(self):
	return self.tree

def init(self, x):
	self.tree = [-1] * x
Disjoint = type('Disjoint', (), {'tree': [], 'init': init, 'union': union, 'show': show})
N = int(input())
d = Disjoint()
d.init(2 * N + 1)
for q in range(N):
	(x, y) = [int(i) for i in input().split()]
	d.union(x, y)
result = d.show()
(small, big) = (2 * N, 1)
for i in range(len(result)):
	if result[i] == -1 or result[i] > 0:
		continue
	small = min(small, -result[i])
	big = max(big, -result[i])
print(small, big)


import sys
import queue

def connected_components(E):
	visited = {}
	smallest = len(E)
	largest = 0
	Q = queue.Queue()
	for vertex in E:
		if vertex in visited:
			continue
		count = 1
		Q.put(vertex)
		visited[vertex] = 1
		while not Q.empty():
			vertex = Q.get()
			for edge in E[vertex]:
				if not edge in visited:
					count += 1
					Q.put(edge)
					visited[edge] = 1
		if smallest > count:
			smallest = count
		if largest < count:
			largest = count
	return (smallest, largest)
N = int(input().split(' ')[0])
E = {}
for i in range(N):
	edge = input().split(' ')
	v = edge[0]
	u = edge[1]
	if not v in E:
		E[v] = []
	if not u in E:
		E[u] = []
	E[v].append(u)
	E[u].append(v)
(smallest, largest) = connected_components(E)
print(smallest, end=' ')
print(largest)


class Node:

	def __init__(self, val):
		self.val = val
		self.edges = []
		self.visited = False
import sys
from queue import Queue
lines = []
for line in sys.stdin:
	lines.append(line.strip())
n = int(lines[0])
G = []
for i in range(1, 2 * n + 1):
	G.append(Node(i))
for line in lines[1:]:
	arr = list(map(lambda x: int(x), line.split(' ')))
	u = arr[0]
	v = arr[1]
	G[u - 1].edges.append(G[v - 1])
	G[v - 1].edges.append(G[u - 1])

def bfs(root):
	q = Queue()
	count = 0
	if not root.visited:
		q.put(root)
		count += 1
		root.visited = True
	while not q.empty():
		node = q.get()
		for e in node.edges:
			if e.visited == False:
				count += 1
				e.visited = True
				q.put(e)
	return count

def graphsize(node):
	if not node:
		return 0
	elif node.visited:
		return 0
	else:
		node.visited = True
		return 1 + sum(list(map(lambda c: graphsize(c), node.edges)))
minsize = None
maxsize = None
for i in range(1, 2 * n + 1):
	dist = bfs(G[i - 1])
	if (not minsize or dist < minsize) and dist > 1:
		minsize = dist
	if (not maxsize or dist > maxsize) and dist > 1:
		maxsize = dist
print(str(minsize) + ' ' + str(maxsize))


def find(x):
	while uf[x] >= 0:
		if uf[uf[x]] >= 0:
			uf[x] = uf[uf[x]]
		x = uf[x]
	return x
n = int(input())
uf = [-1] * (2 * n)
for i in range(n):
	(x, y) = map(int, input().split())
	(x, y) = (find(x - 1), find(y - 1))
	if x != y:
		if uf[x] > uf[y]:
			(x, y) = (y, x)
		uf[x] += uf[y]
		uf[y] = x
(mn, mx) = (2 * n, 0)
for i in range(2 * n):
	if uf[i] < -1:
		mn = min(mn, -uf[i])
		mx = max(mx, -uf[i])
print(mn, mx)


from collections import defaultdict
n = int(input())
A = defaultdict(lambda : [])
for _ in range(n):
	(a, b) = map(int, input().split())
	A[a].append(b)
	A[b].append(a)
low = high = None
U = set(A)
S = set()
for u in U:
	if u not in S:
		i = 0
		V = [u]
		T = set()
		T.add(u)
		while i < len(V):
			v = V[i]
			S.add(v)
			i += 1
			for w in A[v]:
				if w not in T:
					T.add(w)
					V.append(w)
		if low is None or i < low:
			if i == 1:
				print('i', i, 'S', S, 'T', T, 'u', u)
			low = i
		if high is None or i > high:
			high = i
print(low, high)


def find(x):
	while uf[x] >= 0:
		if uf[uf[x]] >= 0:
			uf[x] = uf[uf[x]]
		x = uf[x]
	return x
n = int(input())
uf = [-1] * (2 * n)
for i in range(n):
	(x, y) = map(int, input().split())
	(x, y) = (find(x - 1), find(y - 1))
	if x != y:
		if uf[x] > uf[y]:
			(x, y) = (y, x)
		uf[x] += uf[y]
		uf[y] = x
(mn, mx) = (2 * n, 0)
for i in range(2 * n):
	if uf[i] < -1:
		mn = min(mn, -uf[i])
		mx = max(mx, -uf[i])
print(mn, mx)


class Node:

	def __init__(self):
		self.parent = self
		self.size = 1

	@property
	def rep(self):
		if self.parent == self:
			return self
		self.parent = self.parent.rep
		return self.parent

def merge(node1, node2):
	(rep1, rep2) = (node1.rep, node2.rep)
	if rep1 == rep2:
		return
	if rep1.size <= rep2.size:
		rep1.parent = rep2
		rep2.size += rep1.size
	else:
		rep2.parent = rep1
		rep1.size += rep2.size
N = int(input())
nodes = [Node() for _ in range(2 * N)]
for _ in range(N):
	(G, B) = map(int, input().split(' '))
	merge(nodes[G - 1], nodes[B - 1])
component_sizes = [node.rep.size for node in nodes]
min_size = min([size for size in component_sizes if size > 1])
max_size = max(component_sizes)
print('{} {}'.format(min_size, max_size))


class UF:

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

	def _parent(self, a):
		while self.parent[a] != a:
			self.parent[a] = self.parent[self.parent[a]]
			a = self.parent[a]
		return a

	def _size(self, a):
		return self.size[self._parent(a)]

	def merge(self, a, b):
		(a, b) = (self._parent(a), self._parent(b))
		if a != b:
			if self._size(a) < self._size(b):
				(a, b) = (b, a)
			self.parent[b] = a
			self.size[a] += self.size[b]

	def __repr__(self):
		return self.parent.__str__() + '\n' + self.size.__str__()
T = int(input())
uf = UF(T * 2)
for _ in range(T):
	uf.merge(*map(int, input().split()))
print(min((sz for (node, sz) in zip(range(T * 2 + 1), uf.size) if sz != 1 and node == uf._parent(node))), end=' ')
print(max(uf.size))


def main():
	n = int(input())
	edges = []
	for _ in range(n):
		(G_n, S_n) = [int(x) for x in input().split()]
		edges.append((G_n, S_n))
	(min_len, max_len) = find_connected_components(edges)
	print('{} {}'.format(min_len, max_len))

def find_connected_components(edges):
	disjoint_set = {}

	def parent(node):
		while disjoint_set[node] != node:
			node = disjoint_set[node]
		return node
	for edge in edges:
		(a, b) = edge
		if a in disjoint_set and b in disjoint_set:
			disjoint_set[parent(a)] = parent(b)
		elif a in disjoint_set:
			disjoint_set[b] = parent(a)
		elif b in disjoint_set:
			disjoint_set[a] = parent(b)
		else:
			disjoint_set[a] = a
			disjoint_set[b] = a
	connected_components = {}
	for node in disjoint_set:
		my_parent = parent(node)
		if my_parent in connected_components:
			connected_components[my_parent].append(node)
		else:
			connected_components[my_parent] = [node]
	min_len = 99999999
	max_len = -1
	for dset in connected_components:
		min_len = min(len(connected_components[dset]), min_len)
		max_len = max(len(connected_components[dset]), max_len)
	return (min_len, max_len)
main()


def find(x):
	while uf[x] >= 0:
		if uf[uf[x]] >= 0:
			uf[x] = uf[uf[x]]
		x = uf[x]
	return x
n = int(input())
uf = [-1] * (2 * n)
for i in range(n):
	(x, y) = map(int, input().split())
	(x, y) = (find(x - 1), find(y - 1))
	if x != y:
		if uf[x] > uf[y]:
			(x, y) = (y, x)
		uf[x] += uf[y]
		uf[y] = x
(mn, mx) = (2 * n, 0)
for i in range(2 * n):
	if uf[i] < -1:
		mn = min(mn, -uf[i])
		mx = max(mx, -uf[i])
print(mn, mx)


class Graph:

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

	def adjacents(self, node):
		if node not in self.adjacency_list:
			return []
		return self.adjacency_list[node]

	def add_edge(self, source, destination):
		if source not in self.adjacency_list:
			self.adjacency_list[source] = []
		if destination not in self.adjacency_list:
			self.adjacency_list[destination] = []
		self.adjacency_list[source].append(destination)
		self.adjacency_list[destination].append(source)

	def vertices(self):
		return self.adjacency_list.keys()

def connected_components(graph):
	visited = set()
	cc_by_vertex = {}
	for (cc_id, vertex) in enumerate(graph.vertices()):
		if vertex not in cc_by_vertex:
			dfs(graph, vertex, cc_id, cc_by_vertex)
	return cc_by_vertex

def dfs(graph, source, cc_id, cc_by_vertex):
	visited = set([source])
	frontier = [source]
	while frontier:
		node = frontier.pop()
		cc_by_vertex[node] = cc_id
		for vertex in graph.adjacents(node):
			if vertex in visited:
				continue
			visited.add(vertex)
			frontier.append(vertex)

def group_vertex_by_cc(ccs):
	vertex_by_cc = {}
	for (vertex, cc) in ccs.items():
		if cc not in vertex_by_cc:
			vertex_by_cc[cc] = []
		vertex_by_cc[cc].append(vertex)
	return vertex_by_cc

def min_length(vertex_by_cc):
	return min([len(vertices) for vertices in vertex_by_cc.values()])

def max_length(vertex_by_cc):
	return max([len(vertices) for vertices in vertex_by_cc.values()])
N = int(input())
graph = Graph()
for n in range(N):
	(a, b) = [int(x) for x in input().split()]
	graph.add_edge(a, b)
ccs = connected_components(graph)
vertex_by_cc = group_vertex_by_cc(ccs)
print(min_length(vertex_by_cc), max_length(vertex_by_cc))


class Node:

	def __init__(self, label, neighbors):
		self.visited = False
		self.neighbors = neighbors
		self.label = label
N = int(input().strip())
nodes_map = {}
g = []
b = []
for _ in range(N):
	(node_1, node_2) = [int(i) for i in input().strip().split(' ')]
	g.append(node_1)
	b.append(node_2)

def DFS(cur_node):
	size = 1
	for neighbor in cur_node.neighbors:
		if not neighbor.visited:
			neighbor.visited = True
			size += DFS(neighbor)
	return size

def non_recursive_dfs(cur_node):
	cur_node.visited = True
	size = 1
	nodes_to_visit = cur_node.neighbors
	while len(nodes_to_visit):
		check_node = nodes_to_visit.pop()
		if not check_node.visited:
			check_node.visited = True
			nodes_to_push = []
			ntpl = []
			for neighbor in check_node.neighbors:
				if not neighbor.visited:
					nodes_to_push.append(neighbor)
					ntpl.append(neighbor.label)
			nodes_to_visit[:0] = nodes_to_push
			size += 1
	return size
for label in g:
	nodes_map[label] = Node(label, [])
for label in b:
	nodes_map[label] = Node(label, [])
for (index, label) in enumerate(g):
	b_node = nodes_map[b[index]]
	nodes_map[label].neighbors.append(b_node)
	nodes_map[b[index]].neighbors.append(nodes_map[label])
largest = 0
smallest = None
for label in g:
	cur_node = nodes_map[label]
	size = non_recursive_dfs(cur_node)
	if size != 1:
		if size > largest:
			largest = size
		if smallest is None or size < smallest:
			smallest = size
print('{0} {1}'.format(smallest, largest))


def find_parent(a):
	if a != parent[a]:
		parent[a] = find_parent(parent[a])
		return parent[a]
	else:
		return a
n = int(input())
parent = [i for i in range(2 * n + 1)]
sets_lens = [1 for i in range(2 * n + 1)]
for _ in range(n):
	(a, b) = list(map(lambda a: int(a), input().split()))
	a = find_parent(a)
	b = find_parent(b)
	if a != b:
		if sets_lens[a] > sets_lens[b]:
			parent[b] = a
			sets_lens[a] += sets_lens[b]
			sets_lens[b] = 1
		else:
			parent[a] = b
			sets_lens[b] += sets_lens[a]
			sets_lens[a] = 1
sorted_lens = list(filter(lambda a: a > 1, sorted(sets_lens)))
print(sorted_lens[0], sorted_lens[-1])


import sys
from collections import defaultdict
N = int(sys.stdin.readline().strip())

class Node(object):

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

def find_set(node):
	while node != node.parent:
		node = node.parent
	return node
component = [Node(i) for i in range(2 * N + 1)]
for i in range(N):
	(g, b) = map(int, sys.stdin.readline().strip().split())
	gset = find_set(component[g])
	bset = find_set(component[b])
	if gset != bset:
		if gset.rank < bset.rank:
			gset.parent = bset
		elif gset.rank > bset.rank:
			bset.parent = gset
		else:
			bset.parent = gset
			gset.rank += 1
counts = defaultdict(int)
for i in component[1:]:
	counts[find_set(i)] += 1
print(min(filter(lambda x: x != 1, counts.values())), max(counts.values()))


class UnionSet(object):

	def __init__(self, setSize):
		self.parents = {x: x for x in range(1, setSize + 1)}
		self.size = {x: 1 for x in range(1, setSize + 1)}

	def findRoot(self, x):
		if self.parents[x] == x:
			return x
		return self.findRoot(self.parents[x])

	def getSize(self, x):
		root = self.findRoot(x)
		return self.size[root]

	def sameComponent(self, x, y):
		return self.findRoot(x) == self.findRoot(y)

	def union(self, x, y):
		r1 = self.findRoot(x)
		r2 = self.findRoot(y)
		if r1 == r2:
			return
		if self.size[r1] >= self.size[r2]:
			self.size[r1] += self.size[r2]
			self.parents[r2] = r1
		else:
			self.size[r2] += self.size[r1]
			self.parents[r1] = r2
n = int(input())
unionSet = UnionSet(n * 2)
for _ in range(n):
	(x, y) = [int(x) for x in input().split(' ')]
	unionSet.union(x, y)
smallestSet = float('inf')
largestSet = 0
for i in range(1, n * 2 + 1):
	setLen = unionSet.getSize(i)
	if setLen > 1:
		smallestSet = min(smallestSet, setLen)
		largestSet = max(largestSet, setLen)
print(smallestSet, largestSet)


E = int(input())
nodes = set()
adj_map = {}
for n in range(E):
	edge = [int(x) for x in input().split(' ')]
	if edge[0] not in adj_map.keys():
		adj_map[edge[0]] = set([edge[1]])
	else:
		adj_map[edge[0]].add(edge[1])
	if edge[1] not in adj_map.keys():
		adj_map[edge[1]] = set([edge[0]])
	else:
		adj_map[edge[1]].add(edge[0])
nodes = set(adj_map.keys())
min_components = len(nodes)
max_components = 0
while len(nodes) != 0:
	node = nodes.pop()
	visitable_nodes = set([node])
	to_visit = adj_map[node]
	while len(to_visit) != 0:
		node = to_visit.pop()
		if node not in visitable_nodes:
			to_visit = to_visit.union(adj_map[node])
			visitable_nodes.add(node)
	nodes = nodes.difference(visitable_nodes)
	if len(visitable_nodes) < min_components:
		min_components = len(visitable_nodes)
	if len(visitable_nodes) > max_components:
		max_components = len(visitable_nodes)
print(str(min_components) + ' ' + str(max_components))


class Node:

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

def union(x, y):
	rootx = findSet(x)
	rooty = findSet(y)
	if rootx == rooty:
		return
	if rootx.rank > rooty.rank:
		rooty.par = rootx
		rootx.size += rooty.size
		se.remove(rooty.data)
	else:
		rootx.par = rooty
		if rootx.rank == rooty.rank:
			rooty.rank += 1
		rooty.size += rootx.size
		se.remove(rootx.data)

def findSet(x):
	if x != x.par:
		x.par = findSet(x.par)
	return x.par

def sameComp(x, y):
	return findSet(x) == findSet(y)
n = int(input())
node = []
se = set()
for i in range(2 * n + 1):
	node.append(Node(i))
	se.add(i)
for i in range(n):
	(i, j) = list(map(int, input().split()))
	union(node[i], node[j])
ma = 0
mi = 100000000
for i in se:
	if node[i].size > ma:
		ma = node[i].size
	if node[i].size < mi and node[i].size != 1:
		mi = node[i].size
print(mi, ma)


from collections import defaultdict

def get_graph():
	graph = defaultdict(set)
	for _ in range(int(input())):
		(v1, v2) = [int(s) for s in input().split()]
		graph[v1].add(v2)
		graph[v2].add(v1)
	return graph

def visit_connected_component(graph, starting_point):
	assert graph
	visited = set()
	stack = [starting_point]
	while len(stack) != 0:
		v = stack.pop()
		if v not in visited:
			visited.add(v)
			stack += list(graph[v])
			yield v

def find_min_and_max(graph):
	if len(graph) == 0:
		raise ValueError('Input too short')
	min_size = float('inf')
	max_size = float('-inf')
	visited = set()
	for starting_vertex in graph.keys():
		if starting_vertex not in visited:
			size = 0
			for v in visit_connected_component(graph, starting_vertex):
				size += 1
				visited.add(v)
			min_size = min(min_size, size)
			max_size = max(max_size, size)
	print('{} {}'.format(min_size, max_size))
find_min_and_max(get_graph())


class GraphNode:

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

	def connected_comp_size(self, visited):
		size = 1
		visited[self.id] = True
		for node in self.neighbours:
			if not visited[node.id]:
				size += node.connected_comp_size(visited)
		return size

def connect_nodes(a, b):
	a.neighbours.append(b)
	b.neighbours.append(a)

def min_max_components(n, lower_nodes):
	visited_nodes = [False] * (2 * n + 1)
	min_comp_size = 2 * n
	max_comp_size = 1
	for (iden, node) in lower_nodes.items():
		if visited_nodes[iden]:
			continue
		size = component_size(node, visited_nodes)
		if size == 1:
			continue
		min_comp_size = min(size, min_comp_size)
		max_comp_size = max(size, max_comp_size)
	return (min_comp_size, max_comp_size)

def component_size(start_node, visited):
	stack = [start_node]
	size = 0
	while stack:
		cur = stack.pop()
		if visited[cur.id]:
			continue
		visited[cur.id] = True
		stack += cur.neighbours
		size += 1
	return size
g_nodes = {}
b_nodes = {}
n = int(input())
for ni in range(n):
	(first, second) = [int(i) for i in input().split(' ')]
	if first not in g_nodes:
		g_nodes[first] = GraphNode(first)
	if second not in b_nodes:
		b_nodes[second] = GraphNode(second)
	connect_nodes(g_nodes[first], b_nodes[second])
(min_comp_size, max_comp_size) = min_max_components(n, g_nodes)
print('{} {}'.format(min_comp_size, max_comp_size))


from collections import defaultdict, Counter
N = int(input())
G = defaultdict(set)
for _ in range(N):
	(b, e) = map(int, input().split())
	G[b].add(e)
	G[e].add(b)

def MarkCC(G, start, marks, mark):
	if marks[start]:
		return mark
	stack = [start]
	while stack:
		node = stack.pop()
		marks[node] = mark
		for e in G[node]:
			if not marks[e]:
				stack.append(e)
	return mark + 1
marks = (2 * N + 1) * [0]
mark = 1
for start in range(1, 2 * N + 1):
	mark = MarkCC(G, start, marks, mark)
c = Counter(marks)
minCC = min((el for el in c.values() if el > 1))
maxCC = max((el for el in c.values()))
print(minCC, maxCC)


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)
n = int(input())
edges = []
vert = set()
for i in range(n):
	(a, b) = [int(x) for x in input().split()]
	edges.append((a, b))
	vert.add(a)
	vert.add(b)
uf = UnionFind()
uf.insert_objects(vert)
for e in edges:
	uf.union(e[0], e[1])
s = eval(str(uf))
l = []
for e in s:
	if type(e) == list:
		l.append(len(e))
	else:
		l.append(len(s))
		break
print(min(l), max(l))


class UnionFind:

	def __init__(self):
		self.weights = {}
		self.parents = {}

	def __getitem__(self, object):
		if object not in self.parents:
			self.parents[object] = object
			self.weights[object] = 1
			return object
		path = [object]
		root = self.parents[object]
		while root != path[-1]:
			path.append(root)
			root = self.parents[root]
		for ancestor in path:
			self.parents[ancestor] = root
		return root

	def __iter__(self):
		return iter(self.parents)

	def union(self, *objects):
		roots = [self[x] for x in objects]
		heaviest = max([(self.weights[r], r) for r in roots])[1]
		for r in roots:
			if r != heaviest:
				self.weights[heaviest] += self.weights[r]
				self.parents[r] = heaviest

	def size(self, obj):
		return self.weights[self[obj]]
N = int(input())
u = UnionFind()
for i in range(N):
	u.union(*[int(i) for i in input().split()])
print(min([u.size(i) for i in u.parents.values() if i > 1]), max(u.weights.values()))


def search(node, edge, N, filters):
	size = 0
	queue = []
	queue.append(node)
	history = []
	while len(queue) > 0:
		cur = queue.pop()
		if cur not in history:
			history.append(cur)
			filters.append(cur)
			queue.extend(edge[cur])
			size += 1
		else:
			continue
	return size

def solve(edge, N):
	small = None
	large = None
	filters = []
	for node in edge:
		if node in filters:
			continue
		size = search(node, edge, N, filters)
		if small == None or size < small:
			small = size
		if large == None or size > large:
			large = size
	return (small, large)
edge = {}
N = int(input())
for i in range(N):
	in_data = input().strip()
	in_data = [int(x) for x in in_data.split(' ')]
	if in_data[0] not in edge:
		edge[in_data[0]] = [in_data[1]]
	else:
		edge[in_data[0]].append(in_data[1])
	if in_data[1] not in edge:
		edge[in_data[1]] = [in_data[0]]
	else:
		edge[in_data[1]].append(in_data[0])
(small, large) = solve(edge, N)
print(small, large)


import collections
N = int(input())
edges = collections.OrderedDict()
for i in range(N):
	(G, B) = map(int, input().split(' '))
	if G not in edges:
		edges[G] = set()
	if B not in edges:
		edges[B] = set()
	edges[G].add(B)
	edges[B].add(G)
componentscount = 0
components = collections.OrderedDict()
while len(edges) > 0:
	(node, neighbours) = edges.popitem()
	components[componentscount] = set()
	components[componentscount].add(node)
	components[componentscount] = components[componentscount] | neighbours
	allneighbours = neighbours.copy()
	while len(allneighbours) > 0:
		neighbour = allneighbours.pop()
		if neighbour in edges:
			neighbours = edges.pop(neighbour)
			components[componentscount] = components[componentscount] | neighbours
			allneighbours = allneighbours | neighbours
	componentscount += 1
min = len(components[0])
max = len(components[0])
for i in range(len(components)):
	current = len(components[i])
	if max < current:
		max = current
	if min > current:
		min = current
print(min, max)


from collections import Counter

class Element:

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

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

class Disjoint_Set:

	def __init__(self):
		self.sets = []

	def get_results(self):
		counts = self.get_counts()
		small_list = counts.most_common()[::-1]
		for item in small_list:
			(small_par, count) = item
			if count == 1:
				continue
			else:
				break
		(lar_par, large) = counts.most_common(1)[0]
		return str(count) + ' ' + str(large)

	def get_counts(self):
		for i in range(len(self.sets)):
			self.find_parent(i)
		freq = []
		for item in self.sets:
			freq.append(item.parent)
		counts = Counter(freq)
		return counts

	def make_set(self, N):
		for i in range(1, 2 * N + 1):
			new_item = Element(i)
			self.sets.append(new_item)

	def union(self, num1, num2):
		item1 = self.sets[num1 - 1]
		item2 = self.sets[num2 - 1]
		item1_parent = self.find_parent(item1.parent)
		item2_parent = self.find_parent(item2.parent)
		item1_parent_rank = self.sets[item1_parent - 1].rank
		item2_parent_rank = self.sets[item2_parent - 1].rank
		if item1_parent_rank == item2_parent_rank:
			self.sets[item2_parent - 1].parent = self.sets[item1_parent - 1].parent
			self.sets[item1_parent - 1].rank += 1
		elif item1_parent_rank > item2_parent_rank:
			self.sets[item2_parent - 1].parent = self.sets[item1_parent - 1].parent
		else:
			self.sets[item1_parent - 1].parent = self.sets[item2_parent - 1].parent

	def find_parent(self, num):
		if self.sets[num - 1].parent == num:
			return num
		else:
			parent = self.find_parent(self.sets[num - 1].parent)
			self.sets[num - 1].parent = parent
			return parent
N = int(input().strip())
set1 = Disjoint_Set()
set1.make_set(N)
for i in range(N):
	(G, B) = (int(temp) for temp in input().strip().split(' '))
	set1.union(G, B)
print(set1.get_results())


import sys
sys.setrecursionlimit(16000)
rep = {}

def parent(v):
	if v == rep[v]:
		return v
	rep[v] = parent(rep[v])
	return rep[v]
N = int(input())
for n in range(0, N):
	(g, b) = map(int, input().split(' '))
	if g not in rep:
		rep[g] = g
	if b not in rep:
		rep[b] = b
	rep[parent(g)] = parent(b)
from collections import defaultdict
rep_ = defaultdict(int)
for (k, v) in rep.items():
	rep_[parent(v)] += 1
lengths = [v for (k, v) in rep_.items()]
print('%d %d' % (min(lengths), max(lengths)))


class Communities:

	def __init__(self, n):
		self.comm = {x: x for x in range(1, n + 1)}
		self.commsz = {x: 1 for x in range(1, n + 1)}
		self.n = n

	def community(self, a):
		comm = self.comm
		updates = []
		it = a
		while it != comm.get(it, it):
			updates.append(it)
			it = comm.get(it, it)
		for node in updates:
			comm[node] = it
		return it

	def size(self, a):
		return self.commsz[self.community(a)]

	def merge(self, a, b):
		(commsz, comm) = (self.commsz, self.comm)
		(commA, commB) = (self.community(a), self.community(b))
		if commA == commB:
			return
		(big, small) = (commA, commB) if self.size(a) > self.size(b) else (commB, commA)
		comm[small] = big
		commsz[big] += commsz[small]
		commsz[small] = 0

	def communities(self):
		return {x: self.size(x) for x in self.commsz if self.commsz[x] > 1}
n = int(input())
C = Communities(2 * n)
import pprint
for _ in range(n):
	(a, b) = list(map(int, input().split()))
	C.merge(a, b)
comms = C.communities().values()
print(min(comms), max(comms))


from collections import deque
graph = {}

def addNode(a, b):
	if a in graph:
		graph[a] += [b]
	else:
		graph[a] = [b]
for _ in range(int(input())):
	(a, b) = map(int, input().split(' '))
	addNode(a, b)
	addNode(b, a)
setList = []
visited = set()

def createSet(node):
	newSet = set()
	q = deque()
	q.append(node)
	while 0 != len(q):
		current = q.popleft()
		if current not in visited:
			newSet.add(current)
			visited.add(current)
			for child in graph[current]:
				if child not in visited:
					q.append(child)
	return newSet
for node in graph:
	if node not in visited:
		s = createSet(node)
		setList.append(s)
minS = maxS = None
for s in setList:
	if minS == None or len(s) < minS:
		minS = len(s)
	if maxS == None or len(s) > maxS:
		maxS = len(s)
print(minS, maxS)


def create_graph():
	n = int(input())
	graph = {i + 1: [] for i in range(2 * n)}
	for nth in range(n):
		(g, b) = map(int, input().split(' '))
		graph[g].append(b)
		graph[b].append(g)
	return graph

def component_items(graph, node_i, visited):
	to_visit = [node_i]
	while to_visit:
		visiting = to_visit.pop()
		yield visiting
		visited.add(visiting)
		neighbors = set(graph[visiting])
		to_visit.extend(neighbors - visited)
graph = create_graph()
to_try = set(graph.keys())
components = []
while to_try:
	trying_from = to_try.pop()
	component = set(component_items(graph, trying_from, set()))
	components.append(component)
	to_try -= component
print(min(filter(lambda _: _ > 1, map(len, components))), max(map(len, components)))


from collections import defaultdict

class UnionFind:

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

	def union(self, x, y):
		xr = self.find(x)
		yr = self.find(y)
		if xr == yr:
			return
		if self.rank[xr] < self.rank[yr]:
			self.parent[xr] = yr
		elif self.rank[xr] > self.rank[yr]:
			self.parent[yr] = xr
		else:
			self.parent[yr] = xr
			self.rank[xr] += 1

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

	def sets(self):
		parents = defaultdict(set)
		for val in range(len(self.parent)):
			par = self.find(val)
			parents[par].add(val)
		return parents.values()
n = int(input())
d = UnionFind(2 * n)
for i in range(n):
	(a, b) = map(int, input().split())
	d.union(a - 1, b - 1)
sets = list(map(len, list(d.sets())))
low = min([i for i in sets if i > 1])
high = max(sets)
print(low, high)


class UF:

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

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

	def union(self, x, y):
		i = self.find(x)
		j = self.find(y)
		if i == j:
			return
		elif self.sz[i] <= self.sz[j]:
			self.id[i] = j
			self.sz[j] += self.sz[i]
		else:
			self.id[j] = i
			self.sz[i] += self.sz[j]

	def printCompo(self):
		roots = [self.find(x) for x in range(len(self.id))]
		print(min((self.sz[root] for root in roots if self.sz[root] != 1)), end=' ')
		print(max((self.sz[root] for root in roots if self.sz[root] != 1)))
		return
n = int(input())
uf = UF(2 * n)
for _ in range(n):
	(u, v) = [int(x) for x in input().strip().split()]
	uf.union(u - 1, v - 1)
uf.printCompo()


class Node:

	def __init__(self, i):
		self.nid = i
		self.p = self
		self.rank = 0
		self.size = 1

	def union(self, other):
		xroot = self.find()
		yroot = other.find()
		if xroot == yroot:
			return
		if xroot.rank > yroot.rank:
			(xroot, yroot) = (yroot, xroot)
		xroot.p = yroot
		yroot.size += xroot.size
		if xroot.rank == yroot.rank:
			yroot.rank += 1

	def find(self):
		if self.p != self:
			self.p = self.p.find()
		return self.p

	def __str__(self):
		return '{}({}/{})'.format(self.nid, self.rank, self.size)
nodes = {}

def node(i):
	if i not in nodes:
		nodes[i] = Node(i)
	return nodes[i]
n = int(input().strip())
for _ in range(n):
	(g, b) = input().strip().split(' ')
	node(g).union(node(b))
sizes = set((n.find().size for n in nodes.values()))
print(min(sizes), max(sizes))


import sys
sys.setrecursionlimit(15000)

class disjoint_set:

	def __init__(self, data):
		self.data = data
		self.parent = self
		self.rank = 0
		self.count = 1

	def find(self):
		if self.parent != self:
			self.parent = self.parent.find()
		return self.parent

	def union(self, other):
		aRoot = self.find()
		bRoot = other.find()
		if aRoot == bRoot:
			return
		if aRoot.rank < bRoot.rank:
			aRoot.parent = bRoot
			bRoot.count += aRoot.count
		elif aRoot.rank > bRoot.rank:
			bRoot.parent = aRoot
			aRoot.count += bRoot.count
		else:
			bRoot.parent = aRoot
			aRoot.count += bRoot.count
			bRoot.rank += 1
n = int(input())
nodes = [None] * (2 * n + 1)
for i in range(1, 2 * n + 1):
	nodes[i] = disjoint_set(i)
for iQ in range(n):
	(a, b) = [int(iStr) for iStr in input().strip().split()]
	nodes[a].union(nodes[b])
minCount = 2 * n
maxCount = 0
for i in range(1, 2 * n + 1):
	thisCount = nodes[i].find().count
	if thisCount < minCount and thisCount != 1:
		minCount = thisCount
	if thisCount > maxCount:
		maxCount = thisCount
print(minCount, maxCount)


def scc_sizes(edges):
	vertices = set(edges.keys())
	while vertices:
		(queue, count) = ([vertices.pop()], 0)
		while queue:
			count += 1
			vertex = queue.pop()
			for v in edges[vertex]:
				if v in vertices:
					vertices.remove(v)
					queue.append(v)
		yield count
numedges = int(input())
edges = {}
for _ in range(numedges):
	(x, y) = input().split()
	edges.setdefault(x, []).append(y)
	edges.setdefault(y, []).append(x)
sccs = sorted(list(scc_sizes(edges)))
print(sccs[0], sccs[-1])


import time
import random
n = int(input().strip())
d = [0] * (2 * n + 1)
s = []
for x in range(n):
	(a, b) = map(int, input().strip().split(' '))
	s.append([a, b])
	if d[a] == 0 and d[b] == 0:
		tmp = a
	elif d[a] == 0:
		tmp = min(a, d[b])
	elif d[b] == 0:
		tmp = min(a, d[a])
	else:
		tmp = min(a, d[a], d[b])
	d[a] = tmp
	d[b] = tmp
s = sorted(s, key=lambda x: (x[0], x[1]))
l = len(s)
c = 1
while c > 0:
	c = 0
	for x in range(l):
		if d[s[x][0]] != d[s[x][1]]:
			tmp = min(s[x][0], d[s[x][0]], d[s[x][1]])
			d[s[x][0]] = tmp
			d[s[x][1]] = tmp
			c = 1
			for i in range(x - 1, -1, -1):
				if s[i][0] == s[x][0]:
					d[s[i][0]] = tmp
					d[s[i][1]] = tmp
				else:
					break
c = {}
for x in d:
	if x != 0:
		try:
			c[x] += 1
		except KeyError:
			c[x] = 1
print(min(c.values()), max(c.values()))


from collections import deque

class Vertex:

	def __init__(self, id):
		self.id = id
		self.links = set()

class Graph:

	def __init__(self, directed=False):
		self.vertices = {}
		self.directed = directed

	def add(self, id1, id2):
		if id1 not in self.vertices:
			self.vertices[id1] = Vertex(id1)
		if id2 not in self.vertices:
			self.vertices[id2] = Vertex(id2)
		self.vertices[id1].links.add(self.vertices[id2].id)
		self.vertices[id2].links.add(self.vertices[id1].id)

	def bfs(self, root):
		visited = set()
		queue = deque()
		parents = {}
		if not graph.vertices:
			return
		vertex = self.vertices[root or 0]
		parents[vertex.id] = None
		queue.append(vertex)
		while queue:
			vertex = queue.pop()
			visited.add(vertex)
			for vid in vertex.links:
				adj = self.vertices[vid]
				if adj not in visited:
					visited.add(adj)
					queue.appendleft(adj)
					parents[adj.id] = vertex.id
		return parents
import sys
graph = Graph()
for _ in range(int(input().strip())):
	(a, b) = [int(v) for v in input().strip().split()]
	graph.add(a, b)
toprocess = set(graph.vertices)
mins = sys.maxsize
maxs = 0
while toprocess:
	parents = graph.bfs(toprocess.pop())
	N = len(parents)
	mins = min(mins, N)
	maxs = max(maxs, N)
	toprocess.difference_update(parents)
print('%d %d' % (mins, maxs))


def find(idxs, i):
	j = i
	while idxs[j] != j:
		j = idxs[j]
	while idxs[i] != j:
		(i, idxs[i]) = (idxs[i], j)
	return j
n = int(input())
sizes = (2 * n + 1) * [1]
sizes[0] = 0
idxs = list(range(2 * n + 1))
for _ in range(n):
	(i, j) = map(int, input().strip().split())
	idx = find(idxs, i)
	jdx = find(idxs, j)
	if idx != jdx:
		sizes[idx] += sizes[jdx]
		idxs[jdx] = idx
sizes = [sizes[i] for i in idxs if idxs[i] == i and sizes[i] > 1]
print(min(sizes), max(sizes))


class DSU:

	def __init__(self, n):
		self.n = n
		self.parent = [-1 for i in range(n)]
		self.rank = [0 for i in range(n)]
		self.count = [1 for i in range(n)]

	def set_count(self, u):
		u_root = self.find(u)
		return self.count[u_root]

	def find(self, u):
		if self.parent[u] == -1:
			return u
		v = self.find(self.parent[u])
		self.parent[u] = v
		self.count[u] = self.count[v]
		return self.parent[u]

	def union(self, u, v):
		u_root = self.find(u)
		v_root = self.find(v)
		if u_root == v_root:
			return
		if self.rank[u_root] > self.rank[v_root]:
			self.parent[v_root] = u_root
			self.count[u_root] += self.count[v_root]
		elif self.rank[u_root] < self.rank[v_root]:
			self.parent[u_root] = v_root
			self.count[v_root] += self.count[u_root]
		else:
			self.parent[v_root] = u_root
			self.count[u_root] += self.count[v_root]
			self.rank[u_root] += 1

def read(type=int):
	return type(input())

def read_arr(type=int):
	return [type(token) for token in input().split()]
n = read()
dsu = DSU(2 * n)
for i in range(n):
	(r, g) = read_arr()
	dsu.union(r - 1, g - 1)
size_map = {}
min_size = 2 * n + 1
max_size = 0
for i in range(2 * n):
	root = dsu.find(i)
	cnt = dsu.set_count(root)
	if cnt > 1:
		min_size = min(cnt, min_size)
		max_size = max(cnt, max_size)
print(min_size, max_size)


class Node(object):

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

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

	def set_root(self, root):
		if not self.parent:
			self.parent = root
		else:
			self.parent.set_root(root)

def count(l, key):
	ret = []
	pre = None
	c = 0
	for i in l:
		ki = key(i)
		if ki == pre:
			c += 1
		else:
			ret.append(c)
			c = 1
			pre = ki
	ret.append(c)
	return ret[1:]
N = int(input().strip())
network = [Node() for _ in range(2 * N)]
for _ in range(N):
	(a, b) = map(int, input().strip().split())
	(a, b) = (a - 1, b - 1)
	a_root = network[a].get_root()
	b_root = network[b].get_root()
	if a_root.rank > b_root.rank:
		b_root.set_root(a_root)
		a_root.size += b_root.size
	elif a_root.rank < b_root.rank:
		a_root.set_root(b_root)
		b_root.size += a_root.size
	elif a_root != b_root:
		b_root.set_root(a_root)
		a_root.rank += 1
		a_root.size += b_root.size
min_size = max_size = None
for i in range(N):
	s = network[i].get_root().size
	if s != 1:
		if min_size is None:
			min_size = max_size = s
		else:
			min_size = min(min_size, s)
			max_size = max(max_size, s)
if min_size is not None:
	print(min_size, max_size)


N = int(input().strip())
candidates = set()

class QuickUnion:

	def __init__(self, size):
		self.N = size
		self.arr = []
		self.sizes = []
		for i in range(size):
			self.arr.append(i)
			self.sizes.append(1)

	def root(self, index):
		while index != self.arr[index]:
			self.arr[index] = self.arr[self.arr[index]]
			index = self.arr[index]
		return index

	def union(self, p, q):
		i = self.root(p)
		j = self.root(q)
		if p == q or i == j:
			return
		if self.sizes[i] < self.sizes[j]:
			self.arr[i] = j
			self.sizes[j] += self.sizes[i]
		else:
			self.arr[j] = i
			self.sizes[i] += self.sizes[j]

	def connected(self, p, q):
		return self.root(p) == self.root(q)

	def count(self, index):
		return self.sizes[self.root(index)]
q = QuickUnion(2 * N)
for i in range(N):
	(u, v) = input().strip().split(' ')
	(u, v) = [int(u) - 1, int(v) - 1]
	candidates.add(u)
	candidates.add(v)
	q.union(u, v)
(minimum, maximum) = [2 * N, 1]
for i in range(2 * N):
	if i not in candidates:
		continue
	c = q.count(i)
	(minimum, maximum) = [min(minimum, c), max(maximum, c)]
print(minimum, maximum)


N = int(input())

class Node:
	__slots__ = ['nodenumber', 'children', 'lijst_subtree']

	def __init__(self, nodenumber):
		self.nodenumber = nodenumber
		self.children = dict()
		self.lijst_subtree = list()

class Solution:

	def createNode(self, nodenumber):
		root = Node(nodenumber)
		return root

	def add(self, Tree, root, node):
		root.children[node.nodenumber] = Node(node)
		node.children[root.nodenumber] = Node(root)

	def subtrees(self, root, Tree, lijst_subtree=dict(), curr=dict()):
		curr[root.nodenumber] = None
		if root.children:
			for child in root.children:
				if child in curr:
					continue
				Tree[child].children.pop(root.nodenumber)
				lijst_subtree[child] = None
				lijst_subtree = self.subtrees(Tree[child], Tree, lijst_subtree, curr)
				Tree[child].children[root.nodenumber] = root
			lijst_subtree[root.nodenumber] = None
			return lijst_subtree
		lijst_subtree[root.nodenumber] = None
		return lijst_subtree

	def components(self, Tree):
		(ma, mi) = (0, 15001)
		while Tree:
			i = list(Tree)[0]
			lijst = self.subtrees(Tree[i], Tree, {i: None})
			aantal = len(lijst)
			if aantal > ma:
				ma = aantal
			if aantal < mi:
				mi = aantal
			for elem in lijst:
				Tree.pop(elem)
		print(mi, ma)
Tree = dict()
edgelijst = []
solution = Solution()
import sys
sys.setrecursionlimit(1000000)
for k in range(N):
	edge = list(map(int, input().strip().split()))
	(i, j) = edge
	Tree.setdefault(i, solution.createNode(i))
	Tree.setdefault(j, solution.createNode(j))
	solution.add(Tree, Tree[i], Tree[j])
solution.components(Tree)


class DisjointSetNode:

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

	def setParent(self, parentNode):
		self.parent = parentNode

	def getParent(self):
		return self.parent

	def getData(self):
		return self.data

	def getRank(self):
		return self.rank

class DisjointSet:

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

	def getParent(self, data):
		if data in self.disjointSetNodeMap:
			return self.disjointSetNodeMap[data].getParent()
		else:
			return None

	def makeSet(self, data):
		if data in self.disjointSetNodeMap:
			return False
		node = DisjointSetNode(data)
		node.setParent(node)
		self.disjointSetNodeMap[data] = node

	def union(self, data1, data2):
		parent1 = self.findSet(data1)
		parent2 = self.findSet(data2)
		if parent1 == parent2:
			return False
		if parent1.getRank() >= parent2.getRank():
			if parent1.getRank() == parent2.getRank():
				parent1.rank += 1
			parent2.parent = parent1
		else:
			parent1.parent = parent2
		return True

	def findSet(self, data):
		disjointSetNode = self.disjointSetNodeMap[data]
		if disjointSetNode.getParent() is disjointSetNode:
			return disjointSetNode
		disjointSetNode.parent = self.findSet(disjointSetNode.getParent().getData())
		return disjointSetNode.parent
edgeCount = int(input().strip())
vertexSet = set()
disJointSet = DisjointSet()
for _ in range(edgeCount):
	(sVertex, eVertex) = input().strip().split(' ')
	(sVertex, eVertex) = (int(sVertex), int(eVertex))
	vertexSet.add(sVertex)
	vertexSet.add(eVertex)
	disJointSet.makeSet(sVertex)
	disJointSet.makeSet(eVertex)
	disJointSet.union(sVertex, eVertex)
connectedComponentCountMap = {}
for iValue in vertexSet:
	if disJointSet.findSet(iValue).getData() in connectedComponentCountMap:
		connectedComponentCountMap[disJointSet.findSet(iValue).getData()] = connectedComponentCountMap[disJointSet.findSet(iValue).getData()] + 1
	else:
		connectedComponentCountMap[disJointSet.findSet(iValue).getData()] = 1
tempList = list(connectedComponentCountMap.values())
minCount = tempList[0]
maxCount = tempList[0]
for (key, value) in connectedComponentCountMap.items():
	if maxCount < value:
		minCount = maxCount
		maxCount = value
	if minCount > value:
		minCount = value
print(minCount, end=' ')
print(maxCount)


import sys
from collections import deque
n = int(input().strip())
if not 1 <= n <= 15000:
	raise Exception
nodes = [None] * ((n + 1) * 2)
for _ in range(n):
	(gi, bi) = input().strip().split()
	(gi, bi) = (int(gi), int(bi))
	if 1 <= gi <= n:
		if nodes[gi] is None:
			nodes[gi] = []
		nodes[gi].append(bi)
	else:
		raise Exception
	if n + 1 <= bi <= 2 * n:
		if nodes[bi] is None:
			nodes[bi] = []
		nodes[bi].append(gi)

class MinMaxVisitor:

	def __init__(self, g):
		self.g = g
		self.counts = [0] * len(g)
		self.visited = set()
		self.min = float('inf')
		self.max = 2
		i = 0
		for ni in range(len(self.g)):
			if self.g[ni] is not None:
				if ni not in self.visited:
					self.visit(ni, i)
					if 2 <= self.counts[i] < self.min:
						self.min = self.counts[i]
					if self.counts[i] > self.max:
						self.max = self.counts[i]
					i += 1

	def visit(self, ni, i):
		if type(self.g[ni]) != list:
			raise Exception('Invalid node {}'.format(ni))
		stack = deque([ni])
		while stack:
			j = stack.pop()
			self.counts[i] += 1
			self.visited.add(j)
			for k in self.g[j]:
				if k not in self.visited:
					self.visited.add(k)
					stack.append(k)
v = MinMaxVisitor(nodes)
print('{} {}'.format(v.min, v.max))


n = int(input())
array = [-1 for i in range(2 * n + 1)]
disjoint_set = []
for i in range(n):
	(p, q) = [int(x) for x in input().strip().split(' ')]
	if array[p] == -1 and array[q] == -1:
		disjoint_set.append([p, q])
		array[p] = len(disjoint_set) - 1
		array[q] = len(disjoint_set) - 1
	elif array[p] == -1:
		disjoint_set[array[q]].append(p)
		array[p] = array[q]
	elif array[q] == -1:
		disjoint_set[array[p]].append(q)
		array[q] = array[p]
	elif array[p] != array[q]:
		if array[p] < array[q]:
			disjoint_set[array[p]] += disjoint_set[array[q]]
			tmp = array[q]
			for i in disjoint_set[array[q]]:
				array[i] = array[p]
			disjoint_set[tmp] = []
		elif array[q] < array[p]:
			disjoint_set[array[q]] += disjoint_set[array[p]]
			tmp = array[p]
			for i in disjoint_set[array[p]]:
				array[i] = array[q]
			disjoint_set[tmp] = []
minset = 2 * n
maxset = 0
for i in disjoint_set:
	if i != []:
		minset = min(minset, len(i))
		maxset = max(maxset, len(i))
print(minset, maxset)


import fileinput

class DisjointSet:

	def __init__(self):
		self.leader = {}
		self.group = {}

	def add(self, a, b):
		leadera = self.leader.get(a)
		leaderb = self.leader.get(b)
		if leadera is not None:
			if leaderb is not None:
				if leadera == leaderb:
					return
				groupa = self.group[leadera]
				groupb = self.group[leaderb]
				if len(groupa) < len(groupb):
					(a, leadera, groupa, b, leaderb, groupb) = (b, leaderb, groupb, a, leadera, groupa)
				groupa |= groupb
				del self.group[leaderb]
				for k in groupb:
					self.leader[k] = leadera
			else:
				self.group[leadera].add(b)
				self.leader[b] = leadera
		elif leaderb is not None:
			self.group[leaderb].add(a)
			self.leader[a] = leaderb
		else:
			self.leader[a] = self.leader[b] = a
			self.group[a] = set([a, b])
ds = DisjointSet()
for line in fileinput.input():
	line = line.strip()
	columns = line.split()
	if len(columns) == 1:
		for i in range(2 * int(columns[0])):
			ds.add(i + 1, i + 1)
	else:
		ds.add(int(columns[0]), int(columns[1]))
x = [len(ds.group[ds.leader.get(y)]) for y in ds.leader]
while 1 in x:
	y = x.remove(1)
print(min(x), max(x))


class Graph:

	def __init__(self):
		self.nodes = set()

	def in_graph(self, node):
		return node in self.nodes

	def add_node(self, node):
		self.nodes.add(node)

	def len(self):
		return len(self.nodes)

	def merge(self, g2, nodes):
		self.nodes = self.nodes | g2.nodes
		for node in g2.nodes:
			nodes[node] = self

	def __repr__(self):
		return ''
num_edges = int(input().strip())
nodes = dict()
for i in range(0, num_edges):
	(n1, n2) = [int(x) for x in input().strip().split(' ')]
	if n1 in nodes and n2 in nodes:
		if nodes[n1] != nodes[n2]:
			nodes[n1].merge(nodes[n2], nodes)
		continue
	if n1 in nodes:
		nodes[n1].add_node(n2)
		nodes[n2] = nodes[n1]
	elif n2 in nodes:
		nodes[n2].add_node(n1)
		nodes[n1] = nodes[n2]
	else:
		g = Graph()
		g.add_node(n1)
		g.add_node(n2)
		nodes[n1] = g
		nodes[n2] = g
graphs = set(nodes.values())
min_size = 20000
max_size = 0
for graph in graphs:
	if graph.len() < min_size and graph.len() > 1:
		min_size = graph.len()
	if graph.len() > max_size:
		max_size = graph.len()
print('{} {}'.format(min_size, max_size))


def find(sets, x):
	if sets[x][0] != x:
		sets[x][0] = find(sets, sets[x][0])
	return sets[x][0]

def union(sets, x, y):
	xRoot = find(sets, x)
	yRoot = find(sets, y)
	if xRoot == yRoot:
		return
	if sets[xRoot][1] < sets[yRoot][1]:
		sets[xRoot][0] = sets[yRoot][0]
		sets[yRoot][2] += sets[xRoot][2]
	elif sets[xRoot][1] > sets[yRoot][1]:
		sets[yRoot][0] = sets[xRoot][0]
		sets[xRoot][2] += sets[yRoot][2]
	else:
		sets[yRoot][0] = sets[xRoot][0]
		sets[xRoot][1] += 1
		sets[xRoot][2] += sets[yRoot][2]
N = int(input())
sets = [[i, 0, 1] for i in range(2 * N)]
for i in range(N):
	(G, B) = map(int, input().split(' '))
	union(sets, G - 1, B - 1)
mini = maxi = None
for i in range(len(sets)):
	curSize = sets[find(sets, i)][2]
	if curSize > 1:
		if mini == None or mini > curSize:
			mini = curSize
		if maxi == None or maxi < curSize:
			maxi = curSize
print(mini, maxi)


from collections import deque

class graph:

	def __init__(self, N):
		self.neighbours = [set() for _ in range(2 * N + 1)]
		self.vertices = set()

	def addEdge(self, G_i, B_i):
		if G_i == B_i:
			return
		self.neighbours[G_i].add(B_i)
		self.neighbours[B_i].add(G_i)
		self.vertices.add(G_i)
		self.vertices.add(B_i)

	def components(self):
		min_component = float('inf')
		max_component = -float('inf')
		visited = set()
		while len(self.vertices) > 0:
			v = self.vertices.pop()
			if v not in visited:
				component = 0
				fringe = deque()
				visited.add(v)
				fringe.appendleft(v)
				while len(fringe) > 0:
					w = fringe.pop()
					component += 1
					for n in self.neighbours[w]:
						if n not in visited:
							visited.add(n)
							fringe.appendleft(n)
				if component < min_component:
					min_component = component
				if component > max_component:
					max_component = component
		return (min_component, max_component)
N = int(input().strip())
G = graph(N)
for _ in range(N):
	(G_i, B_i) = [int(tmp) for tmp in input().strip().split(' ')]
	G.addEdge(G_i, B_i)
(min_component, max_component) = G.components()
print('%d %d' % (min_component, max_component))


class Disjoint(object):

	def __init__(self, n):
		n = 2 * n
		self.nodes = [i for i in range(n + 1)]
		self.size = [1] * (n + 1)

	def __repr__(self):
		return ' '.join((str(i) for i in self.nodes[1:]))

	def printSize(self):
		return self.size[1:]

	def getSize(self, a):
		while self.nodes[a] != a:
			a = self.nodes[a]
		return self.size[a]

	def getBigger(self, a, b):
		if self.getSize(a) < self.getSize(b):
			return (b, a)
		return (a, b)

	def add(self, a, b):
		(a, b) = self.getBigger(a, b)
		while self.nodes[a] != a:
			a = self.nodes[a]
		while self.nodes[b] != b:
			temp = b
			b = self.nodes[b]
			self.nodes[temp] = a
		if not b == a:
			self.nodes[b] = a
			self.size[a] += self.size[b]
			self.size[b] = 1

	def getSmallLarge(self):
		temp = list(filter(lambda x: x != 1, self.size))
		return (min(temp), max(temp))

def process_query(s, q):
	(n, g) = map(int, q.split(' '))
	s.add(n, g)
n = int(input().strip())
s = Disjoint(n)
for _ in range(n):
	query = input().strip()
	process_query(s, query)
print('{} {}'.format(*s.getSmallLarge()))


from collections import Counter
n = int(input())
p = [i for i in range(2 * n + 1)]
size = [1 for _ in range(2 * n + 1)]

def union(i, j):
	(i, j) = (find(i), find(j))
	if size[i] < size[j]:
		p[i] = j
		size[j] += size[i]
	else:
		p[j] = i
		size[i] += size[j]

def find(i):
	while p[i] != i:
		p[i] = p[p[i]]
		i = p[i]
	return i
for _ in range(n):
	(i, j) = list(map(int, input().split()))
	union(i, j)
for i in range(len(p)):
	p[i] = find(i)
counts = Counter(p)
(least, most) = (float('inf'), 0)
for c in counts.values():
	if c > 1:
		least = min(least, c)
		most = max(most, c)
print('{} {}'.format(least, most))


class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			self.total[a_parent] += self.total[b_parent]

	def find(self, a):
		parents = [a]
		while self.parent[a] != a:
			a = self.parent[a]
			parents.append(a)
		for x in parents[:-1]:
			self.parent[x] = parents[-1]
		return parents[-1]

	def get_total(self, a):
		return self.total[self.find(a)]
N = int(input())
ds = DisjointSet(2 * N)
for i in range(N):
	(G, B) = map(int, input().split())
	ds.union(G - 1, B - 1)
set_size = [ds.get_total(i) for i in range(2 * N) if ds.get_total(i) != 1]
print(min(set_size), max(set_size))


n = int(input())
lst = [[] for _ in range(2 * n)]
visit = [1 for _ in range(2 * n)]
q = []
for _ in range(n):
	(g, b) = map(int, input().split())
	g -= 1
	b -= 1
	if b not in lst[g]:
		lst[g].append(b)
		visit[g] = 0
		q.append(g)
	if g not in lst[b]:
		lst[b].append(g)
		visit[b] = 0
min_len = 2 * n
max_len = 0
for el in range(len(q)):
	if visit[el] == 1:
		continue
	count = 1
	curr_q = [el]
	visit[el] = 1
	while curr_q:
		parent = curr_q.pop(0)
		for child in lst[parent]:
			lst[child].remove(parent)
			if visit[child] == 0:
				count += 1
				curr_q.append(child)
				visit[child] = 1
	if count < min_len:
		min_len = count
	if count > max_len:
		max_len = count
print(min_len, max_len)


Graph = {}
for _ in range(int(input())):
	(g, b) = map(int, input().split())
	if g not in Graph:
		Graph[g] = {g}
	if b not in Graph:
		Graph[b] = {b}
	if len(Graph[g]) > len(Graph[b]):
		Graph[g].update(Graph[b])
		for u in Graph[b]:
			Graph[u] = Graph[g]
	else:
		Graph[b].update(Graph[g])
		for u in Graph[g]:
			Graph[u] = Graph[b]
print(min((len(g) for g in Graph.values())), max((len(g) for g in Graph.values())))


class Queue:

	def __init__(self):
		self.data = []
		self.size = 0

	def queue(self, item):
		self.data = [item] + self.data
		self.size += 1

	def dequeue(self):
		removed_item = self.data[-1]
		self.data = self.data[:-1]
		self.size -= 1
		return removed_item

	def empty(self):
		return self.size == 0

	def display(self):
		print(list(reversed(self.data)))

def initialise_adjacency_list_if_needed(graph, v1, v2):
	if v1 not in graph:
		graph[v1] = []
	if v2 not in graph:
		graph[v2] = []

def BFS_with_visited_count(graph, start, visited_node_flags):
	q = Queue()
	q.queue(start)
	visited_count = 1
	while not q.empty():
		cur = q.dequeue()
		visited_node_flags[cur] = 1
		if len(graph[cur]) == 0:
			continue
		for adjacentNode in graph[cur]:
			if visited_node_flags[adjacentNode]:
				continue
			q.queue(adjacentNode)
			visited_count += 1
			visited_node_flags[adjacentNode] = 1
	return visited_count

def build_graph_and_nodes(edge_count):
	graph = {}
	nodes = set([])
	for i in range(edge_count):
		(v1, v2) = list(map(lambda x: int(x) - 1, input().split(' ')))
		nodes.add(v1)
		nodes.add(v2)
		initialise_adjacency_list_if_needed(graph, v1, v2)
		graph[v1].append(v2)
		graph[v2].append(v1)
	nodes = range(max(nodes) + 1)
	return (graph, nodes)

def find_next_starting_point(visited_node_flags):
	for (i, flag) in enumerate(visited_node_flags):
		if flag == 0:
			return i

def mark_nonexistent_nodes(visited_node_flags, graph):
	for i in range(len(visited_node_flags)):
		node_exists = i in graph
		if not node_exists:
			visited_node_flags[i] = 1
edge_count = int(input())
(graph, nodes) = build_graph_and_nodes(edge_count)
visited_node_flags = [0] * len(nodes)
mark_nonexistent_nodes(visited_node_flags, graph)
starting_node = find_next_starting_point(visited_node_flags)
visited_counts = []
while sum(visited_node_flags) < len(nodes):
	visited_this_round = BFS_with_visited_count(graph, starting_node, visited_node_flags)
	visited_counts.append(visited_this_round)
	starting_node = find_next_starting_point(visited_node_flags)
print(min(visited_counts), max(visited_counts))


class Queue:

	def __init__(self):
		self.data = []
		self.size = 0

	def queue(self, item):
		self.data = [item] + self.data
		self.size += 1

	def dequeue(self):
		removed_item = self.data[-1]
		self.data = self.data[:-1]
		self.size -= 1
		return removed_item

	def empty(self):
		return self.size == 0

	def display(self):
		print(list(reversed(self.data)))

def initialise_adjacency_list_if_needed(graph, v1, v2):
	if v1 not in graph:
		graph[v1] = []
	if v2 not in graph:
		graph[v2] = []

def BFS_with_visited_count(graph, start, visited_node_flags):
	q = Queue()
	q.queue(start)
	visited_count = 1
	while not q.empty():
		cur = q.dequeue()
		visited_node_flags[cur] = 1
		if len(graph[cur]) == 0:
			continue
		for adjacentNode in graph[cur]:
			if visited_node_flags[adjacentNode]:
				continue
			q.queue(adjacentNode)
			visited_count += 1
			visited_node_flags[adjacentNode] = 1
	return visited_count

def build_graph_and_nodes(edge_count):
	graph = {}
	nodes = set([])
	for i in range(edge_count):
		(v1, v2) = list(map(lambda x: int(x) - 1, input().split(' ')))
		nodes.add(v1)
		nodes.add(v2)
		initialise_adjacency_list_if_needed(graph, v1, v2)
		graph[v1].append(v2)
		graph[v2].append(v1)
	nodes = range(max(nodes) + 1)
	return (graph, nodes)

def find_next_starting_point(visited_node_flags):
	for (i, flag) in enumerate(visited_node_flags):
		if flag == 0:
			return i

def mark_nonexistent_nodes(visited_node_flags, graph):
	for i in range(len(visited_node_flags)):
		node_exists = i in graph
		if not node_exists:
			visited_node_flags[i] = 1
edge_count = int(input())
(graph, nodes) = build_graph_and_nodes(edge_count)
visited_node_flags = [0] * len(nodes)
mark_nonexistent_nodes(visited_node_flags, graph)
starting_node = find_next_starting_point(visited_node_flags)
visited_counts = []
while sum(visited_node_flags) < len(nodes):
	visited_this_round = BFS_with_visited_count(graph, starting_node, visited_node_flags)
	visited_counts.append(visited_this_round)
	starting_node = find_next_starting_point(visited_node_flags)
print(min(visited_counts), max(visited_counts))


n = int(input().strip())
arr = [([], None) for _ in range(n * 2 + 1)]
for _ in range(n):
	(a, b) = map(int, input().strip().split(' '))
	arr[a][0].append(b)
	arr[b][0].append(a)

def visit(ind):
	cnt = 0
	stack = [ind]
	while stack:
		ind = stack.pop()
		if arr[ind][1] != None:
			continue
		arr[ind] = (arr[ind][0], True)
		cnt += 1
		for i in arr[ind][0]:
			stack.append(i)
	return cnt
min_ = n * 2
max_ = None
for i in range(n * 2 + 1):
	cnt = visit(i)
	if cnt > 1 and cnt < min_:
		min_ = cnt
	if max_ == None or cnt > max_:
		max_ = cnt
print(min_, max_)


import sys
n = int(sys.stdin.readline())
leader = {}

def find_leader(a):
	path = []
	while a in leader:
		path.append(a)
		a = leader[a]
	for y in path:
		leader[y] = a
	return a

def union(a, b):
	al = find_leader(a)
	bl = find_leader(b)
	if al != bl:
		leader[al] = bl
for i in range(n):
	(a, b) = sys.stdin.readline().split()
	(a, b) = (int(a), int(b))
	union(a, b)
from collections import defaultdict
size_of_set = defaultdict(int)
for a in leader:
	size_of_set[find_leader(a)] += 1

def second(t):
	return t[1]
sorted_by_size = sorted(size_of_set.items(), key=second)
small = sorted_by_size[0][1]
large = sorted_by_size[-1][1]
print(small + 1, large + 1)


from collections import defaultdict

def make_set(x):
	ds[x] = [0, 0, 0]
	ds[x][0] = x
	ds[x][1] = 0
	ds[x][2] = 1

def merge(x, y):
	xroot = find(x)
	yroot = find(y)
	if xroot == yroot:
		return
	if ds[xroot][1] < ds[yroot][1]:
		ds[xroot][0] = yroot
		ds[yroot][2] += ds[xroot][2]
	elif ds[xroot][1] > ds[yroot][1]:
		ds[yroot][0] = xroot
		ds[xroot][2] += ds[yroot][2]
	else:
		ds[yroot][0] = xroot
		ds[xroot][2] += ds[yroot][2]
		ds[xroot][1] += 1

def find(x):
	if ds[x][0] == x:
		return x
	else:
		return find(ds[x][0])

def size(x):
	xroot = find(x)
	return ds[xroot][2]
n = int(input())
ds = defaultdict(list)
for i in range(1, 2 * n + 1):
	make_set(i)
for _ in range(n):
	(i, j) = map(int, input().split())
	merge(i, j)
min_val = 2 * n + 1
max_val = 0
for i in range(1, 2 * n + 1):
	s = size(i)
	if s == 1:
		continue
	if s < min_val:
		min_val = s
	if s > max_val:
		max_val = s
print(min_val, max_val)


import sys
readrow = iter(sys.stdin.read().splitlines()).__next__
n = int(readrow())
m = n << 1
conn = tuple(([] for _ in range(m)))
for _ in range(n):
	(v, u) = map(int, readrow().split())
	u -= 1
	v -= 1
	conn[u].append(v)
	conn[v].append(u)
cache = []
maxv = 0
minv = m
newnodes = [True] * m
for (i, isnew) in enumerate(newnodes):
	if isnew:
		newnodes[i] = False
		cache.append(i)
		count = 1
		while cache:
			curr = cache.pop()
			for j in conn[curr]:
				if newnodes[j]:
					newnodes[j] = False
					cache.append(j)
					count += 1
		if count > 1:
			maxv = max(maxv, count)
			minv = min(minv, count)
print(minv, maxv)


import sys

def solve(N, E):
	color = dict()
	cc = []
	n = 0
	for i in range(N):
		(u, v) = E[i]
		if u not in color and v not in color:
			color[u] = n
			color[v] = n
			cc.append(set([u, v]))
			n += 1
		elif u not in color and v in color:
			k = color[v]
			cc[k].add(u)
			color[u] = k
		elif v not in color and u in color:
			k = color[u]
			cc[k].add(v)
			color[v] = k
		else:
			k0 = color[u] if color[u] <= color[v] else color[v]
			k1 = color[v] if color[u] <= color[v] else color[u]
			if k0 < k1:
				for x in cc[k1]:
					color[x] = k0
				cc[k0] |= cc[k1]
				cc[k1] = set()
	ccsize = []
	for i in range(len(cc)):
		clen = len(cc[i])
		if clen > 1:
			ccsize.append(clen)
	ccsize.sort()
	return (ccsize[0], ccsize[-1])
N = int(sys.stdin.readline())
E = []
for i in range(N):
	(g, b) = (int(x) for x in sys.stdin.readline().split())
	E.append((g, b))
(mi, ma) = solve(N, E)
print('%d %d' % (mi, ma))


n = int(input().strip())
(h, m) = ([], [])
for i in range(2 * n):
	h.append(i)
	m.append(1)

def find(t):
	if h[t] != t:
		h[t] = find(h[t])
	return h[t]
for _ in range(n):
	s = list(map(int, input().strip().split()))
	a = find(s[0] - 1)
	b = find(s[1] - 1)
	if a != b:
		h[a] = b
		m[b] += m[a]
		m[a] = 0
(minv, maxv) = (n * 2, 0)
for i in m:
	if i > 1:
		minv = min(minv, i)
		maxv = max(maxv, i)
print(minv, maxv)


import fileinput
from collections import defaultdict

def dfs(graph, node, visited=set()):
	visited.add(node)
	for neighbour in graph[node]:
		if neighbour not in visited:
			dfs(graph, neighbour, visited)
		else:
			continue
	return visited

def iterative_dfs(graph, node):
	visited = set()
	stack = list()
	stack.append(node)
	while len(stack) != 0:
		current = stack.pop()
		visited.add(current)
		for neighbour in graph[current]:
			if neighbour not in visited:
				stack.append(neighbour)
			else:
				continue
	return visited

class Graph(object):

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

	@property
	def nodes(self):
		return self.adjacency_list.keys()

	def add_edge(self, node1, node2, bidirectional=True):
		self._add_edge(node1, node2)
		if bidirectional:
			self._add_edge(node2, node1)

	def _add_edge(self, node1, node2):
		self.adjacency_list[node1].append(node2)

	def get_components(self):
		comp_sizes = []
		visited = set()
		for node in self.adjacency_list.keys():
			if node in visited:
				continue
			comp = iterative_dfs(self.adjacency_list, node)
			visited |= comp
			comp_sizes.append(len(comp))
		return comp_sizes

class GraphParser(object):

	def __init__(self):
		self.graph = Graph()

	def read(self, line):
		nodes = line.split()
		if len(nodes) != 2:
			return
		self.graph.add_edge(nodes[0], nodes[1])
parser = GraphParser()
for (i, line) in enumerate(fileinput.input()):
	if i == 0:
		continue
	parser.read(line)
graph = parser.graph
comps = graph.get_components()
if not len(comps):
	print('0 0')
	exit(0)
comps.sort()
(smallest, largest) = (comps[0], comps[-1])
print(str(smallest) + ' ' + str(largest))


class Node:

	def __init__(self, index):
		self.index = index
		self.edges = []
		self.visited = False

def addNodes(numNodes, start, Graph):
	q = []
	q.append(start)
	start.visited = True
	c = 1
	while q:
		s = q.pop(0)
		for i in s.edges:
			if not i.visited:
				q.append(i)
				c += 1
				i.visited = True
	if c == 1:
		return numNodes
	numNodes.append(c)
	return numNodes
n = int(input())
Graph = [None] * 2 * n
for i in range(2 * n):
	Graph[i] = Node(i + 1)
for i in range(n):
	(a, b) = list(map(int, input().split(' ')))
	Graph[a - 1].edges.append(Graph[b - 1])
	Graph[b - 1].edges.append(Graph[a - 1])
numNodes = []
for i in Graph:
	if not i.visited:
		addNodes(numNodes, i, Graph)
print(min(numNodes), max(numNodes), sep=' ')


class UnionSetNode(object):

	def __init__(self, value):
		self.value = value
		self.rank = 0
		self.parent = self
		self.nodes = 1

	def __repr__(self):
		return '<Node value={}, rank={}, parent={} nodes={}>'.format(self.value, self.rank, self.parent.value, self.nodes)

class UnionSet(object):

	def __init__(self):
		self._nodes = {}
		self._roots = {}

	def make_set(self, value):
		nodes = self._nodes
		roots = self._roots
		if value not in nodes:
			node = UnionSetNode(value)
			nodes[node.value] = node
			roots[node.value] = node

	def merge(self, value_x, value_y):
		nodes = self._nodes
		self._validate_existence_node(value_x)
		self._validate_existence_node(value_y)
		root_x_value = self.find(value_x)
		root_y_value = self.find(value_y)
		if root_x_value == root_y_value:
			return
		root_x = nodes[root_x_value]
		root_y = nodes[root_y_value]
		if root_x.rank == root_y.rank:
			root_y.parent = root_x
			root_x.rank += 1
			root_x.nodes += root_y.nodes
			del self._roots[root_y_value]
		elif root_x.rank > root_y.rank:
			root_y.parent = root_x
			root_x.nodes += root_y.nodes
			del self._roots[root_y_value]
		else:
			root_x.parent = root_y
			root_y.nodes += root_x.nodes
			del self._roots[root_x_value]

	def find(self, value):
		self._validate_existence_node(value)
		node = self._nodes[value]
		to_compress = []
		while node.parent != node:
			node = node.parent
			to_compress.append(node)
		for child_node in to_compress:
			child_node.parent = node
		return node.value

	def roots(self):
		return list(self._roots.values())

	def _validate_existence_node(self, value):
		if value not in self._nodes:
			raise ValueError('Inexistent node provided {}'.format(value))

	def __repr__(self):
		nodes = self._nodes
		repr_nodes = []
		for value in nodes:
			repr_nodes.append(nodes[value])
		return str(repr_nodes)
num_entries = int(input())
distinct_nodes = {}
union_set = UnionSet()
for _i in range(num_entries):
	(value_a, value_b) = [int(x) for x in input().strip().split()]
	if value_a not in distinct_nodes:
		union_set.make_set(value_a)
		distinct_nodes[value_a] = True
	if value_b not in distinct_nodes:
		union_set.make_set(value_b)
		distinct_nodes[value_b] = True
	union_set.merge(value_a, value_b)
min_nodes = None
max_nodes = None
roots = union_set.roots()
for node in roots:
	if min_nodes is None or node.nodes < min_nodes:
		min_nodes = node.nodes
	if max_nodes is None or node.nodes > max_nodes:
		max_nodes = node.nodes
print('{} {}'.format(min_nodes, max_nodes))


class DisjointSet:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.total = [1] * N

	def union(self, a, b):
		a_parent = self.find(a)
		b_parent = self.find(b)
		if a_parent != b_parent:
			self.parent[b_parent] = a_parent
			self.total[a_parent] += self.total[b_parent]

	def find(self, a):
		parents = [a]
		while self.parent[a] != a:
			a = self.parent[a]
			parents.append(a)
		for x in parents[:-1]:
			self.parent[x] = parents[-1]
		return parents[-1]

	def get_total(self, a):
		return self.total[self.find(a)]
N = int(input())
ds = DisjointSet(2 * N)
for i in range(N):
	(G, B) = map(int, input().split())
	ds.union(G - 1, B - 1)
set_size = [ds.get_total(i) for i in range(2 * N) if ds.get_total(i) != 1]
print(min(set_size), max(set_size))