Berland Government decided to improve relations with neighboring countries. First of all, it was decided to build new roads so that from each city of Berland and neighboring countries it became possible to reach all the others. There are n cities in Berland and neighboring countries in total and exactly n - 1 two-way roads. Because of the recent financial crisis, the Berland Government is strongly pressed for money, so to build a new road it has to close some of the existing ones. Every day it is possible to close one existing road and immediately build a new one. Your task is to determine how many days would be needed to rebuild roads so that from each city it became possible to reach all the others, and to draw a plan of closure of old roads and building of new ones.

Input

The first line contains integer n (2 ≤ n ≤ 1000) — amount of cities in Berland and neighboring countries. Next n - 1 lines contain the description of roads. Each road is described by two space-separated integers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — pair of cities, which the road connects. It can't be more than one road between a pair of cities. No road connects the city with itself.

Output

Output the answer, number t — what is the least amount of days needed to rebuild roads so that from each city it became possible to reach all the others. Then output t lines — the plan of closure of old roads and building of new ones. Each line should describe one day in the format i j u v — it means that road between cities i and j became closed and a new road between cities u and v is built. Cities are numbered from 1. If the answer is not unique, output any.

Examples

Input

2
1 2


Output

0


Input

7
1 2
2 3
3 1
4 5
5 6
6 7


Output

1
3 1 3 7

Difficulty: HARD
Tags: Tree algorithms

Graph algorithms

Spanning trees

Starter code:

Solutions:
from os import path
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('a')
file = 1

def solve():
	n = ii()
	par = [i for i in range(n + 1)]
	freq = [1 for i in range(n + 1)]

	def find(i):
		if i == par[i]:
			return i
		par[i] = find(par[i])
		return par[i]

	def union(x, y):
		x = find(x)
		y = find(y)
		if x == y:
			return 0
		if freq[x] < freq[y]:
			par[x] = y
			freq[y] += 1
		else:
			par[y] = x
			freq[x] += 1
		return 1
	erase = []
	for i in range(n - 1):
		(x, y) = mi()
		x1 = find(x)
		y1 = find(y)
		if x1 == y1:
			erase.append([x, y])
			continue
		union(x, y)
	add = []
	x = list(set(par[1:]))
	for i in range(1, len(x)):
		if union(x[0], x[i]):
			add.append([x[0], x[i]])
	print(len(add))
	for i in range(len(add)):
		print(*erase[i], end=' ')
		print(*add[i], end=' ')
		print()
if file:
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	else:
		input = sys.stdin.readline
solve()


n = int(input())
p = [0] * n
rank = [0] * n
for i in range(n):
	p[i] = i

def find_set(x):
	if x == p[x]:
		return x
	return find_set(p[x])

def union_set(a, b):
	fa = find_set(a)
	fb = find_set(b)
	if rank[fa] < rank[fb]:
		p[fa] = fb
	else:
		p[fb] = fa
	if rank[a] == rank[b]:
		rank[a] += 1
edges = []
for i in range(n - 1):
	(a, b) = list(map(int, input().split()))
	fa = find_set(a - 1)
	fb = find_set(b - 1)
	if fa == fb:
		edges.append((a - 1, b - 1, fa))
	else:
		union_set(a - 1, b - 1)
used = [False] * len(edges)
P = []
q = []
for i in range(n):
	if find_set(i) == i:
		q.append(i)
for i in range(len(q) - 1):
	P.append((edges[i][0] + 1, edges[i][1] + 1, q[i] + 1, q[i + 1] + 1))
	union_set(q[i], q[i + 1])
print(len(P))
for (i, j, k, z) in P:
	print(i, j, k, z)


class BerlandRoads:

	def __init__(self, n, edges):
		self.n = n
		self.edges = edges
		self.parents = [i for i in range(n)]
		self.sizes = [1 for i in range(n)]

	def find(self, v):
		while self.parents[v] != v:
			temp = self.parents[v]
			self.parents[v] = self.parents[temp]
			v = temp
		return v

	def union(self, u, v):
		u = self.find(u)
		v = self.find(v)
		if u == v:
			return False
		else:
			if self.sizes[u] > self.sizes[v]:
				self.parents[v] = u
				self.sizes[u] += self.sizes[v]
			else:
				self.parents[u] = v
				self.sizes[v] += self.sizes[u]
			return True

	def build_roads(self):
		rem_edges = []
		for (u, v) in self.edges:
			if not self.union(u - 1, v - 1):
				rem_edges.append((u, v))
		tree_reps = []
		for i in range(n):
			if self.parents[i] == i:
				tree_reps.append(i + 1)
		print(len(rem_edges))
		for i in range(len(rem_edges)):
			vals = [rem_edges[i][0], rem_edges[i][1], tree_reps[i], tree_reps[i + 1]]
			print(*vals)
n = int(input())
edges = []
for i in range(n - 1):
	(u, v) = list(map(int, input().strip(' ').split(' ')))
	edges.append((u, v))
br = BerlandRoads(n, edges)
br.build_roads()


C = 0
n = int(input())
B = [0 for _ in range(n + 1)]
p = [0 for _ in range(n + 1)]
CC = [0 for _ in range(n + 1)]
a = [[] for _ in range(n + 1)]
VV = []
V = []
for i in range(n - 1):
	(x, y) = map(int, input().split())
	a[x].append(y)
	a[y].append(x)
	V.append([x, y])

def anc(u):
	if p[u] == u:
		return u
	else:
		p[u] = anc(p[u])
		return p[u]

def join(u, v):
	p[anc(u)] = anc(v)

def DFS(u):
	B[u] = C
	for v in a[u]:
		if B[v] == 0:
			DFS(v)
for i in range(1, n + 1):
	p[i] = i
for it in V:
	if anc(it[0]) == anc(it[1]):
		VV.append(it)
	else:
		join(it[0], it[1])
for i in range(1, n + 1):
	if B[i] == 0:
		C += 1
		DFS(i)
for i in range(1, n + 1):
	CC[B[i]] = i
it = 0
print(C - 1)
for i in range(C - 1):
	print(VV[i][0], ' ', VV[i][1], ' ', CC[i + 1], ' ', CC[i + 2])


import os, sys
from io import BytesIO, IOBase

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

def union(parent, a, b, rank):
	(a, b) = (find(parent, a), find(parent, b))
	if a != b:
		if rank[a] < rank[b]:
			(a, b) = (b, a)
		parent[b] = a
		if rank[a] == rank[b]:
			rank[a] += 1
		return 1
	return 0

def main():
	n = int(input())
	parent = list(range(n))
	rank = [0] * n
	ex = []
	for _ in range(n - 1):
		(a1, b1) = map(lambda xx: int(xx) - 1, input().split())
		if not union(parent, a1, b1, rank):
			ex.append((a1, b1))
	par = []
	for i in range(n):
		if parent[i] == i:
			par.append(i)
	print(len(par) - 1)
	for i in range(len(par) - 1):
		print(ex[i][0] + 1, ex[i][1] + 1, par[i] + 1, par[i + 1] + 1)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def root(node):
	if node == parent[node]:
		return node
	parent[node] = root(parent[node])
	return parent[node]

def union(a, b):
	root_a = root(a)
	root_b = root(b)
	if root_a != root_b:
		if rank[root_a] < rank[root_b]:
			(root_a, root_b) = (root_b, root_a)
		parent[root_b] = root_a
		if rank[root_a] == rank[root_b]:
			rank[root_a] += 1

def find(a, b):
	if root(a) == root(b):
		return True
	else:
		return False
n = int(input())
parent = [x for x in range(n + 1)]
rank = [0 for x in range(n + 1)]
join = []
remove = []
for i in range(n - 1):
	(u, v) = map(int, input().strip().split(' '))
	if u > v:
		(u, v) = (v, u)
	if find(u, v) == False:
		union(u, v)
	else:
		remove.append((u, v))
for i in range(1, n + 1):
	parent[i] = root(parent[i])
for i in range(2, n + 1):
	if root(1) != root(i):
		join.append((1, i))
		union(1, i)
if len(join) == 0 or len(remove) == 0:
	print(0)
else:
	print(len(join))
	for i in range(len(join)):
		print(remove[i][0], remove[i][1], join[i][0], join[i][1])


def make_set(v):
	parent[v] = v
	rank[v] = 1

def find_set(a):
	if parent[a] == a:
		return a
	parent[a] = find_set(parent[a])
	return parent[a]

def union_set(a, b):
	x = find_set(a)
	y = find_set(b)
	if x == y:
		return
	if rank[x] > rank[y]:
		parent[y] = x
		rank[x] += rank[y]
	else:
		parent[x] = y
		rank[y] += rank[x]
n = int(input())
a = [_ for _ in range(1, n + 1)]
parent = [0] * n
rank = [0] * n
for i in a:
	make_set(i - 1)
t = []
for i in range(n - 1):
	(p, q) = map(int, input().split(' '))
	if find_set(p - 1) == find_set(q - 1):
		t.append((p - 1, q - 1))
	else:
		union_set(p - 1, q - 1)
d = []
for i in range(2, n + 1):
	if find_set(i - 1) != find_set(0):
		union_set(i - 1, 0)
		d.append((i, 1))
y = len(t)
print(len(d))
for i in d:
	if y > 0:
		print(str(t[len(t) - y][0] + 1) + ' ' + str(t[len(t) - y][1] + 1) + ' ' + str(i[0]) + ' ' + str(i[1]))
		y -= 1


def main():
	from random import getrandbits

	def find_set(v):
		if v == parent[v]:
			return v
		parent[v] = find_set(parent[v])
		return parent[v]

	def unite(a, b):
		(a, b) = (find_set(a), find_set(b))
		if a == b:
			return False
		if getrandbits(1):
			(a, b) = (b, a)
		parent[a] = b
		return True
	n = int(input())
	parent = [i for i in range(n + 1)]
	spare = []
	for i in range(n - 1):
		(a, b) = [int(i) for i in input().split()]
		if not unite(a, b):
			spare.append((a, b))
	leaders = list(set((find_set(i) for i in range(1, n + 1))))
	print(len(spare))
	for i in range(len(spare)):
		print(*spare[i], end=' ')
		print(leaders[i], leaders[i + 1])
main()


from sys import stdin
from collections import defaultdict
input = stdin.readline

def put():
	return map(int, input().split())

def find(i):
	if i == p[i]:
		return i
	p[i] = find(p[i])
	return p[i]

def union(i, j):
	if rank[i] > rank[j]:
		(i, j) = (j, i)
	elif rank[i] == rank[j]:
		rank[j] += 1
	p[i] = j
n = int(input())
graph = [[] for i in range(n)]
(extra, p, rank) = ([], list(range(n)), [0] * n)
for _ in range(n - 1):
	(x, y) = put()
	(i, j) = map(find, (x - 1, y - 1))
	if i != j:
		union(i, j)
	else:
		extra.append((x, y))
s = set(map(find, range(n)))
x = s.pop()
print(len(s))
for y in s:
	(u, v) = extra.pop()
	print(u, v, x + 1, y + 1)


import os
import sys
import math
import itertools
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = 10 ** 9 + 7
pi = 3.141592653589793

def i1():
	return int(sys.stdin.readline())

def sf():
	return sys.stdin.readline()

def mi():
	return map(int, sys.stdin.readline().split())

def arr():
	return list(map(int, sys.stdin.readline().split()))

def pf(ans):
	return sys.stdout.write(str(ans) + '\n')

def gcd(a, b):
	if a == 0:
		return b
	elif b == 0:
		return a
	if a > b:
		return gcd(a % b, b)
	else:
		return gcd(a, b % a)

def lcm(a, b):
	return a * b // gcd(a, b)

def solve():
	n = int(input())
	parent = [i for i in range(n + 1)]
	rank = [0] * (n + 1)
	close = []
	build = []

	def find(vertex):
		if vertex != parent[vertex]:
			parent[vertex] = find(parent[vertex])
		return parent[vertex]

	def union(x, y):
		parent_x = find(x)
		parent_y = find(y)
		if rank[parent_x] < rank[parent_y]:
			parent[parent_x] = parent_y
		elif rank[parent_y] < rank[parent_x]:
			parent[parent_y] = parent_x
		else:
			parent[parent_y] = parent_x
			rank[parent_x] += 1

	def roads():
		for i in range(n - 1):
			(u, v) = map(int, input().split())
			if find(u) == find(v):
				close.append([u, v])
			else:
				union(u, v)
		for i in range(2, n + 1):
			if find(i) != find(1):
				union(i, 1)
				build.append([1, i])
	roads()
	print(len(build))
	for i in range(len(close)):
		print(close[i][0], close[i][1], build[i][0], build[i][1])
solve()


import math
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
from copy import deepcopy

def isprime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def freq(l):
	f = {}
	for i in l:
		if i in f:
			f[i] += 1
		else:
			f[i] = 1
	return f
MAX = pow(10, 5)
inp = lambda : int(stdin.readline())
sip = lambda : stdin.readline()
mulip = lambda : map(int, stdin.readline().split())
lst = lambda : list(map(int, stdin.readline().split()))
slst = lambda : list(sip())

def make_set(N):
	for i in range(1, N + 1):
		d[i] = i

def find_set(a):
	if d[a] == a:
		return a
	else:
		d[a] = find_set(d[a])
		return d[a]

def union(a, b):
	x = find_set(a)
	y = find_set(b)
	if x == y:
		arr.append([a, b])
	else:
		d[max(x, y)] = min(x, y)
N = inp()
d = {}
arr = []
par = {}
make_set(N)
for i in range(N - 1):
	(a, b) = mulip()
	union(a, b)
for i in d:
	x = find_set(i)
	if x not in par:
		par[x] = x
l = list(par.values())
if len(l) == 1 or len(arr) == 0:
	print(0)
else:
	print(len(l) - 1)
	for i in range(1, len(l)):
		print(*arr[i - 1], l[i - 1], l[i])


n = int(input())

class UnionFind:

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

	def find(self, a):
		r = self.representative[a]
		if self.representative[r] != r:
			r = self.find(r)
			self.representative[a] = r
		return r

	def union(self, a, b):
		ra = self.find(a)
		rb = self.find(b)
		self.representative[ra] = rb

	def same(self, a, b):
		return self.find(a) == self.find(b)
uf = UnionFind(n)
edges_to_remove = []
for i in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	if uf.same(a, b):
		edges_to_remove.append((a, b))
	else:
		uf.union(a, b)
edges_to_create = []
for i in range(n):
	if not uf.same(0, i):
		edges_to_create.append((0, i))
		uf.union(0, i)
output = []
for ((i, j), (u, v)) in zip(edges_to_remove, edges_to_create):
	output.append('%d %d %d %d' % (i + 1, j + 1, u + 1, v + 1))
output = ['%d' % len(output)] + output
print('\n'.join(output))


n = int(input())
parent = list(range(n + 1))

def find(i):
	while i != parent[i]:
		i = parent[i]
	return i
to_delete = []
for _ in range(n - 1):
	(a, b) = list(map(int, input().split()))
	a_id = find(a)
	b_id = find(b)
	if a_id == b_id:
		to_delete.append((a, b))
	else:
		parent[a_id] = b_id
print(len(to_delete))
first_id = find(1)
for (x, y) in to_delete:
	for other in range(2, n + 1):
		other_id = find(other)
		if first_id != other_id:
			parent[other_id] = first_id
			print(x, y, other_id, first_id)
			break


def find(u):
	if parent[u] == u:
		return u
	parent[u] = find(parent[u])
	return parent[u]

def union(a, b):
	u = parent[a]
	v = parent[b]
	if size[u] > size[v]:
		parent[v] = u
		size[u] += size[v]
	else:
		parent[u] = v
		size[v] += size[u]
n = int(input())
parent = [i for i in range(n + 1)]
size = [1 for i in range(n + 1)]
torm = []
for j in range(n - 1):
	(u, v) = map(int, input().split())
	if find(u) != find(v):
		union(u, v)
	else:
		torm.append([u, v])
toadd = []
for i in range(1, n + 1):
	if find(1) != find(i):
		union(1, i)
		toadd.append([1, i])
ans = []
for j in range(len(toadd)):
	ans.append(torm[j] + toadd[j])
print(len(ans))
for j in ans:
	print(*j)


def find_set(p, a, shorten=True):
	t = a
	while p[t] != t:
		t = p[t]
	if shorten:
		p[a] = t
	return t

def union(p, a, b, acyclic):
	pa = find_set(p, a)
	pb = find_set(p, b)
	if pa != pb:
		p[pb] = pa
	elif a != b:
		acyclic.append((a, b))
n = int(input())
p = [0] * (n + 1)
ac = []
for i in range(1, n + 1):
	p[i] = i
for _ in range(n - 1):
	(a, b) = list(map(int, input().split()))
	union(p, a, b, ac)
print(len(ac))
j = 0
g = find_set(p, 1)
for i in range(2, n + 1):
	if find_set(p, i) != g:
		union(p, 1, i, [])
		print(*ac[j], 1, i)
		j += 1


import os
import sys
from io import BytesIO, IOBase
maxval = 1000
rank = [0] * (maxval + 1)
parent = [i for i in range(maxval + 1)]

def find(x):
	if x == parent[x]:
		return x
	parent[x] = find(parent[x])
	return parent[x]

def union(a, b):
	aset = find(a)
	bset = find(b)
	if aset == bset:
		return 1
	(ra, rb) = (rank[aset], rank[bset])
	if ra < rb:
		(aset, bset) = (bset, aset)
	parent[bset] = aset
	if ra == rb:
		rank[aset] += 1
	return 0

def main():
	n = int(input())
	extra = []
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		if union(a, b):
			extra.append((a, b))
	print(len(extra))
	zz = []
	for i in range(1, n + 1):
		if parent[i] == i:
			zz.append(i)
	for i in range(len(extra)):
		print(extra[i][0], extra[i][1], zz[i], zz[i + 1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def find_set(v):
	if parent[v] == v:
		return v
	parent[v] = find_set(parent[v])
	return parent[v]

def union(a, b):
	a = find_set(a)
	b = find_set(b)
	if a != b:
		if size[a] < size[b]:
			(a, b) = (b, a)
		parent[b] = a
		size[a] += size[b]
		return 1
	return 0
n = int(input())
parent = [int(i) for i in range(n + 1)]
size = [1 for i in range(n + 1)]
broke = []
for i in range(1, n):
	(a, b) = map(int, input().split())
	x = union(a, b)
	if x == 0:
		broke.append((a, b))
print(len(broke))
free = []
for i in range(1, n + 1):
	if parent[i] == i:
		free.append(i)
if len(broke) != 0:
	Ans = ''
	for i in range(len(broke)):
		Ans += str(broke[i][0]) + ' ' + str(broke[i][1]) + ' ' + str(free[i]) + ' ' + str(free[i + 1]) + ' '
	print(Ans)


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def solve(N, edges):
	dsu = collections.defaultdict(int)

	def find(u):
		if dsu[u] == 0:
			return u
		p = find(dsu[u])
		dsu[u] = p
		return p

	def union(u, v):
		(pu, pv) = (find(u), find(v))
		dsu[pu] = pv

	def same(u, v):
		return find(u) == find(v)
	remove = []
	for (u, v) in edges:
		if same(u, v):
			remove.append((u, v))
		else:
			union(u, v)
	groups = list(sorted({find(u) for u in range(1, N + 1)}))
	added = []
	for (u, v) in zip(groups[:-1], groups[1:]):
		added.append((u, v))
	if not remove:
		print(0)
	else:
		print(len(remove))
		for i in range(len(remove)):
			print('{} {} {} {}'.format(remove[i][0], remove[i][1], added[i][0], added[i][1]))
N = int(input())
edges = []
for i in range(N - 1):
	(u, v) = map(int, input().split())
	edges.append((u, v))
solve(N, edges)


def root(x, arr):
	if x == arr[x]:
		return x
	return root(arr[x], arr)
n = int(input())
roads = []
arr = [i for i in range(n + 1)]
dlt = []
for i in range(n - 1):
	(x, y) = map(int, input().split(' '))
	roads.append([x, y])
	a = root(x, arr)
	b = root(y, arr)
	if a == b:
		dlt.append([x, y])
	else:
		arr[b] = a
for i in range(1, n + 1):
	arr[i] = root(i, arr)
lst = list(set(arr))
lst.remove(0)
print(len(lst) - 1)
for i in range(len(lst) - 1):
	print(f'{dlt[i][0]} {dlt[i][1]} {lst[i]} {lst[i + 1]}')


class DSU:

	def __init__(self, n):
		self.parent = [*range(n)]
		self.set_size = [1] * n
		self.roots = set(self.parent)

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

	def join(self, a, b):
		a = self.root(a)
		b = self.root(b)
		if self.set_size[a] < self.set_size[b]:
			(a, b) = (b, a)
		if a == b:
			return False
		self.roots.remove(b)
		self.set_size[a] += self.set_size[b]
		self.set_size[b] = 0
		self.parent[b] = a
		return True
n = int(input())
roads = []
d = DSU(n)
for _ in range(n - 1):
	i = [*map(int, input().split())]
	if d.join(i[0] - 1, i[1] - 1) is False:
		roads.append(i)
ans = []
while len(d.roots) > 1 and len(roads):
	i = iter(d.roots)
	ans.append((roads[-1][0], roads[-1][1], next(i) + 1, next(i) + 1))
	d.join(ans[-1][2] - 1, ans[-1][3] - 1)
	del roads[-1]
print(len(ans))
for i in ans:
	print(*i)


import sys
from array import array

def input():
	return sys.stdin.buffer.readline().decode('utf-8')
n = int(input())
adj = [[] for _ in range(n)]
deg = [0] * n
for (u, v) in (map(int, input().split()) for _ in range(n - 1)):
	adj[u - 1].append(v - 1)
	adj[v - 1].append(u - 1)
	deg[u - 1] += 1
	deg[v - 1] += 1
groups = []
remove_edge = []
visited = [0] * n
visited2 = [0] * n

def dfs(stack: list):
	while stack:
		v = stack.pop()
		deg[v] = 0
		visited2[v] = 1
		for dest in adj[v]:
			if not deg[dest]:
				continue
			deg[dest] -= 1
			if deg[dest] == 1:
				stack.append(dest)
for i in range(n):
	if visited[i]:
		continue
	visited[i] = 1
	groups.append(i + 1)
	vs = [i]
	stack = [i]
	nstack = []
	while stack:
		v = stack.pop()
		if deg[v] <= 1:
			nstack.append(v)
		for dest in adj[v]:
			if not visited[dest]:
				visited[dest] = 1
				stack.append(dest)
				vs.append(dest)
	dfs(nstack)
	vs = [v for v in vs if not visited2[v]]
	while vs:
		(u, v) = (vs[-1], [x for x in adj[vs[-1]] if not visited2[x]][0])
		adj[u].remove(v)
		adj[v].remove(u)
		deg[u] -= 1
		deg[v] -= 1
		remove_edge.append(f'{u + 1} {v + 1} ')
		if deg[u] == 1:
			nstack.append(u)
		if deg[v] == 1:
			nstack.append(v)
		dfs(nstack)
		vs = [v for v in vs if not visited2[v]]
ans = []
for (i, s) in enumerate(remove_edge):
	ans.append(s + f'{groups[i]} {groups[i + 1]}')
sys.stdout.buffer.write((str(len(ans)) + '\n' + '\n'.join(ans)).encode('utf-8'))


def an(x):
	for i in x:
		return i
	return None
n = int(input())
r = dict()
for i in range(1, n + 1):
	r[i] = set()
edge = set()
for i in range(n - 1):
	(a, b) = map(int, input().split())
	edge.add((min(a, b), max(a, b)))
	r[a].add(b)
	r[b].add(a)
total = set(range(1, n + 1))
v = []
while len(total) > 0:
	v.append(set())
	x = total.pop()
	v[-1].add(x)
	sosed = set()
	sosed.add(x)
	while len(sosed) > 0:
		sosed2 = set()
		for i in sosed:
			for j in r[i]:
				if j in total:
					sosed2.add(j)
					v[-1].add(j)
					total.discard(j)
		sosed = sosed2.copy()
need = set()
for z in v:
	if len(z) == 1:
		continue
	x = an(z)
	sosed = set()
	sosed.add(x)
	pos = set()
	pos.add(x)
	while len(sosed) > 0:
		sosed2 = set()
		for i in sosed:
			for j in r[i]:
				if j not in pos:
					need.add((min(i, j), max(i, j)))
					sosed2.add(j)
					pos.add(j)
		sosed = sosed2.copy()
print(len(v) - 1)
edge -= need
edge = list(edge)
for i in range(len(v) - 1):
	print(edge[i][0], edge[i][1], an(v[i]), an(v[i + 1]))


import sys
lines = sys.stdin.read().split('\n')
lines.pop(-1)
n = int(lines.pop(0))

class Node:

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

	def __repr__(self):
		return 'Node({!r})'.format(self.id)

def Find(x):
	if x.parent is not x:
		x.parent = Find(x.parent)
	return x.parent

def Union(x, y):
	xroot = Find(x)
	yroot = Find(y)
	if xroot is yroot:
		return
	if xroot.rank < yroot.rank:
		(xroot, yroot) = (yroot, xroot)
	yroot.parent = xroot
	xroot.size += yroot.size
	if xroot.rank == yroot.rank:
		xroot.rank = xroot.rank + 1
nodos = [Node(i) for i in range(n + 1)]
edges = []
final = []
for line in lines:
	a = nodos[int(line.split(' ')[0])]
	b = nodos[int(line.split(' ')[1])]
	if Find(a) != Find(b):
		Union(a, b)
	else:
		edges.append((a, b))
for i in range(2, n + 1):
	if Find(nodos[1]) != Find(nodos[i]):
		final.append((nodos[1], nodos[i]))
		Union(nodos[1], nodos[i])
print(len(final))
for i in range(len(final)):
	print(edges[i][0].id, end=' ')
	print(edges[i][1].id, end=' ')
	print(final[i][0].id, end=' ')
	print(final[i][1].id, end=' ')


from sys import stdin
input = stdin.readline
n = int(input())
parents = list(range(n))
ranks = [0] * n

def find(x):
	if parents[x] != x:
		parents[x] = find(parents[x])
	return parents[x]

def union(x, y):
	xp = find(x)
	yp = find(y)
	if ranks[xp] > ranks[yp]:
		(xp, yp) = (yp, xp)
	parents[xp] = yp
	if ranks[xp] == ranks[yp]:
		ranks[yp] += 1
c = []
for ni in range(n - 1):
	(s, e) = [int(x) for x in input().strip().split()]
	s -= 1
	e -= 1
	sp = find(s)
	ep = find(e)
	if sp == ep:
		c.append([s, e])
	else:
		union(s, e)
for ni in range(n):
	find(ni)
ntc = list(set(parents))
print(len(ntc) - 1)
for i in range(1, len(ntc)):
	print(c[i - 1][0] + 1, c[i - 1][1] + 1, ntc[i] + 1, ntc[i - 1] + 1)


def find_set(v):
	if v == parent[v]:
		return v
	parent[v] = find_set(parent[v])
	return parent[v]

def union_sets(a, b):
	a = find_set(a)
	b = find_set(b)
	if a != b:
		if size[a] < size[b]:
			(a, b) = (b, a)
		parent[b] = a
		size[a] += size[b]
		return True
	return False
n = int(input())
parent = [0] * n
size = [1] * n
mustBreak = []
mustConnect = []
for i in range(n):
	parent[i] = i
for i in range(n - 1):
	line = input().split(' ')
	a = int(line[0]) - 1
	b = int(line[1]) - 1
	result = union_sets(a, b)
	if not result:
		mustBreak.append((a, b))
for i in range(n):
	if parent[i] == i:
		mustConnect.append(i)
lenMustBreak = len(mustBreak)
print(lenMustBreak)
if lenMustBreak != 0:
	for i in range(lenMustBreak):
		print(str(mustBreak[i][0] + 1) + ' ' + str(mustBreak[i][1] + 1) + ' ' + str(mustConnect[i] + 1) + ' ' + str(mustConnect[i + 1] + 1))


n = int(input())
parent = [i for i in range(n)]

def find_set(v):
	if v != parent[v]:
		parent[v] = find_set(parent[v])
	return parent[v]
rem = []
for _ in range(n - 1):
	(u, v) = list(map(int, input().split()))
	l = [u, v]
	l.sort()
	(u, v) = l
	u -= 1
	v -= 1
	a = find_set(u)
	b = find_set(v)
	if a != b:
		if a > b:
			(a, b) = (b, a)
		for i in range(len(parent)):
			if parent[i] == b:
				parent[i] = a
	else:
		rem.append([u + 1, v + 1])
d = {}
for i in range(len(parent)):
	d[parent[i]] = i
ind = []
for i in d:
	ind.append(d[i] + 1)
ans = []
for i in range(1, len(ind)):
	ans.append([ind[i], ind[i - 1]])
print(len(rem))
for i in range(len(rem)):
	print(*rem[i], *ans[i])


import sys
input = sys.stdin.readline
from collections import defaultdict

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

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

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		group_members = defaultdict(list)
		for member in range(self.n):
			group_members[self.find(member)].append(member)
		return group_members
n = int(input())
can_del = []
uf = UnionFind(n)
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	if uf.same(u, v):
		can_del.append([u + 1, v + 1])
	else:
		uf.union(u, v)
need_add = []
for i in range(n):
	for j in range(i + 1, n):
		if not uf.same(i, j):
			need_add.append([i + 1, j + 1])
			uf.union(i, j)
print(len(can_del))
for i in range(len(can_del)):
	print(*can_del[i], *need_add[i])


def getPar(x):
	while a[x] != x:
		x = a[x]
	return x

def union(x, y):
	p1 = getPar(x)
	p2 = getPar(y)
	a[p2] = p1
n = int(input())
a = [i for i in range(n + 1)]
e = []
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	p1 = getPar(u)
	p2 = getPar(v)
	if p1 == p2:
		e.append([u, v])
	else:
		union(u, v)
s = []
for i in a[1:]:
	s.append(getPar(i))
s = list(set(s))
print(len(e))
for i in range(len(e)):
	print(e[i][0], e[i][1], s[i], s[i + 1])


n = int(input())
graph = [_ for _ in range(n)]
reply = []

def findRoot(i):
	return i if i == graph[i] else findRoot(graph[i])
for _ in range(n - 1):
	s = input().split(' ')
	i = int(s[0]) - 1
	j = int(s[1]) - 1
	i_root = findRoot(i)
	j_root = findRoot(j)
	if i_root == j_root:
		reply.append((i, j))
	else:
		graph[i_root] = j_root
print(len(reply))
first_root = findRoot(0)
for (x, y) in reply:
	for k in range(1, n + 1):
		k_root = findRoot(k)
		if first_root != k_root:
			graph[k_root] = first_root
			print(x + 1, y + 1, k_root + 1, first_root + 1)
			break


def way(v):
	if vertices[v] == v:
		return v
	else:
		vertices[v] = way(vertices[v])
		return vertices[v]
n = int(input())
vertices = [i for i in range(n + 1)]
useless = []
useful = []
for i in range(n - 1):
	(a, b) = map(int, input().split())
	(v, u) = (a, b)
	a = way(a)
	b = way(b)
	if a == b:
		useless.append((v, u))
	else:
		vertices[max(a, b)] = min(a, b)
used = set()
previous = 0
for i in range(1, n + 1):
	a = way(i)
	if a not in used:
		used.add(a)
		if previous:
			useful.append((previous, i))
		previous = i
print(len(useful))
for i in range(len(useful)):
	(a, b) = useless.pop()
	(a1, b1) = useful.pop()
	print(a, b, a1, b1)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
start_time = time.time()

def getInts():
	return [int(s) for s in input().split()]

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

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def isInt(s):
	return '0' <= s[0] <= '9'
MOD = 998244353

def solve():
	N = getInt()
	graph = dd(set)
	for _ in range(N - 1):
		(A, B) = getInts()
		graph[A].add(B)
		graph[B].add(A)
	nodes = set(range(1, N + 1))
	to_connect = []
	to_remove = set()

	def bfs(node):
		to_connect.append(node)
		queue = dq([(node, 0)])
		visited.add(node)
		nodes.remove(node)
		while queue:
			(node, parent) = queue.popleft()
			for neigh in graph[node]:
				if neigh in visited and neigh != parent:
					(x, y) = (min(node, neigh), max(node, neigh))
					to_remove.add((x, y))
				elif neigh not in visited:
					visited.add(neigh)
					nodes.remove(neigh)
					queue.append((neigh, node))
	while nodes:
		visited = set()
		node = next(iter(nodes))
		bfs(node)
	to_remove = list(to_remove)
	assert len(to_remove) == len(to_connect) - 1
	print(len(to_remove))
	while to_remove:
		(i, j) = to_remove.pop()
		v = to_connect.pop()
		u = to_connect[-1]
		print(i, j, u, v)
	assert len(to_connect) == 1
	return
solve()


class dsu:

	def __init__(self, n):
		self.p = []
		for x in range(n):
			self.p.append(x)

	def find(self, v):
		if self.p[v] == v:
			return v
		else:
			self.p[v] = self.find(self.p[v])
			return self.p[v]

	def union(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a != b:
			self.p[a] = b

	def __str__(self):
		return str(self.p)
n = int(input())
DSU = dsu(n + 1)
WRONG = []
for x in range(n - 1):
	ss = input().split()
	a = int(ss[0])
	b = int(ss[1])
	if DSU.find(a) == DSU.find(b):
		WRONG.append([a, b])
	else:
		DSU.union(a, b)
z = 2
print(len(WRONG))
for x in range(len(WRONG)):
	while DSU.find(1) == DSU.find(z):
		z += 1
	DSU.union(1, z)
	print(WRONG[x][0], WRONG[x][1], 1, z)


class DSU:
	nodes = []
	duplicates = []

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

	def find(self, x):
		return self.nodes[x]

	def union(self, x, y):
		(xRoot, yRoot) = (self.find(x), self.find(y))
		if xRoot[0] == yRoot[0]:
			self.duplicates.append([x, y])
			return
		connections = xRoot[1] + yRoot[1]
		xRoot_pointer__original = xRoot[0]
		yRoot_pointer__original = yRoot[0]
		if xRoot[1] > yRoot[1]:
			for node in self.nodes:
				if node[0] == yRoot_pointer__original or node[0] == xRoot_pointer__original:
					node[0] = xRoot_pointer__original
					node[1] = connections
		else:
			for node in self.nodes:
				if node[0] == xRoot_pointer__original or node[0] == yRoot_pointer__original:
					node[0] = yRoot_pointer__original
					node[1] = connections

	def insert(self, x, y):
		if self.nodes[x][0] == 0 and self.nodes[y][0] == 0:
			self.nodes[x] = [x, 2]
			self.nodes[y] = [x, 2]
		elif self.nodes[x][0] != 0 and self.nodes[y][0] != 0:
			self.union(x, y)
		elif self.nodes[x][0] != 0:
			self.nodes[y] = [y, 1]
			self.union(x, y)
		elif self.nodes[y][0] != 0:
			self.nodes[x] = [x, 1]
			self.union(x, y)
n = int(input())
dsu = DSU(n + 1)
for i in range(n - 1):
	a = list(map(int, input().split()))
	(x, y) = (a[0], a[1])
	dsu.insert(x, y)
new_roads = []
connected = -1
for i in range(1, len(dsu.nodes)):
	if dsu.nodes[i] != [0, 0]:
		connected = i
		break
for i in range(len(dsu.duplicates)):
	for i in range(1, len(dsu.nodes)):
		if dsu.nodes[i][0] != dsu.nodes[connected][0] and dsu.nodes[i] != [0, 0]:
			dsu.union(connected, i)
			new_roads.append([connected, i])
			break
for i in range(1, len(dsu.nodes)):
	if dsu.nodes[i] == [0, 0]:
		new_roads.append([connected, i])
print(len(new_roads))
for i in range(len(new_roads)):
	print(dsu.duplicates[i][0], dsu.duplicates[i][1], new_roads[i][0], new_roads[i][1])


n = int(input())
p = [i for i in range(n + 1)]

def asd(i):
	if i != p[i]:
		p[i] = asd(p[i])
	return p[i]

def qwe(i, j):
	i = asd(i)
	j = asd(j)
	if i != j:
		p[i] = p[j]
		return True
	return False
l = list()
for i in range(n - 1):
	(a, b) = map(int, input().split())
	if not qwe(a, b):
		l.append((a, b))
print(len(l))
for i in l:
	for j in range(1, n + 1):
		if qwe(i[0], j):
			print(f'{i[0]} {i[1]} {i[0]} {j}')
			break


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

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

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

class Node:

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

	def __str__(self):
		return self.label
n = int(input())
l = [Node(i) for i in range(n)]
calles_cerrar = list()
calles_abrir = list()
[MakeSet(node) for node in l]
for i in range(n - 1):
	(a, b) = list(map(int, input().strip().split()))
	if Find(l[a - 1]) != Find(l[b - 1]):
		Union(l[a - 1], l[b - 1])
	else:
		calles_cerrar.append((a - 1, b - 1))
for i in range(1, n):
	if Find(l[0]) != Find(l[i]):
		calles_abrir.append((0, i))
		Union(l[0], l[i])
print(len(calles_cerrar))
for i in range(len(calles_cerrar)):
	lista = calles_cerrar[i] + calles_abrir[i]
	print(' '.join((str(p + 1) for p in lista)))


n = int(input())
a = [[] for i in range(n)]
for i in range(n):
	for j in range(n):
		if i != j:
			a[i].append([j + 1, 1])
		else:
			a[i].append([j + 1, 1000000000000000000])
d = []
e = []
for i in range(n - 1):
	(u, v) = list(map(int, input().split()))
	a[u - 1][v - 1][1] = 0
	a[v - 1][u - 1][1] = 0
	e.append(sorted([u, v]) + [1])
b = [[-1, -1] for i in range(n)]
c = [0] * n
c[0] = 2
t = 0
for i in a[0]:
	if i[0] != 1:
		b[i[0] - 1] = [i[1], 1]
		c[i[0] - 1] = 1
for i in range(n - 1):
	z = -1
	for j in range(n):
		if c[j] == 1 and (z == -1 or b[j][0] < b[z][0]):
			z = j
	c[z] = 2
	t += b[z][0]
	e.append(sorted([b[z][1], z + 1]) + [2])
	for j in a[z]:
		if j != z + 1:
			if c[j[0] - 1] == 0:
				c[j[0] - 1] = 1
				b[j[0] - 1] = [j[1], z + 1]
			elif j[1] < b[j[0] - 1][0]:
				b[j[0] - 1] = [j[1], z + 1]
e.sort()
f = []
g = []
for i in range(len(e)):
	if e[i][2] == 2:
		if not (i and e[i - 1][0] == e[i][0] and (e[i - 1][1] == e[i][1])):
			g.append([e[i][0], e[i][1]])
	elif not (2 * n - 3 - i and e[i + 1][0] == e[i][0] and (e[i + 1][1] == e[i][1])):
		f.append([e[i][0], e[i][1]])
print(t)
for i in range(t):
	print(*f[i] + g[i])


def find_set(parent, v):
	stack = [v, 0]
	while stack:
		anymore = False
		(x, y) = (stack[-2], stack[-1])
		if parent[x] != x and y == 0:
			anymore = True
			stack[-1] = 1
			stack.append(parent[x])
			stack.append(0)
		elif parent[x] == x:
			dada = parent[x]
			anymore = False
		else:
			anymore = False
		if anymore == False:
			parent[x] = dada
			stack.pop()
			stack.pop()
	return parent[v]

def union_set(a, b, size, parent, brk):
	(u, v) = (a, b)
	a = find_set(parent, a)
	b = find_set(parent, b)
	if a != b:
		if size[a] < size[b]:
			(a, b) = (b, a)
		parent[b] = a
		size[a] += size[b]
	else:
		brk.append([u, v])
n = int(input())
parent = [i for i in range(n + 1)]
size = [1] * (n + 1)
brk = []
for i in range(n - 1):
	(a, b) = map(int, input().split())
	union_set(a, b, size, parent, brk)
etc = {}
for i in range(1, n + 1):
	find_set(parent, i)
allah = parent[1]
etc[parent[1]] = 1
parents = []
for i in range(2, len(parent)):
	try:
		etc[parent[i]] += 1
	except:
		parents.append(parent[i])
		etc[parent[i]] = 1
print(len(parents))
for i in range(len(parents)):
	(x, y) = brk.pop()
	print(x, y, allah, parents[i])


class Graph:

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

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

	def union(self, a, b):
		pa = self.find(a)
		pb = self.find(b)
		if pa != pb:
			if self.rank[pa] > self.rank[pb]:
				self.parent[pb] = pa
			elif self.rank[pa] < self.rank[pb]:
				self.parent[pa] = pb
			else:
				self.parent[pb] = pa
				self.rank[pa] += 1
			return 1
		else:
			delete.append([a, b])
		return 0
n = int(input())
graph = Graph(n)
c = n
delete = []
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	c -= graph.union(a, b)
arr = []
print(c - 1)
for i in range(1, n + 1):
	arr.append(graph.find(i))
arr = list(set(arr))
for i in range(1, len(arr)):
	print(delete[i - 1][0], delete[i - 1][1], arr[0], arr[i])


def u_find(padre, i):
	if padre[i] == -1:
		return i
	return u_find(padre, padre[i])

def union(padre, x, y):
	x_i = u_find(padre, x)
	y_j = u_find(padre, y)
	padre[x_i] = y_j
n = int(input())
grafo = [list() for i in range(n)]
caminos_iniciales = []
for i in range(n - 1):
	(x, y) = map(lambda z: int(z) - 1, input().split())
	grafo[x].append(y)
	grafo[y].append(x)
	caminos_iniciales.append((x, y))
cerrados = []
padre = [-1 for i in range(n)]
for (x, y) in caminos_iniciales:
	i = u_find(padre, x)
	j = u_find(padre, y)
	if i == j:
		cerrados.append((x + 1, y + 1))
	else:
		union(padre, x, y)
nuevos = []
for i in range(1, n):
	if u_find(padre, 0) != u_find(padre, i):
		union(padre, 0, i)
		nuevos.append((0 + 1, i + 1))
print(len(cerrados))
for index in range(len(cerrados)):
	(i, j) = cerrados[index]
	(u, v) = nuevos[index]
	print(i, j, u, v)


from sys import stdin, stdout

def find(node):
	x = []
	while dsu[node] > 0:
		x.append(node)
		node = dsu[node]
	for i in x:
		dsu[i] = node
	return node

def union(node1, node2):
	if dsu[node1] > dsu[node2]:
		(node1, node2) = (node2, node1)
	dsu[node1] += dsu[node2]
	dsu[node2] = node1
n = int(stdin.readline().strip())
dsu = [-1] * (n + 1)
remove = []
for __ in range(n - 1):
	(a, b) = map(int, stdin.readline().strip().split())
	(p_a, p_b) = (find(a), find(b))
	if p_a == p_b:
		remove.append((a, b))
	else:
		union(p_a, p_b)
req = []
for i in range(1, n + 1):
	if dsu[i] < 0:
		req.append(i)
if len(req) == 1:
	stdout.write('0')
else:
	stdout.write(f'{len(req) - 1}\n')
	pointer = 0
	for i in range(len(req) - 1):
		stdout.write(f'{remove[pointer][0]} {remove[pointer][1]} {req[i]} {req[i + 1]}\n')
		pointer += 1


class SNM:

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

	def find(self, v):
		if self.par[v] == v:
			return v
		ANS = self.find(self.par[v])
		self.par[v] = ANS
		return ANS

	def join(self, v, u):
		pr1 = self.find(v)
		pr2 = self.find(u)
		if pr1 == pr2:
			return 0
		if self.sizes[pr1] > self.sizes[pr2]:
			self.par[pr2] = pr1
		else:
			self.par[pr1] = pr2
		return 1
N = int(input())
L = []
SN = SNM(N)
for i in range(N - 1):
	(A, B) = map(int, input().split())
	L.append([A - 1, B - 1])
BadEdges = []
for i in L:
	if not SN.join(i[0], i[1]):
		BadEdges.append((i[0], i[1]))
print(len(BadEdges))
hk = 0
for i in range(1, N):
	if SN.find(0) != SN.find(i):
		SN.join(0, i)
		print(BadEdges[hk][0] + 1, BadEdges[hk][1] + 1, 1, i + 1)
		hk += 1


n = int(input())
li = []
for i in range(n - 1):
	(x, y) = map(int, input().split())
	li.append([x, y])
parent = [i for i in range(n + 1)]
close = []
bild = []

def root(t):
	while parent[t] != t:
		t = parent[t]
	return t

def union(s, d):
	p = root(s)
	q = root(d)
	if p < q:
		parent[q] = p
	else:
		parent[p] = q

def roads():
	for i in li:
		if root(i[0]) == root(i[1]):
			close.append([i[0], i[1]])
		else:
			union(i[0], i[1])
	for i in range(2, n + 1):
		if root(i) != root(1):
			union(1, i)
			bild.append([1, i])
roads()
print(len(bild))
for i in range(len(close)):
	print(close[i][0], close[i][1], bild[i][0], bild[i][1])


class dsu:

	def __init__(self):
		self.parent = [0] * 10 ** 6
		self.size = [0] * 10 ** 6

	def make_set(self, v):
		self.parent[v] = v
		self.size[v] = 1

	def union_set(self, a, b):
		a = self.find_set(a)
		b = self.find_set(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 find_set(self, v):
		if v == self.parent[v]:
			return v
		self.parent[v] = self.find_set(self.parent[v])
		return self.parent[v]
n = int(input())
x = dsu()
for i in range(1, n + 1):
	x.make_set(i)
p = []
for i in range(n - 1):
	(a, b) = map(int, input().split())
	if x.find_set(a) == x.find_set(b):
		p.append([a, b])
	else:
		x.union_set(a, b)
tt = set()
for i in range(1, n + 1):
	tt.add(x.find_set(i))
tt = list(tt)
print(len(tt) - 1)
for i in range(1, len(tt)):
	print(*p[i - 1] + [tt[i], tt[i - 1]])


import sys
import math

def ii():
	return int(input())

def il():
	return input().split(' ')

def ili():
	return [int(i) for i in input().split(' ')]

def ilis():
	return (int(i) for i in input().split(' '))

def ip():
	return input()

def op(*args, **kwargs):
	print(*args, **kwargs)
	sys.stdout.flush()

def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)

def extgcd(a, b, x=0, y=0):
	if b == 0:
		return (a, 1, 0)
	(d, m, n) = extgcd(b, a % b, x, y)
	return (d, n, m - a // b * n)

class UFS:

	def __init__(self, n):
		self.data = [i for i in range(n)]
		self.size = [1] * n
		self.cnt = n

	def find(self, m):
		if self.data[m] == m:
			return m
		ancestor = self.find(self.data[m])
		self.data[m] = ancestor
		return ancestor

	def union(self, a, b):
		ancestor_a = self.find(a)
		ancestor_b = self.find(b)
		if ancestor_a == ancestor_b:
			return
		if self.size[ancestor_a] > self.size[ancestor_b]:
			self.data[ancestor_b] = ancestor_a
			self.size[ancestor_a] += ancestor_b
		else:
			self.data[ancestor_a] = ancestor_b
			self.size[ancestor_b] += ancestor_a
		self.cnt -= 1

	def query(self, a, b):
		return self.find(a) == self.find(b)

def main():
	n = ii()
	ufs = UFS(n + 1)
	dels = []
	for i in range(n - 1):
		(u, v) = ilis()
		if ufs.query(u, v):
			dels.append((u, v))
		else:
			ufs.union(u, v)
	for i in range(n):
		ufs.find(i + 1)
	roots = list(set(ufs.data))
	roots.pop(0)
	unum = len(roots) - 1
	op(unum)
	for num in range(unum):
		op(dels[num][0], dels[num][1], roots[0], roots[num + 1])
main()


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
n = iinp()
pars = [i for i in range(n + 1)]
to_close = []
to_open = []
for i in range(n - 1):
	(x, y) = mp()
	if pars[x] == pars[y]:
		to_close.append((x, y))
	else:
		for j in range(1, n + 1):
			if y != j and pars[j] == pars[y]:
				pars[j] = pars[x]
		pars[y] = pars[x]
s = set([pars[1]])
for i in range(2, n + 1):
	if pars[i] not in s:
		to_open.append((1, i))
		s.add(pars[i])
l = len(to_close)
print(l)
for i in range(l):
	print(to_close[i][0], to_close[i][1], to_open[i][0], to_open[i][1])


import math
import sys
n = int(input())
g = []
fa = [i for i in range(0, n + 1)]
value = [0 for i in range(0, n + 1)]
num = [1 for i in range(0, n + 1)]
vec = []

def getfa(x):
	if x == fa[x]:
		return x
	else:
		root = getfa(fa[x])
		fa[x] = root
		return fa[x]
for i in range(n - 1):
	(u, v) = map(int, list(input().strip().split(' ')))
	g.append([u, v])
for edge in g:
	u = edge[0]
	v = edge[1]
	f1 = getfa(u)
	f2 = getfa(v)
	if f1 > f2:
		tmp = f1
		f1 = f2
		f2 = tmp
	if f1 != f2:
		fa[f2] = f1
		value[f1] += value[f2] + 1
		num[f1] += num[f2]
	elif f1 == f2:
		value[f1] += 1
		vec.append((u, v))
ans = 0
pos = -1
op = []
op1 = []
for i in range(1, n + 1):
	if i == getfa(fa[i]):
		ans += 1
		if num[i] > value[i]:
			op.append(i)
		if num[i] <= value[i]:
			op1.append(i)
print(ans - 1)
if len(vec) == 0:
	exit(0)
now = 0
cnt = 0
siz = len(op)
for i in range(0, len(vec)):
	if now != siz - 1:
		print(vec[i][0], vec[i][1], op[now], op[now + 1])
		now += 1
	else:
		print(vec[i][0], vec[i][1], op1[cnt], op[now])
		cnt += 1


n = int(input())
parent = [i for i in range(n + 1)]
size = [1 for _ in range(n + 1)]

def paren(x):
	while x != parent[x]:
		x = parent[x]
	return parent[x]
closingroad = []

def union(x, y):
	a = paren(x)
	b = paren(y)
	if a != b:
		if size[a] > size[b]:
			parent[b] = a
			size[a] += size[b]
		else:
			parent[a] = b
			size[b] += size[a]
	else:
		closingroad.append([x, y])
for _ in range(n - 1):
	(x, y) = map(int, input().strip().split(' '))
	union(x, y)
count = 0
li = set()
for i in range(1, n + 1):
	li.add(paren(i))
count = len(li) - 1
li = list(li)
print(count)
for i in range(count):
	print(closingroad[i][0], closingroad[i][1], li[i], li[i + 1])


class DSU:

	def __init__(self, N):
		self.sz = [1] * N
		self.parent = list(range(N))
		self.redundant = []

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

	def union(self, a, b):
		(p1, p2) = (self.find(a), self.find(b))
		if p1 == p2:
			self.redundant.append((a, b))
		elif self.sz[p1] < self.sz[p2]:
			self.parent[p1] = p2
			self.sz[p2] += self.sz[p1]
		else:
			self.parent[p2] = p1
			self.sz[p1] += self.sz[p2]
N = int(input())
dsu = DSU(N)
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	dsu.union(a, b)
s = set()
for i in range(N):
	s.add(dsu.find(i))
s = list(s)
print(len(s) - 1)
for (x, y) in zip(s, s[1:]):
	(a, b) = dsu.redundant.pop()
	print('{} {} {} {}'.format(a + 1, b + 1, x + 1, y + 1))


parent = [0 for i in range(1001)]
rank = [0 for i in range(1001)]

def make_set(num):
	parent[num] = num
	rank[num] = 1

def find_set(a):
	if parent[a] == a:
		return a
	parent[a] = find_set(parent[a])
	return parent[a]

def union_sets(a, b):
	x = find_set(a)
	y = find_set(b)
	if x != y:
		if rank[x] < rank[y]:
			(x, y) = (y, x)
		parent[y] = x
		if rank[x] == rank[y]:
			rank[x] += 1
n = int(input())
for i in range(1, n + 1):
	make_set(i)
to_remove = []
for i in range(1, n):
	[a, b] = list(map(int, input().split()))
	if find_set(a) == find_set(b):
		to_remove.append((a, b))
	else:
		union_sets(a, b)
is_parent = [0 for i in range(1001)]
parents = []
for i in range(1, n + 1):
	p = find_set(i)
	if is_parent[p] == 0:
		is_parent[p] = 1
		parents.append(p)
print(len(to_remove))
for i in range(len(to_remove)):
	print(to_remove[i][0], to_remove[i][1], parents[i], parents[i + 1])