Consider a rooted tree. A rooted tree has one special vertex called the root. All edges are directed from the root. Vertex u is called a child of vertex v and vertex v is called a parent of vertex u if there exists a directed edge from v to u. A vertex is called a leaf if it doesn't have children and has a parent.

Let's call a rooted tree a spruce if its every non-leaf vertex has at least 3 leaf children. You are given a rooted tree, check whether it's a spruce.

The definition of a rooted tree can be found here.


-----Input-----

The first line contains one integer n — the number of vertices in the tree (3 ≤ n ≤ 1 000). Each of the next n - 1 lines contains one integer p_{i} (1 ≤ i ≤ n - 1) — the index of the parent of the i + 1-th vertex (1 ≤ p_{i} ≤ i).

Vertex 1 is the root. It's guaranteed that the root has at least 2 children.


-----Output-----

Print "Yes" if the tree is a spruce and "No" otherwise.


-----Examples-----
Input
4
1
1
1

Output
Yes

Input
7
1
1
1
2
2
2

Output
No

Input
8
1
1
1
1
3
3
3

Output
Yes



-----Note-----

The first example:

[Image]

The second example:

$8$

It is not a spruce, because the non-leaf vertex 1 has only 2 leaf children.

The third example:

[Image]

Difficulty: interview

Starter code:

Solutions:
#!/usr/bin/env python3

def main():
    class Node:
        def __init__(self):
            self.children = [ ]

    n = int(input())
    nodes = [Node() for i in range(n)]
    for i in range(1, n):
        p = int(input())
        nodes[p - 1].children.append(nodes[i])
    ok = all(
        len([child for child in node.children if not child.children]) >= 3
        for node in nodes
        if node.children
    )
    print("Yes" if ok else "No")

try:
    while True:
        main()
except EOFError:
    pass


read = lambda: list(map(int, input().split()))
n = int(input())
g = [list() for i in range(n + 1)]
for i in range(n - 1):
    p = int(input())
    g[p].append(i + 2)
c = [0] * (n + 1)
for i in range(1, n + 1):
    if len(g[i]) == 0:
        c[i] = 1
for i in range(1, n +1):
    if not c[i]:
        cnt = 0
        for u in g[i]:
            cnt += c[u]
        if cnt < 3:
            print('No')
            return
print('Yes')


n = int(input())
par = [-1 for i in range(n + 123)]

for i in range(2, n + 1):
    par[i] = int(input())

is_leaf = [True for i in range(n + 123)]

for i in range(2, n + 1):
    is_leaf[par[i]] = False

children = [0 for i in range(n + 123)]

for i in range(2, n + 1):
    children[par[i]] += is_leaf[i]


ans = True
for i in range(1, n + 1):
    if is_leaf[i]:
        continue
    ans &= children[i] >= 3


print('Yes' if ans else 'No')


n = int(input())
is_leaf = [True]*(n+1)
children = [[] for _ in range(n+1)]
ans = "Yes"

for i in range(2, n+1):
    p = int(input())
    children[p].append(i)
    is_leaf[p] = False

for node in range(1, n+1):
    if not is_leaf[node]:
        count = 0
        for child in children[node]:
            count += is_leaf[child]
        if count < 3:
            ans = "No"
            break
print(ans)


n = int(input())
d = []
for i in range(n - 1):
	d.append(int(input()))
m = {i:[] for i in range(1, n + 1)}
z = {i:0 for i in range(1, n + 1)}
for i in range(len(d)):
	m[d[i]].append(i + 2)
for i in m:
	if m[i] == []:
		z[i] = -1
for i in m:
	for j in m[i]:
		if z[j] == -1:
			z[i] += 1
f = True
for i in z:
	if z[i] < 3 and z[i] != -1:
		f = False
		break
if f:
	print('Yes')
else:
	print('No')

import sys
sys.setrecursionlimit(10 ** 5)
n = int(input())
g = [[] for i in range(n)]
for i in range(1, n):
    z = int(input()) - 1
    g[z].append(i)
#print(g)
b = True
for el in g:
    if len(el) == 0:
        continue
    z = 0
    for v in el:
        z += len(g[v]) == 0
    if z <= 2:
        b = False
if b:
    print("Yes")
else:
    print("No")


n = int(input())
deg = [0 for _ in range(n + 1)]
chd = [0 for _ in range(n + 1)]
f = [0 for _ in range(n + 1)]
for i in range(2, n + 1):
    f[i] = int(input())
    deg[f[i]] += 1
isok = True
for i in range(2, n + 1):
    if deg[i] == 0:
        chd[f[i]] += 1

for i in range(1, n + 1):
    if deg[i] != 0 and chd[i] < 3:
        isok = False
if isok:
    print("Yes")
else:
    print("No")

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

n = ii()
g = [[] for i in range(n+1)]
for i in range(2, n+1):
    x = ii()
    g[x].append(i)
l = set(i for i in range(1, n+1) if not g[i])
c = sum(sum(j in l for j in g[i]) >= 3 for i in range(1, n+1))
print('Yes' if c + len(l) == n else 'No')


n = int(input())
parent = [None] * n
children = [[] for i in range(n)]
for i in range(1, n):
	p = int(input())
	p = p - 1
	parent[i] = p
	children[p].append(i)

leaf = {}		
for i in range(n):
	if len(children[i]) == 0:
		leaf[i] = True
	else:
		leaf[i] = False

for i in range(n):
	if leaf[i]:
		continue
	c = 0
	for j in children[i]:
		if leaf[j]:
			c = c + 1
	if c < 3:
		print("No")
		quit()

print("Yes")

n = int(input())
leaf = [True]*(n+1)
chd = [-1]*(n+1)
for i in range(2,n+1):
    p = int(input())
    if chd[p] == -1:
        chd[p] = [i]
        leaf[p] = False
    else:
        chd[p].append(i)
suc = True
for i in range(1,n+1):
    ctr = 0
    if not leaf[i]:
        for x in chd[i]:
            if leaf[x]:
                ctr += 1
        if ctr < 3:
            suc = False
            break

if suc:
    print('Yes')
else:
    print('No')


from collections import defaultdict as dd, deque

n = int(input())

V = [i+1 for i in range(n)]
E = dd(list)

for i in V[1:]:
    p = int(input())
    E[p].append(i)

for v in V:
    if len(E[v]) != 0 and sum(len(E[u])==0 for u in E[v]) < 3:
        print('No')
        break
else:
    print('Yes')


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

c_children = [0] * (n + 1)

for pi in p:
	c_children[pi] += 1

def is_leaf(i):
	return c_children[i] == 0

for i in range(1, n + 1):
	if not is_leaf(i):
		t = 0

		for j in range(2, n + 1): 
			if p[j - 2] == i and is_leaf(j): t += 1

		if t < 3: 
			print("No")
			return

print("Yes")


def spruce():
    n = int(input())
    tree = dict()
    parent = set()
    for i in range(n-1):
        p = int(input())
        parent.add(p)
        childs = tree.get(p, list())
        childs.append(i+2)
        tree[p] = childs
    is_spruce = True
    for p in parent:
        childs = set(tree[p])
        leafs = childs - parent
        if len(leafs) < 3:
            is_spruce = False
            break

    if is_spruce:
        print('Yes')
    else:
        print('No')

def __starting_point():
    spruce()
__starting_point()

from itertools import permutations

MOD = 10**9+7

def main():
    n = int(input())
    parent = [0] * n
    is_leaf = [True] * n
    for i in range(1,n):
        parent[i] = int(input()) - 1
        is_leaf[parent[i]] = False
    leafs_cnt = [0] * n
    for i in range(n):
        leafs_cnt[parent[i]] += is_leaf[i]
    for i in range(n):
        if not is_leaf[i] and leafs_cnt[i] < 3:
            print("No")
            return
    print("Yes")

while 1:
    main()
    break
# input()


n = int(input())
c = {}
for i in range(n):
    c[i]=[]
for i in range(n-1):
    c[int(input())-1].append(i+1)
f = True
for i in range(n):
    cl = 0
    for j in c[i]:
        if len(c[j]) == 0:cl+=1
    if len(c[i])!=0 and cl < 3:f = False
print('Yes' if f else 'No')


import sys
sys.setrecursionlimit(10000)
n=int(input())

vs = {}
for c in range(2, n+1):
    p = int(input())
    if p in vs:
        vs[p].append(c)
    else:
        vs[p] = [c]

def check(n):
    if n not in vs:
        return 1
    ch = vs[n]
    s = 0
    for c in ch:
        r = check(c)
        if r == -1:
            return -1
        s+=r
    if s >= 3:
        return 0
    return -1

print('Yes' if check(1) == 0 else 'No')

def solve():
    n =  int(input())
    #l = [[]] * (n+1)
    l = [[] for i in range(n+1)]
    for i in range(2, n+1):
        a = int(input())
        l[a].append(i)
        #print(l)

    #print(l)
    for i in l:
        if len(i) != 0:
            leafCount = 0
            for j in i:
                if len(l[j]) == 0:
                    leafCount+=1
            if leafCount < 3:
                print("No")
                return
    print("Yes")

solve()

n=int(input())
d={1:[]}
for i in range(n-1):
	parent=int(input())
	if parent in d:
		d[parent].append(i+2)
	else:
		d[parent]=[i+2]
for i in d:
	count=0
	for j in d[i]:
		if j not in d:
			count+=1
	if count<3:
		print('No')
		return
print('Yes')

a = dict()
for i in range(int(input())-1):
	c = int(input())
	if (not c in a): a[c] = list()
	a[c].append(i+2)
for i in a:
	l = int()
	for j in a[i]:
		if (j not in a): l += 1
	if (l < 3):
		print("No")
		return
print("Yes")

n=int(input())
parents=[]
tree=[[] for i in range(n)]
for i in range(n-1):
    par=int(input())-1
    tree[par].append(i+1)
    parents.append(par)
flag=True
#print(parents)
#print(tree)
for i in parents:
    count=0
    
    for j in tree[i]:
        if(len(tree[j])==0):
            count+=1
    if(count<3):
        flag=False
        
        
        
if(flag):
    print('Yes')
else:
    print('No')

n = int(input())
l = [0] * n

for i in range(1,n):
    l[i] = int(input())-1

leaves = [1] * n
leaves[0] = 0

for i in range(n):
    for j in range(i, n-1):
        if l[j] == i:
            leaves[i] = 0

spruce = 'Yes'

for i in range(n):
    if leaves[i] == 0:
        count = 0
        for j in range(i,n):
            if l[j] == i and leaves[j]:
                count += 1
        if count < 3:
            spruce = 'No'

print(spruce)


n = int(input())
g = {}
s = set()
bol = True
for i in range(1,2000):
    g[i]=[]

for j in range(2,n+1):
    a = int(input())
    s.add(a)
    g[a].append(j)

for k in s:
    d = 0 
    for h in g[k]:
        if h not in s:
            d = d + 1

    if d<3:
        bol = False
if bol:
    print("Yes")
else:
    print("No")


from queue import Queue


def BFS(v):
    st = Queue()
    st.put(v)

    while not st.empty():
        u = st.get()

        count = 0
        for v in graph[u]:
            if graph[v] == list():
                count += 1

            else:
                st.put(v)

        if count < 3:
            return False

    return True


n = int(input())

graph = {i: list() for i in range(1, n + 1)}
for i in range(2, n + 1):
    j = int(input())

    graph[j].append(i)

print(('No', 'Yes')[BFS(1)])