Ramesses knows a lot about problems involving trees (undirected connected graphs without cycles)!

He created a new useful tree decomposition, but he does not know how to construct it, so he asked you for help!

The decomposition is the splitting the edges of the tree in some simple paths in such a way that each two paths have at least one common vertex. Each edge of the tree should be in exactly one path.

Help Remesses, find such a decomposition of the tree or derermine that there is no such decomposition.


-----Input-----

The first line contains a single integer $n$ ($2 \leq n \leq 10^{5}$) the number of nodes in the tree.

Each of the next $n - 1$ lines contains two integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$) — the edges of the tree. It is guaranteed that the given edges form a tree.


-----Output-----

If there are no decompositions, print the only line containing "No".

Otherwise in the first line print "Yes", and in the second line print the number of paths in the decomposition $m$. 

Each of the next $m$ lines should contain two integers $u_i$, $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$) denoting that one of the paths in the decomposition is the simple path between nodes $u_i$ and $v_i$. 

Each pair of paths in the decomposition should have at least one common vertex, and each edge of the tree should be presented in exactly one path. You can print the paths and the ends of each path in arbitrary order.

If there are multiple decompositions, print any.


-----Examples-----
Input
4
1 2
2 3
3 4

Output
Yes
1
1 4

Input
6
1 2
2 3
3 4
2 5
3 6

Output
No

Input
5
1 2
1 3
1 4
1 5

Output
Yes
4
1 2
1 3
1 4
1 5



-----Note-----

The tree from the first example is shown on the picture below: [Image] The number next to each edge corresponds to the path number in the decomposition. It is easy to see that this decomposition suits the required conditions.

The tree from the second example is shown on the picture below: [Image] We can show that there are no valid decompositions of this tree.

The tree from the third example is shown on the picture below: [Image] The number next to each edge corresponds to the path number in the decomposition. It is easy to see that this decomposition suits the required conditions.

Source: codeforces | Difficulty: MEDIUM
Tags: Tree algorithms

Implementation


Solutions:
n = int(input())
deg = [0] * 100005
leaves = []
for i in range(1, n):
	(a, b) = map(int, input().split())
	deg[a] += 1
	deg[b] += 1
cnt = 0
mxdeg = 0
root = 0
for j in range(1, n + 1):
	if deg[j] > mxdeg:
		mxdeg = deg[j]
		root = j
	if deg[j] == 1:
		leaves.append(j)
	if deg[j] > 2:
		cnt += 1
if cnt > 1:
	print('No')
	exit()
print('Yes')
m = 0
for it in leaves:
	if it != root:
		m += 1
print(m)
for it2 in leaves:
	if it2 != root:
		print(root, it2)


import os
import sys
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))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	pass

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def lts(l):
	s = ''.join(map(str, l))
	return s

def stl(s):
	l = list(s)
	return l

def sq(a, target, arr=[]):
	s = sum(arr)
	if s == target:
		return arr
	if s >= target:
		return
	for i in range(len(a)):
		n = a[i]
		remaining = a[i + 1:]
		ans = sq(remaining, target, arr + [n])
		if ans:
			return ans

def SieveOfEratosthenes(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			cnt += 1
	return cnt

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)
mod = int(1000000000.0) + 7
import math

def deep(node):
	visited[node - 1] = 1
	if len(d[node]) == 1:
		return node
	for c in d[node]:
		if visited[c - 1] != 1:
			return deep(c)
n = int(input())
d = {}
for i in range(n - 1):
	(u, v) = map(int, input().split())
	d.setdefault(u, []).append(v)
	d.setdefault(v, []).append(u)
node = 1
for key in d:
	if len(d[key]) > len(d[node]):
		node = key
ans = []
visited = [0] * n
visited[node - 1] = 1
for c in d[node]:
	while True:
		visited[c - 1] = 1
		if len(d[c]) == 1:
			ans.append([node, c])
			break
		for child in d[c]:
			if visited[child - 1] != 1:
				c = child
				break
if sum(visited) == n:
	print('Yes')
	print(len(ans))
	for c in ans:
		print(*c)
else:
	print('No')


count = int(input())
tree = {}
for _ in range(count - 1):
	edge = input().split()
	if edge[0] in tree:
		tree[edge[0]].append(edge[1])
	else:
		tree[edge[0]] = [edge[1]]
	if edge[1] in tree:
		tree[edge[1]].append(edge[0])
	else:
		tree[edge[1]] = [edge[0]]
centroid = []
leaves = []
for (key, adj) in tree.items():
	if len(adj) == 1:
		leaves.append(key)
	elif len(adj) >= 3 and len(centroid) == 0:
		centroid.append(key)
	elif len(adj) >= 3 and len(centroid) > 0:
		print('No')
		break
else:
	print('Yes')
	if len(centroid) == 0:
		print(1)
		print(leaves[0] + ' ' + leaves[1])
	else:
		print(len(leaves))
		for leaf in leaves:
			print(leaf + ' ' + centroid[0])


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

def bfs(start, graph, explored):
	queue = deque([start])
	visited = {start}
	ele = 0
	while queue:
		node = queue.popleft()
		explored.add(node)
		neighbours = graph[node]
		cnt = 0
		for neighbour in neighbours:
			if neighbour not in visited and neighbour not in explored:
				cnt += 1
		if e[0] == 0 and cnt != 1:
			ele = node
			break
		else:
			for neighbour in neighbours:
				if neighbour not in visited:
					queue.append(neighbour)
					visited.add(neighbour)
	return ele
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

@bootstrap
def solve(i):
	cnt = 0
	visited.add(i)
	for k in graph[i]:
		if k not in visited:
			cnt += 1
	if cnt >= 1:
		for k in graph[i]:
			if k not in visited:
				yield solve(k)
				break
	else:
		r[0] = i
	yield
n = int(input())
graph = {}
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	if a in graph:
		graph[a].append(b)
	else:
		graph[a] = [b]
	if b in graph:
		graph[b].append(a)
	else:
		graph[b] = [a]
roots = []
visited = set()
ele = 0
e = [ele]
for i in graph:
	if len(graph[i]) == 1:
		roots.append(i)
x = roots[0]
ans = []
ele = bfs(x, graph, visited)
ans.append((str(x), str(ele)))
for i in graph[ele]:
	r = [0]
	if i not in visited:
		y = solve(i)
		ans.append([str(r[0]), str(ele)])
if len(visited) == n:
	sys.stdout.write('Yes\n')
	q = str(len(ans))
	sys.stdout.write(q + '\n')
	for i in ans:
		e = ' '.join(i)
		sys.stdout.write(e + '\n')
else:
	sys.stdout.write('No\n')


from collections import Counter
n = int(input())
tree = []
for i in range(n - 1):
	tree.extend(list(map(int, input().split())))
ans = Counter(tree)
if ans.most_common(2)[1][1] > 2:
	print('No')
else:
	print('Yes')
	if n == 2:
		print(1)
		print('1 2')
	elif ans.most_common(1)[0][1] == 2:
		print(1)
		print(ans.most_common()[-2][0], ans.most_common()[-1][0])
	else:
		center = ans.most_common(1)[0][0]
		kraya = [n[0] for n in ans.most_common() if n[1] == 1]
		print(len(kraya))
		for i in kraya:
			print(center, i)


n = int(input().strip())
degs = [0 for _ in range(n)]
for _ in range(n - 1):
	[u, v] = map(int, input().strip().split())
	degs[u - 1] += 1
	degs[v - 1] += 1
ni = [None, [], [], []]
for (v, d) in enumerate(degs):
	dd = min(d, 3)
	ni[dd].append(v)
if len(ni[3]) > 1:
	print('No')
elif len(ni[3]) == 1:
	print('Yes')
	print(len(ni[1]))
	u = ni[3][0]
	for v in ni[1]:
		print(u + 1, v + 1)
else:
	print('Yes')
	print(1)
	print(ni[1][0] + 1, ni[1][1] + 1)


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

def getTransIntList(n):
	first = getIntList()
	m = len(first)
	result = [[0] * n for _ in range(m)]
	for i in range(m):
		result[i][0] = first[i]
	for j in range(1, n):
		curr = getIntList()
		for i in range(m):
			result[i][j] = curr[i]
	return result
n = int(input())

def solve():
	nearVerts = [0] * (n + 1)
	for i in range(n - 1):
		(u, v) = getIntList()
		nearVerts[u] += 1
		nearVerts[v] += 1
	result = -1
	count3 = 0
	ways = []
	mainVert = -1
	oneVerts = []
	for i in range(n + 1):
		nears = nearVerts[i]
		if nears == 1:
			oneVerts.append(i)
			result += 1
		elif nears >= 3:
			mainVert = i
			count3 += 1
			if count3 > 1:
				return (-1, ways)
	ways.append((oneVerts[0], oneVerts[1]))
	for v in oneVerts[2:]:
		ways.append((v, mainVert))
	return (result, ways)
(result, ways) = solve()
if result == -1:
	print('No')
else:
	print('Yes')
	print(result)
	for w in ways:
		print(w[0], w[1])


import sys
input = sys.stdin.readline
n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n - 1)]
deg = [0] * n
for (a, b) in ab:
	deg[a - 1] += 1
	deg[b - 1] += 1
ideg = [(i, deg[i]) for i in range(n)]
ideg.sort(key=lambda k: k[1])
deg2 = [ideg[i][1] for i in range(n)]
if deg2 == [1] * 2 + [2] * (n - 2):
	print('Yes')
	print(1)
	print(ideg[0][0] + 1, ideg[1][0] + 1)
elif deg2[-2] <= 2:
	ans = []
	for i in range(n):
		if deg[i] == 1:
			ans.append((i + 1, ideg[-1][0] + 1))
	print('Yes')
	print(len(ans))
	for (u, v) in ans:
		print(u, v)
else:
	print('No')


def readline():
	return tuple(map(int, input().split()))

def readlines(count):
	return (readline() for __ in range(count))

def main():
	(n,) = readline()
	degree = [0] * n
	root = None
	for (a, b) in readlines(n - 1):
		degree[a - 1] += 1
		degree[b - 1] += 1
	for (x, d) in enumerate(degree, start=1):
		if d > 2:
			if root is None:
				root = x
			else:
				print('No')
				return
	if root is None:
		root = 1
	ways = [i for (i, d) in enumerate(degree, start=1) if d == 1 and i != root]
	print('Yes')
	print(len(ways))
	print('\n'.join(map(f'{root} {{}}'.format, ways)))
main()


import sys
from sys import stdin, stdout
n = int(stdin.readline())
leafs = []
posroot = -1
pos2 = -1
if n == 2:
	print('Yes')
	print(1)
	print(1, 2)
	sys.exit()
edges = [[] for i in range(n)]
for i in range(n - 1):
	(x, y) = map(int, stdin.readline().split())
	x -= 1
	y -= 1
	edges[x].append(y)
	edges[y].append(x)
for i in range(n):
	if len(edges[i]) == 1:
		leafs.append(i)
	elif len(edges[i]) > 2:
		if posroot != -1:
			print('No')
			sys.exit()
		else:
			posroot = i
	elif pos2 == -1:
		pos2 = i
if posroot == -1:
	posroot = pos2
print('Yes')
s = ''
print(len(leafs))
for i in range(len(leafs)):
	s += str(posroot + 1) + ' ' + str(leafs[i] + 1) + '\n'
print(s[:-1])


import sys, math
n = int(input())
tree = [[] for i in range(n)]
degree = [0] * n
for i in range(n - 1):
	(u, v) = map(int, sys.stdin.readline().split())
	tree[u - 1].append(v)
	tree[v - 1].append(u)
	degree[u - 1] += 1
	degree[v - 1] += 1
x = 0
for i in range(n):
	if degree[i] >= 3:
		x += 1
if x == 0:
	print('Yes')
	a = 0
	b = 0
	flag = True
	for i in range(n):
		if degree[i] == 1 and flag:
			a = i + 1
			flag = False
		elif degree[i] == 1:
			b = i + 1
	print(1)
	print(a, b)
elif x > 1:
	print('No')
else:
	print('Yes')
	max_degree = degree.index(max(degree)) + 1
	ans = []
	for i in range(n):
		if degree[i] == 1:
			ans.append([max_degree, i + 1])
	print(len(ans))
	for i in range(len(ans)):
		print(*ans[i])


import sys
import filecmp
import math
FILE_IO = False
CURR_PATH = []
list_of_connections = [[] for _ in range(100001)]

def dfs(vertex):
	(visited, stack) = (set(), [vertex])
	while stack:
		vertex = stack.pop()
		if vertex not in visited:
			visited.add(vertex)
			stack.extend(set(list_of_connections[vertex]) - visited)
			if len(set(list_of_connections[vertex]) - visited) == 0:
				CURR_PATH.append(vertex)
if FILE_IO:
	input_stream = open('input_test.txt')
	sys.stdout = open('current_output2.txt', 'w')
else:
	input_stream = sys.stdin
n = int(input_stream.readline())
for _ in range(n - 1):
	input_list = input_stream.readline().split()
	(start, end) = (int(input_list[0]), int(input_list[1]))
	list_of_connections[start].append(end)
	list_of_connections[end].append(start)
max_edges = None
max_less_then_3 = None
no = False
for (ind, edges) in enumerate(list_of_connections):
	current_len = len(edges)
	if current_len > 2:
		if max_less_then_3 is not None:
			print('No')
			exit()
		else:
			max_less_then_3 = ind
if max_less_then_3 is None:
	max_less_then_3 = 1
print('Yes')
root = max_less_then_3
paths = []
visited = [False] * 100001
dfs(root)
print(len(CURR_PATH))
for node in CURR_PATH:
	print(str(root) + ' ' + str(node))


n = int(input())
flag = True
f = [0] * (n - 1)
t = [0] * (n - 1)
co = [0] * n
for i in range(n - 1):
	(f[i], t[i]) = map(int, input().split())
	co[f[i] - 1] += 1
	co[t[i] - 1] += 1
mid = 0
en = []
for i in range(n):
	if co[i] == 1:
		en.append(i + 1)
	elif co[i] > 2:
		if mid == 0:
			mid = i + 1
		else:
			print('No')
			flag = False
			break
if flag:
	print('Yes')
	if mid != 0:
		print(len(en))
		for i in range(len(en)):
			print(mid, en[i])
	else:
		print(1)
		print(en[0], en[1])


from math import *

def main():
	n = int(input())
	Edge = [[] for i in range(n + 3)]
	for i in range(1, n):
		(u, v) = map(int, input().split())
		Edge[u].append(v)
		Edge[v].append(u)
	cnt = 0
	ComPo = []
	for i in range(1, n + 1):
		if len(Edge[i]) > 2:
			cnt += 1
			ComPo.append(i)
	if cnt > 1:
		print('No')
	else:
		print('Yes')
		if cnt == 0:
			print(1)
			for i in range(1, n + 1):
				if len(Edge[i]) == 1:
					ComPo.append(i)
			print(ComPo[0], ComPo[1])
		else:
			Ans = []
			for i in range(1, n + 1):
				if len(Edge[i]) == 1:
					Ans.append(i)
			print(len(Ans))
			for i in Ans:
				print(ComPo[0], i)
try:
	while True:
		main()
except EOFError:
	pass


a = int(input())
s = {}
ans = 0
for i in range(a - 1):
	(v, c) = map(int, input().split())
	if v in s:
		s[v].append(c)
	else:
		s[v] = [c]
	if c in s:
		s[c].append(v)
	else:
		s[c] = [v]
c = 0
for i in range(1, a + 1):
	if len(s[i]) > 2:
		c += 1
		ans = i
if c > 1:
	print('No')
elif c == 0:
	print('Yes')
	print(1)
	for i in s:
		if len(s[i]) == 1:
			print(i, end=' ')
else:
	print('Yes')
	print(len(s[ans]))
	k = []
	for i in s:
		if len(s[i]) == 1:
			k.append(i)
	for i in k:
		print(min(ans, i), max(ans, i))


import sys

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

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

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))
n = iinput()
d = {}
for i in range(n - 1):
	(u, v) = rinput()
	d.setdefault(u, []).append(v)
	d.setdefault(v, []).append(u)
node = 1
for key in d:
	if len(d[key]) > len(d[node]):
		node = key
ans = []
visited = [0] * n
visited[node - 1] = 1
for c in d[node]:
	while True:
		visited[c - 1] = 1
		if len(d[c]) == 1:
			ans.append([node, c])
			break
		for child in d[c]:
			if visited[child - 1] != 1:
				c = child
				break
if sum(visited) == n:
	print('Yes')
	print(len(ans))
	for c in ans:
		print(*c)
else:
	print('No')


N = int(input())
cnt = [0] * N
G = [[] for i in range(N)]
rec = []
for i in range(N - 1):
	(a, b) = map(int, input().split())
	cnt[a - 1] += 1
	cnt[b - 1] += 1
rec = []
num = 0
root = 0
for i in range(N):
	if cnt[i] > 2:
		num += 1
		root = i
	elif cnt[i] == 1:
		rec.append(i)
if num >= 2:
	print('No')
elif num == 0:
	print('Yes')
	print(1)
	print(rec[0] + 1, rec[1] + 1)
else:
	print('Yes')
	print(len(rec))
	for i in range(len(rec)):
		print('{} {}'.format(root + 1, rec[i] + 1))


n = int(input())
d = {}
for i in range(n - 1):
	(a, b) = map(int, input().split())
	(d[a], d[b]) = (d.get(a, 0) + 1, d.get(b, 0) + 1)
root = []
lev = []
for (a, b) in d.items():
	if b > 2:
		root.append(a)
	if b == 1:
		lev.append(a)
if len(root) > 1:
	print('No')
elif len(root) == 0:
	print('Yes')
	print('1')
	print(*lev)
else:
	print('Yes')
	print(d[root[0]])
	for a in lev:
		print(root[0], a)


def main():
	n = int(input())
	neis = [[] for _ in range(n + 1)]
	common = None
	max_deg = 0
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		neis[u].append(v)
		neis[v].append(u)
		if len(neis[u]) > max_deg:
			max_deg = len(neis[u])
			common = u
		if len(neis[v]) > max_deg:
			max_deg = len(neis[v])
			common = v

	def get_path(start, cur):
		path = [start]
		while True:
			if len(neis[cur]) == 1:
				return (True, cur)
			else:
				pre = path[-1]
				vers = set(neis[cur])
				vers.remove(pre)
				if len(vers) > 1:
					return (False, None)
				else:
					path.append(cur)
					cur = vers.pop()

	def fake_dfs(common):
		nonlocal neis
		paths = []
		for nei in neis[common]:
			(is_path, end_ver) = get_path(common, nei)
			if is_path:
				paths.append((common, end_ver))
			else:
				print('No')
				return
		print('Yes')
		print(len(paths))
		for (u, v) in paths:
			print(u, v)
	fake_dfs(common)
main()


n = int(input())
d = [0] * 100010
l = []
le = []
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	d[u] += 1
	d[v] += 1
	l.append(u)
	l.append(v)
r = 0
for i in range(1, max(l) + 1):
	if d[i] == 1:
		le.append(i)
	if d[i] > 2:
		if not r:
			r = i
		else:
			print('No')
			exit(0)
print('Yes')
if not r:
	print(1)
	print(min(le), max(le))
else:
	x = len(le)
	print(x)
	le.sort()
	for i in range(1, x + 1):
		print(r, le[i - 1])


from sys import stdin, stdout
import heapq
import cProfile, math
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect, bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
import sys
sys.setrecursionlimit(10 ** 6)
threading.stack_size(2 ** 27)
fac_warm_up = False
printHeap = str()
memory_constrained = False
P = 10 ** 9 + 7

class MergeFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n
		self.lista = [[_] for _ in range(n)]

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]
		self.lista[a] += self.lista[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def display(string_to_print):
	stdout.write(str(string_to_print) + '\n')

def prime_factors(n):
	factors = dict()
	for i in range(2, math.ceil(math.sqrt(n)) + 1):
		while n % i == 0:
			if i in factors:
				factors[i] += 1
			else:
				factors[i] = 1
			n = n // i
	if n > 2:
		factors[n] = 1
	return factors

def all_factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def fibonacci_modP(n, MOD):
	if n < 2:
		return 1
	return (cached_fn(fibonacci_modP, (n + 1) // 2, MOD) * cached_fn(fibonacci_modP, n // 2, MOD) + cached_fn(fibonacci_modP, (n - 1) // 2, MOD) * cached_fn(fibonacci_modP, (n - 2) // 2, MOD)) % MOD

def factorial_modP_Wilson(n, p):
	if p <= n:
		return 0
	res = p - 1
	for i in range(n + 1, p):
		res = res * cached_fn(InverseEuler, i, p) % p
	return res

def binary(n, digits=20):
	b = bin(n)[2:]
	b = '0' * (digits - len(b)) + b
	return b

def is_prime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	if n % 3 == 0:
		return False
	i = 5
	w = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True

def generate_primes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	return prime
factorial_modP = []

def warm_up_fac(MOD):
	global factorial_modP, fac_warm_up
	if fac_warm_up:
		return
	factorial_modP = [1 for _ in range(fac_warm_up_size + 1)]
	for i in range(2, fac_warm_up_size):
		factorial_modP[i] = factorial_modP[i - 1] * i % MOD
	fac_warm_up = True

def InverseEuler(n, MOD):
	return pow(n, MOD - 2, MOD)

def nCr(n, r, MOD):
	global fac_warm_up, factorial_modP
	if not fac_warm_up:
		warm_up_fac(MOD)
		fac_warm_up = True
	return factorial_modP[n] * (pow(factorial_modP[r], MOD - 2, MOD) * pow(factorial_modP[n - r], MOD - 2, MOD) % MOD) % MOD

def test_print(*args):
	if testingMode:
		print(args)

def display_list(list1, sep=' '):
	stdout.write(sep.join(map(str, list1)) + '\n')

def display_2D_list(li):
	for i in li:
		print(i)

def prefix_sum(li):
	sm = 0
	res = []
	for i in li:
		sm += i
		res.append(sm)
	return res

def get_int():
	return int(stdin.readline().strip())

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

def get_list():
	return list(map(int, stdin.readline().split()))
memory = dict()

def clear_cache():
	global memory
	memory = dict()

def cached_fn(fn, *args):
	global memory
	if args in memory:
		return memory[args]
	else:
		result = fn(*args)
		memory[args] = result
		return result

def ncr(n, r):
	return math.factorial(n) / (math.factorial(n - r) * math.factorial(r))

def binary_search(i, li):
	fn = lambda x: li[x] - x // i
	x = -1
	b = len(li)
	while b >= 1:
		while b + x < len(li) and fn(b + x) > 0:
			x += b
		b = b // 2
	return x
TestCases = False
fac_warm_up_size = 10 ** 5 + 100
optimise_for_recursion = False

def main():
	n = get_int()
	ngbrs = [[] for x in range(n)]
	for i in range(n - 1):
		(x, y) = get_tuple()
		(x, y) = (x - 1, y - 1)
		ngbrs[x].append(y)
		ngbrs[y].append(x)
	one = []
	morethantwo = []
	for (i, li) in enumerate(ngbrs):
		if len(li) == 1:
			one.append(i)
		elif len(li) > 2:
			morethantwo.append(i)
	if len(morethantwo) == 0:
		print('Yes')
		print(1)
		print(one[0] + 1, one[1] + 1)
	elif len(morethantwo) > 1:
		print('No')
	else:
		print('Yes')
		print(len(one))
		for i in one:
			print(i + 1, morethantwo[0] + 1)
if TestCases:
	for i in range(get_int()):
		main()
else:
	main() if not optimise_for_recursion else threading.Thread(target=main).start()


from sys import stdin, stdout, setrecursionlimit
import heapq
from math import gcd, ceil, sqrt
from collections import Counter, deque
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
setrecursionlimit(100000)
mod = 1000000007
n = ii1()
deg = [0] * n
for i in range(n - 1):
	(a, b) = iia()
	deg[a - 1] += 1
	deg[b - 1] += 1
count = node = 0
ans = []
for i in range(n):
	if deg[i] > 2:
		count += 1
		node = i
	elif deg[i] == 1:
		ans.append(i)
if count > 1:
	print('No')
else:
	print('Yes')
	print(deg[node])
	for i in ans:
		if node != i:
			print(node + 1, i + 1)


d = {}
n = int(input())
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	d[a] = d.get(a, 0) + 1
	d[b] = d.get(b, 0) + 1
zz = list(filter(lambda x: d[x] > 2, d))
z = len(zz)
y = list(filter(lambda x: d[x] == 1, d))
if z > 1:
	print('No')
elif z == 0:
	print('Yes')
	print(1)
	print(*y)
else:
	print('Yes')
	print(len(y))
	for v in y:
		print(zz[0], v)


import collections

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

def getTransIntList(n):
	first = getIntList()
	m = len(first)
	result = [[0] * n for _ in range(m)]
	for i in range(m):
		result[i][0] = first[i]
	for j in range(1, n):
		curr = getIntList()
		for i in range(m):
			result[i][j] = curr[i]
	return result
n = int(input())

def solve():
	nearVerts = [0] * (n + 1)
	for i in range(n - 1):
		(u, v) = getIntList()
		nearVerts[u] += 1
		nearVerts[v] += 1
	result = -1
	count3 = 0
	ways = []
	mainVert = -1
	v1 = -1
	v2 = -1
	oneVersts = collections.deque()
	for i in range(n + 1):
		nears = nearVerts[i]
		if nears == 1:
			result += 1
			oneVersts.append(i)
		elif nears >= 3:
			mainVert = i
			count3 += 1
			if count3 > 1:
				result = -1
				break
	if result == -1:
		print('No')
	else:
		print('Yes')
		print(result)
		v1 = oneVersts.pop()
		v2 = oneVersts.pop()
		print(v1, v2)
		l = len(oneVersts)
		for _ in range(l):
			print(oneVersts.pop(), mainVert)
solve()


n = int(input())
ind = [0] * (n + 1)
cnt = 0
for i in range(n - 1):
	(u, v) = map(int, input().split())
	ind[u] += 1
	ind[v] += 1
ok = sum((ind[i] > 2 for i in range(1, n + 1))) < 2
if not ok:
	print('No')
	exit()
print('Yes')
centre = ind.index(max(ind))
leaf = []
for i in range(1, n + 1):
	if ind[i] == 1:
		leaf.append(i)
if max(ind) == 2 or n == 2:
	print(1)
	print(leaf[0], leaf[1])
else:
	print(len(leaf))
	for i in leaf:
		print(*[centre, i])


import os, sys
from io import BytesIO, IOBase

def main():
	n = rint()
	deg = [0] * n
	if n == 2:
		exit(print(f'Yes\n1\n1 2'))
	for i in range(n - 1):
		(u, v) = rints()
		deg[u - 1] += 1
		deg[v - 1] += 1
	ix = deg.index(max(deg))
	if deg[ix] < 3 or deg.count(1) + deg.count(2) == n - 1:
		print(f'Yes\n{deg.count(1)}')
		for i in range(n):
			if deg[i] == 1:
				print(i + 1, ix + 1)
	else:
		print('No')

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')
BUFSIZE = 8192
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
rstr = lambda : input().strip()
rstrs = lambda : [str(x) for x in input().split()]
rstr_2d = lambda n: [rstr() for _ in range(n)]
rint = lambda : int(input())
rints = lambda : [int(x) for x in input().split()]
rint_2d = lambda n: [rint() for _ in range(n)]
rints_2d = lambda n: [rints() for _ in range(n)]
ceil1 = lambda a, b: (a + b - 1) // b
main()


n = int(input())
g = [0 for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	g[a - 1] += 1
	g[b - 1] += 1
q = 0
k = 0
kind = 0
m = 0
for i in range(n):
	if g[i] == 1:
		m += 1
	if g[i] > 2:
		if g[i] > k:
			kind = i
			k = g[i]
		q += 1
if q > 1:
	print('No')
else:
	print('Yes')
	if k > 2:
		print(m)
		for i in range(n):
			if g[i] == 1:
				print(kind + 1, i + 1)
	else:
		print(1)
		for i in range(n):
			if g[i] == 1:
				print(i + 1, end=' ')


n = int(input())
if n == 2:
	print('Yes\n1\n1 2')
	exit(0)
deg = [0] * n
for i in range(1, n):
	[a, b] = [int(x) for x in input().split()]
	deg[a - 1] += 1
	deg[b - 1] += 1
leaf = []
for i in range(n):
	if deg[i] == 1:
		leaf.append(i)
cnt = len(leaf)
sz = cnt // 2
for i in range(n):
	if deg[i] == cnt:
		print('Yes')
		print(sz + cnt % 2)
		for j in range(sz):
			print(leaf[j] + 1, leaf[j + sz] + 1)
		if cnt % 2 == 1:
			print(leaf[cnt - 1] + 1, i + 1)
		exit(0)
print('No')


import sys
mod = 1000000007

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

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

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

def print_array(a):
	print(' '.join(map(str, a)))

def main():
	n = int(input())
	tree = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(x, y) = get_ints()
		tree[x].append(y)
		tree[y].append(x)
	(cnt, flag, q, intersection) = (0, True, [], 0)
	for i in range(1, n + 1):
		x = len(tree[i])
		if x > 2:
			cnt += 1
			intersection = i
		if cnt > 1:
			flag = False
		if x == 1:
			q.append(i)
	print('Yes' if flag else 'No')
	if flag:
		l = len(q)
		print(l - 1)
		print(q[0], q[1])
		if l > 2:
			q.pop(0)
			q.pop(0)
			for _ in range(l - 2):
				print(intersection, q.pop(0))
main()


n = int(input())
deg = [0 for i in range(1, n + 1)]
odeg = []
for i in range(n - 1):
	[a, b] = [int(i) for i in input().split()]
	deg[a - 1] += 1
	deg[b - 1] += 1
mxdv = 0
mxd = 0
for i in range(n):
	if deg[i] > mxd:
		mxd = deg[i]
		mxdv = i
	if deg[i] == 1:
		odeg.append(i + 1)
mxdv += 1
deg = sorted(deg)
if deg[n - 2] > 2:
	print('No')
else:
	print('Yes')
	c = len(odeg)
	if mxdv in odeg:
		c -= 1
	print(c)
	for v in odeg:
		if v != mxdv:
			print(str(mxdv) + ' ' + str(v))


def main():
	n = int(input())
	deg = [0] * n
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		deg[u - 1] += 1
		deg[v - 1] += 1
	count = 0
	ans = 0
	e = []
	for i in range(n):
		if deg[i] > 2:
			count += 1
			ans = i
		if deg[i] == 1:
			e.append(i)
	if count > 1:
		print('No')
	else:
		print('Yes')
		print(deg[ans])
		for el in e:
			if el != ans:
				print(ans + 1, el + 1)
main()


MOD = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
n = ii()
l = [[] for i in range(n)]
deg = [0] * n
for _ in range(n - 1):
	(a, b) = f()
	l[a - 1].append(b - 1)
	l[b - 1].append(a - 1)
	deg[a - 1] += 1
	deg[b - 1] += 1
mx = max(deg)
if mx == 1:
	print('Yes')
	print(1)
	print(mx + 1, l[mx][0] + 1)
	exit()
if mx > 2 and deg.count(mx) > 1 or any((not i in [mx, 0, 1, 2] for i in deg)):
	exit(print('No'))
ind = deg.index(mx)
path = []
for i in range(n):
	if len(l[i]) == 1:
		path.append(i)
print('Yes')
print(len(path))
for i in path:
	print(ind + 1, i + 1)


from copy import deepcopy
import itertools
from bisect import bisect_left

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

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

def readlist():
	return list(map(int, input().split()))
N = read()
degree = [0] * N
for _ in range(N - 1):
	(a, b) = readmap()
	degree[a - 1] += 1
	degree[b - 1] += 1
more_than_three = 0
for d in degree:
	if d >= 3:
		more_than_three += 1
if more_than_three >= 2:
	print('No')
	quit()
ans = []
if more_than_three == 1:
	for v in range(N):
		if degree[v] >= 3:
			center = v
	for v in range(N):
		if degree[v] == 1:
			ans.append((center + 1, v + 1))
	print('Yes')
	print(len(ans))
	for tup in ans:
		print(tup[0], tup[1])
	quit()
leaf = []
for v in range(N):
	if degree[v] == 1:
		leaf.append(v)
print('Yes')
print(1)
print(leaf[0] + 1, leaf[1] + 1)


import sys
sys.setrecursionlimit(100001)
n = int(input())
adjlist = [[] for i in range(n)]
number = [0 for i in range(n)]
visited = [0 for i in range(n)]
i = 0
while i < n - 1:
	(a, b) = [int(j) for j in input().split()]
	adjlist[a - 1].append(b - 1)
	adjlist[b - 1].append(a - 1)
	i += 1
contador = 0
raiz = 0
i = 0
while i < n:
	if len(adjlist[i]) > 2:
		contador += 1
		raiz = i
	i += 1
if contador <= 1:
	print('Yes')
	folhas = []
	i = 0
	while i < n:
		if len(adjlist[i]) == 1 and i != raiz:
			folhas.append('%d %d' % (raiz + 1, i + 1))
		i += 1
	print(len(folhas))
	print('\n'.join(folhas))
else:
	print('No')


from sys import stdin
all_in = stdin.read().splitlines()
n = int(all_in[0])
if n == 2:
	print('Yes')
	print(1)
	print(1, 2)
	exit()
graph = {i: list() for i in range(1, n + 1)}
for el in all_in[1:n + 1]:
	(a, b) = map(int, el.split())
	graph[a].append(b)
	graph[b].append(a)
sor = sorted(graph.items(), key=lambda x: len(x[1]), reverse=True)
if len(sor[1][1]) > 2:
	print('No')
	exit()
else:
	print('Yes')
	print(len(sor[0][1]))
	ans = list()
	a = sor[0][0]
	for el in sor[0][1]:
		prev = a
		temp = el
		list_ = graph[temp]
		list_.remove(prev)
		while len(list_) != 0:
			prev = temp
			temp = list_[0]
			list_ = graph[temp]
			list_.remove(prev)
		b = temp
		ans.append(f'{a} {b}')
	print('\n'.join(ans))


n = int(input())
orders = [0 for i in range(n)]
for i in range(n - 1):
	(a, b) = [int(j) - 1 for j in input().split()]
	orders[a] += 1
	orders[b] += 1
roots = []
leafs = []
for (i, x) in enumerate(orders):
	if x > 2:
		roots.append(i)
	elif x == 2:
		pass
	elif x == 1:
		leafs.append(i)
	else:
		raise Exception('woww')
if len(roots) > 1:
	print('No')
elif len(roots) == 0:
	print('Yes')
	print('1')
	print(' '.join([str(l + 1) for l in leafs]))
elif len(roots) == 1:
	print('Yes')
	print(str(len(leafs)))
	root = str(roots[0] + 1)
	for l in leafs:
		print(root, str(l + 1))
else:
	raise Exception('woww')


n = int(input())
dic = {}
for i in range(n):
	dic.update({i + 1: 0})
for i in range(n - 1):
	s = input().split()
	dic[int(s[0])] += 1
	dic[int(s[1])] += 1
cl = []
count1 = 0
count2 = 0
count3 = 0
for x in dic.keys():
	if dic[x] == 1:
		count1 += 1
		cl.append(x)
	elif dic[x] == 2:
		count2 += 1
	else:
		count3 += 1
		p = x
if count3 == 0:
	print('Yes')
	print(1)
	print('{} {}'.format(cl[0], cl[1]))
elif count3 == 1:
	print('Yes')
	print(count1)
	for i in range(1, n + 1):
		if i != p and dic[i] == 1:
			print('{} {}'.format(p, i))
else:
	print('No')


n = int(input())
edges = [0 for i in range(n + 1)]
for _ in range(n - 1):
	(x, y) = map(int, input().split())
	edges[x] += 1
	edges[y] += 1
leaves = []
node = None
flag = True
for i in range(1, n + 1):
	if edges[i] == 1:
		leaves.append(i)
	elif edges[i] > 2:
		if not node == None:
			flag = False
			break
		else:
			node = i
if flag:
	print('Yes')
	if node == None:
		print(1)
		print(leaves[0], end=' ')
		print(leaves[1])
	else:
		print(len(leaves))
		for item in leaves:
			print(item, end=' ')
			print(node)
else:
	print('No')


import sys
n = int(sys.stdin.readline())
degree = [0 for i in range(n + 1)]
for i in range(n - 1):
	(u, v) = map(int, sys.stdin.readline().split())
	degree[u] += 1
	degree[v] += 1
ok = sum([int(degree[u] > 2) for u in range(n + 1)]) < 2
if not ok:
	print('No')
	sys.exit()
print('Yes')
maxdeg = max(degree)
center = degree.index(maxdeg)
ends = []
[ends.append(i) for i in range(n + 1) if degree[i] == 1]
if maxdeg == 2 or n == 2:
	print(1)
	print(ends[0], ends[1])
else:
	print(len(ends))
	[print(center, i) for i in ends]


n = int(input())
graph = [[] for i in range(n + 1)]
center = None
should_continue = True
ends = set()
for i in range(n - 1):
	parameters = [int(s) for s in input().split(' ')]
	from_ = parameters[0]
	to = parameters[1]
	graph[from_].append(to)
	graph[to].append(from_)
	if len(graph[from_]) > 2:
		if center and center != from_:
			should_continue = False
			break
		center = from_
	if len(graph[to]) > 2:
		if center and center != to:
			should_continue = False
			break
		center = to
	if len(graph[from_]) == 1:
		ends.add(from_)
	else:
		ends.discard(from_)
	if len(graph[to]) == 1:
		ends.add(to)
	else:
		ends.discard(to)
if not should_continue:
	print('No')
else:
	print('Yes')
	if center == None:
		print('1')
		print(str(ends.pop()) + ' ' + str(ends.pop()))
	else:
		print(len(graph[center]))
		for i in ends:
			print(str(center) + ' ' + str(i))


def tr(f, d, z):
	l = d[z]
	left = []
	ans = {}
	c = 0
	for i in d:
		if len(d[i]) == 1:
			left.append(i)
	if len(left) % 2 == 1:
		c = c + 1
		ans[z] = left[0]
		left.pop(0)
	print(c + len(left) // 2)
	for i in range(len(left) // 2):
		print(left[i], left[i + len(left) // 2])
	if z in ans:
		print(z, ans[z])

def fin(f, s):
	print(1)
	l = []
	for i in d:
		if len(d[i]) == 1:
			l.append(i)
	print(l[0], l[1])
m = int(input())
d = {}
f = {}
for i in range(m - 1):
	(a, b) = map(int, input().split())
	f[a] = b
	if a in d:
		d[a].append(b)
	else:
		d[a] = [b]
	if b in d:
		d[b].append(b)
	else:
		d[b] = [a]
c = 0
n = 0
z = 0
for i in d:
	if len(d[i]) > 2:
		c += 1
		z = i
if c > 1:
	print('No')
else:
	print('Yes')
	if c > 0:
		tr(f, d, z)
	else:
		fin(f, m * (m + 1) // 2)