Let F_k denote the k-th term of Fibonacci sequence, defined as below:

  * F_0 = F_1 = 1
  * for any integer n ≥ 0, F_{n+2} = F_{n+1} + F_n



You are given a tree with n vertices. Recall that a tree is a connected undirected graph without cycles.

We call a tree a Fib-tree, if its number of vertices equals F_k for some k, and at least one of the following conditions holds:

  * The tree consists of only 1 vertex;
  * You can divide it into two Fib-trees by removing some edge of the tree. 



Determine whether the given tree is a Fib-tree or not.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of vertices in the tree.

Then n-1 lines follow, each of which contains two integers u and v (1≤ u,v ≤ n, u ≠ v), representing an edge between vertices u and v. It's guaranteed that given edges form a tree.

Output

Print "YES" if the given tree is a Fib-tree, or "NO" otherwise.

You can print your answer in any case. For example, if the answer is "YES", then the output "Yes" or "yeS" will also be considered as correct answer.

Examples

Input


3
1 2
2 3


Output


YES


Input


5
1 2
1 3
1 4
1 5


Output


NO


Input


5
1 3
1 2
4 5
3 4


Output


YES

Note

In the first sample, we can cut the edge (1, 2), and the tree will be split into 2 trees of sizes 1 and 2 correspondently. Any tree of size 2 is a Fib-tree, as it can be split into 2 trees of size 1.

In the second sample, no matter what edge we cut, the tree will be split into 2 trees of sizes 1 and 4. As 4 isn't F_k for any k, it's not Fib-tree.

In the third sample, here is one possible order of cutting the edges so that all the trees in the process are Fib-trees: (1, 3), (1, 2), (4, 5), (3, 4).

Difficulty: VERY_HARD
Tags: Graph traversal

Complete search

Number theory

Tree algorithms

Divide and conquer
Skill types: Complete search

Starter code:

Solutions:
def main():
	n = int(input())
	graph = [[] for _ in range(n + 1)]
	parent = [-1 for _ in range(n + 1)]
	for _ in range(n - 1):
		(x, y) = map(int, input().split(' '))
		graph[x].append(y)
		graph[y].append(x)
	digraph = [[] for _ in range(n + 1)]
	stack = [1]
	count_order = []
	while stack:
		cur = stack.pop()
		count_order.append(cur)
		for adj in graph[cur]:
			if parent[cur] == adj:
				continue
			stack.append(adj)
			parent[adj] = cur
			digraph[cur].append(adj)
	count = [1 for _ in range(n + 1)]
	while count_order:
		cur = count_order.pop()
		for child in digraph[cur]:
			count[cur] += count[child]
	fib_numbers = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418]
	fib_d = {val: i for (i, val) in enumerate(fib_numbers)}
	fin = [0 for _ in range(n + 1)]

	def rec(cur_root, total_nodes):
		if total_nodes <= 3:
			return True
		elif total_nodes not in fib_d:
			return False
		fib_idx = fib_d[total_nodes]
		search_vals = [fib_numbers[fib_idx - 1], fib_numbers[fib_idx - 2]]
		cut_node = -1
		stack = [cur_root]
		while stack:
			cur_node = stack.pop()
			if count[cur_node] in search_vals:
				cut_node = cur_node
				fin[cut_node] = True
				break
			for adj in digraph[cur_node]:
				if not fin[adj]:
					stack.append(adj)
		if cut_node == -1:
			return False
		cut_node_count = count[cut_node]
		cur_parent = parent[cut_node]
		while cur_parent != -1:
			count[cur_parent] -= cut_node_count
			cur_parent = parent[cur_parent]
		parent[cut_node] = -1
		if count[cur_root] <= count[cut_node]:
			try1 = rec(cur_root, count[cur_root])
			if try1:
				return rec(cut_node, count[cut_node])
		else:
			try1 = rec(cut_node, count[cut_node])
			if try1:
				return rec(cur_root, count[cur_root])
		return False
	print('YES' if rec(1, n) else 'NO')
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')
main()


import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import log, gcd
input = lambda : sys.stdin.buffer.readline()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
fibo = [1, 1]
for i in range(40):
	fibo.append(fibo[-1] + fibo[-2])
fibo_dic = {e: i for (i, e) in enumerate(fibo)}
N = int(input())
edge = [[] for i in range(N)]
for i in range(N - 1):
	(u, v) = mi()
	edge[u - 1].append(v - 1)
	edge[v - 1].append(u - 1)
deq = deque([0])
res = []
size = [0 for i in range(N)]
parent = [-1 for i in range(N)]
while deq:
	v = deq.popleft()
	res.append(v)
	size[v] += 1
	for nv in edge[v]:
		if size[nv] != 1:
			parent[nv] = v
			deq.append(nv)
res = res[::-1]
for v in res:
	for nv in edge[v]:
		if nv != parent[v]:
			size[v] += size[nv]
	if v:
		edge[v].remove(parent[v])
	edge[v] = [nv for nv in edge[v] if nv != parent[v]]
if N not in fibo_dic:
	exit(print('NO'))
k = fibo_dic[N]
Nodes = [(0, k)]
cutted = set()
while Nodes:
	(root, k) = Nodes.pop()
	if size[root] <= 2:
		continue
	cut = (-1, -1)
	stack = [root]
	while stack:
		v = stack.pop()
		for nv in edge[v]:
			if size[nv] == fibo[k - 1] or size[nv] == fibo[k - 2]:
				cut = (v, nv)
				break
			stack.append(nv)
		else:
			continue
		break
	if cut == (-1, -1):
		exit(print('NO'))
	(pv, v) = cut
	edge[pv].remove(v)
	pos = pv
	while True:
		size[pos] -= size[v]
		if parent[pos] != -1 and (parent[pos], pos) not in cutted:
			pos = parent[pos]
		else:
			break
	cutted.add(cut)
	Nodes.append((root, fibo_dic[size[root]]))
	Nodes.append((v, fibo_dic[size[v]]))
print('YES')


import io, os
from collections import deque

def solve(N, edges):
	fib = [1, 1]
	while fib[-1] < N:
		fib.append(fib[-2] + fib[-1])
	fibToIndex = {x: i for (i, x) in enumerate(fib)}
	if N not in fibToIndex:
		return 'NO'
	graph = [[] for i in range(N)]
	for (u, v) in edges:
		graph[u].append(v)
		graph[v].append(u)
	root = 0
	q = [root]
	parent = [-1] * N
	for u in q:
		q += graph[u]
		for v in graph[u]:
			parent[v] = u
			graph[v].remove(u)
	children = graph
	subTreeSize = [-1] * N
	for u in q[::-1]:
		subTreeSize[u] = 1 + sum((subTreeSize[v] for v in children[u]))

	def isFib(root, numNodes):
		if numNodes <= 3:
			return True
		i = fibToIndex[numNodes]
		F1 = fib[i - 1]
		F2 = fib[i - 2]
		q = deque([root])
		while q:
			u = q.popleft()
			count = subTreeSize[u]
			if count == F1 or count == F2:
				p = parent[u]
				parent[u] = -1
				children[p].remove(u)
				while parent[p] != -1:
					subTreeSize[p] -= count
					p = parent[p]
				return isFib(u, count) and isFib(p, numNodes - count)
			q += graph[u]
		return False
	if isFib(root, N):
		return 'YES'
	return 'NO'
DEBUG = False
if DEBUG:
	N = 196418
	edges = [(i, i + 1) for i in range(N - 1)]
	print(solve(N, edges))
	exit()
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N,) = [int(x) for x in input().split()]
edges = [[int(x) - 1 for x in input().split()] for i in range(N - 1)]
print(solve(N, edges))


import io
import os
from collections import Counter, defaultdict, deque

def solve(N, edges):
	fib = [1, 1]
	while fib[-1] < N:
		fib.append(fib[-2] + fib[-1])
	fibToIndex = {x: i for (i, x) in enumerate(fib)}
	if N not in fibToIndex:
		return 'NO'
	graph = [set() for i in range(N)]
	for (u, v) in edges:
		graph[u].add(v)
		graph[v].add(u)
	root = 0
	q = [root]
	parent = [-1] * N
	parent[root] = -1
	for u in q:
		for v in graph[u]:
			if v != parent[u]:
				parent[v] = u
				q.append(v)
	subTreeSize = [-1] * N
	for u in q[::-1]:
		count = 1
		for v in graph[u]:
			if v != parent[u]:
				count += subTreeSize[v]
		subTreeSize[u] = count

	def isFib(root, numNodes):
		if numNodes <= 3:
			return True
		i = fibToIndex[numNodes]
		F1 = fib[i - 1]
		F2 = fib[i - 2]
		q = deque([root])
		while q:
			u = q.popleft()
			count = subTreeSize[u]
			if count == F1 or count == F2:
				uSize = F1 if count == F1 else F2
				p = parent[u]
				graph[u].remove(p)
				graph[p].remove(u)
				parent[u] = -1
				while parent[p] != -1:
					subTreeSize[p] -= count
					p = parent[p]
				return isFib(u, uSize) and isFib(p, numNodes - uSize)
			for v in graph[u]:
				if v != parent[u]:
					q.append(v)
		return False
	if isFib(root, N):
		return 'YES'
	return 'NO'
DEBUG = False
if DEBUG:
	N = 196418
	edges = []
	for i in range(N - 1):
		edges.append((i, i + 1))
	ans = solve(N, edges)
	print(ans)
	exit()
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = 1
for tc in range(1, TC + 1):
	(N,) = [int(x) for x in input().split()]
	edges = [[int(x) - 1 for x in input().split()] for i in range(N - 1)]
	ans = solve(N, edges)
	print(ans)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

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

def MI1():
	return map(int1, sys.stdin.buffer.readline().split())

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
inf = 10 ** 16
md = 10 ** 9 + 7
fibo = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418]
ftoi = {f: i for (i, f) in enumerate(fibo)}
n = II()
to = [[] for _ in range(n)]
for e in range(n - 1):
	(u, v) = MI1()
	to[u].append(v)
	to[v].append(u)
if n <= 3:
	print('YES')
	exit()
if n not in ftoi:
	print('NO')
	exit()
stack = [0]
sz = [-1] * n
par = [-1] * n
while stack:
	u = stack.pop()
	if sz[u] == -1:
		sz[u] = 1
		stack.append(u)
		for v in to[u]:
			if v == par[u]:
				continue
			par[v] = u
			stack.append(v)
	else:
		sz[par[u]] += sz[u]
fin = [False] * n

def dfs(r, s):
	i = ftoi[s]
	(s1, s2) = (fibo[i - 1], fibo[i - 2])
	stack = [r]
	while stack:
		u = stack.pop()
		for v in to[u]:
			if v == par[u]:
				continue
			if fin[v]:
				continue
			if sz[v] == s1 or sz[v] == s2:
				fin[v] = True
				return v
			stack.append(v)
	return -1

def ok():
	root = [(0, sz[0])]
	while root:
		(r, s) = root.pop()
		u = dfs(r, s)
		if u == -1:
			return False
		s1 = sz[u]
		if s1 > 3:
			root.append((u, s1))
		if s - s1 > 3:
			root.append((r, s - s1))
		while u != r:
			u = par[u]
			sz[u] -= s1
	return True
print('YES' if ok() else 'NO')


import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.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(io.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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
Fibs = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418]
N = int(input())
G_ = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(u, v) = map(int, input().split())
	G_[u].append(v)
	G_[v].append(u)
G = [[] for _ in range(N + 1)]
q = [(-1, 1)]
while q:
	(p, v) = q.pop()
	for u in G_[v]:
		if u != p:
			G[v].append(u)
			q.append((v, u))
if N not in Fibs:
	print('NO')
	exit()
idx_Fibs = Fibs.index(N)
Q = [(1, idx_Fibs)]
Counts = [1] * (N + 1)
Closed = [False] * (N + 1)
while Q:
	(V, idx_Fibs) = Q.pop()
	if idx_Fibs <= 2:
		continue
	ok1 = Fibs[idx_Fibs - 1]
	ok2 = Fibs[idx_Fibs - 2]
	q = [V]
	path = []
	while q:
		v = q.pop()
		Counts[v] = 1
		for u in G[v]:
			if Closed[u]:
				continue
			path.append((v, u))
			q.append(u)
	for (v, u) in reversed(path):
		if Counts[u] == ok1 or Counts[u] == ok2:
			break
		Counts[v] += Counts[u]
	else:
		print('NO')
		exit()
	Closed[u] = True
	if Counts[u] == ok1:
		Q.append((u, idx_Fibs - 1))
		Q.append((V, idx_Fibs - 2))
	else:
		Q.append((u, idx_Fibs - 2))
		Q.append((V, idx_Fibs - 1))
print('YES')


import os, sys, heapq as h, time
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict as dd
import math, string
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')

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

def getStrs():
	return input().split()

def getInts():
	return list(map(int, 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'

def solve():
	N = getInt()
	fibs = [1, 1]
	while True:
		x = fibs[-1] + fibs[-2]
		if x > N:
			break
		fibs.append(x)
	G = [[] for i in range(N)]
	for n in range(N - 1):
		(U, V) = getInts()
		U -= 1
		V -= 1
		G[U].append(V)
		G[V].append(U)
	q = [(0, -1)]
	graph = [[] for i in range(N)]
	while q:
		(v, p) = q.pop()
		for neigh in G[v]:
			if neigh != p:
				graph[v].append(neigh)
				q.append((neigh, v))
	if fibs[-1] != N:
		return 'NO'
	Q = [(0, len(fibs) - 1)]
	subtree = [1] * N
	used = [False] * N
	while Q:
		(node, idx) = Q.pop()
		if idx <= 3:
			continue
		(f1, f2) = (fibs[idx - 1], fibs[idx - 2])
		q = [node]
		path = []
		while q:
			v = q.pop()
			subtree[v] = 1
			for neigh in graph[v]:
				if used[neigh]:
					continue
				path.append((v, neigh))
				q.append(neigh)
		for (v, neigh) in reversed(path):
			if subtree[neigh] in [f1, f2]:
				break
			subtree[v] += subtree[neigh]
		else:
			return 'NO'
		used[neigh] = True
		if subtree[neigh] == f1:
			Q.append((neigh, idx - 1))
			Q.append((node, idx - 2))
		else:
			Q.append((neigh, idx - 2))
			Q.append((node, idx - 1))
	return 'YES'
print(solve())


class Graph:

	def __init__(self, n_vertices, edges, directed=True):
		self.n_vertices = n_vertices
		self.directed = directed
		self.edges = edges

	@property
	def adj(self):
		try:
			return self._adj
		except AttributeError:
			adj = [[] for _ in range(self.n_vertices)]
			if self.directed:
				for (u, v) in self.edges:
					adj[u].append(v)
			else:
				for (u, v) in self.edges:
					adj[u].append(v)
					adj[v].append(u)
			self._adj = adj
			return adj

class RootedTree(Graph):

	def __init__(self, n_vertices, edges, root_vertex=0):
		super().__init__(n_vertices, edges, directed=False)
		self.root = root_vertex

	@property
	def parent(self):
		try:
			return self._parent
		except AttributeError:
			adj = self.adj
			parent = [0] * self.n_vertices
			parent[self.root] = -1
			stack = [self.root]
			for _ in range(self.n_vertices):
				v = stack.pop()
				p = parent[v]
				for u in adj[v]:
					if u != p:
						parent[u] = v
						stack.append(u)
			self._parent = parent
			return parent

	@property
	def children(self):
		try:
			return self._children
		except AttributeError:
			children = [None] * self.n_vertices
			for (v, (l, p)) in enumerate(zip(self.adj, self.parent)):
				children[v] = [u for u in l if u != p]
			self._children = children
			return children

	@property
	def dfs_order(self):
		try:
			return self._dfs_order
		except AttributeError:
			order = [0] * self.n_vertices
			children = self.children
			stack = [self.root]
			for i in range(self.n_vertices):
				v = stack.pop()
				order[i] = v
				for u in children[v]:
					stack.append(u)
			self._dfs_order = order
			return order

def solve(edges, n):
	fib = [1, 1]
	while fib[-1] < n:
		fib.append(fib[-1] + fib[-2])
	if fib[-1] != n:
		return False
	rt = RootedTree(n, edges)
	parent = rt.parent
	children = rt.children
	size = [0] * n
	stack = [(len(fib) - 1, 0)]
	while stack:
		(ind, root) = stack.pop()
		if ind <= 1:
			continue
		split = [fib[ind - 2], fib[ind - 1]]
		s = [~root, root]
		while s:
			v = s.pop()
			if v < 0:
				v = ~v
				t = 1 + sum((size[u] for u in children[v]))
				size[v] = t
				p = parent[v]
				if t in split:
					if t == split[0]:
						stack.append((ind - 2, v))
						stack.append((ind - 1, root))
					else:
						stack.append((ind - 1, v))
						stack.append((ind - 2, root))
					children[p].remove(v)
					parent[v] = -1
					break
			else:
				for u in children[v]:
					s.append(~u)
					s.append(u)
		else:
			return False
	return True
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
m = map(int, read().split())
n = next(m)
edges = [(a - 1, b - 1) for (a, b) in zip(m, m)]
print('Yes' if solve(edges, n) else 'No')