human
Evlampiy was gifted a rooted tree. The vertices of the tree are numbered from 1 to n. Each of its vertices also has an integer a_i written on it. For each vertex i, Evlampiy calculated c_i — the number of vertices j in the subtree of vertex i, such that a_j < a_i. 

Illustration for the second example, the first integer is a_i and the integer in parentheses is c_i

After the new year, Evlampiy could not remember what his gift was! He remembers the tree and the values of c_i, but he completely forgot which integers a_i were written on the vertices.

Help him to restore initial integers!

Input

The first line contains an integer n (1 ≤ n ≤ 2000) — the number of vertices in the tree.

The next n lines contain descriptions of vertices: the i-th line contains two integers p_i and c_i (0 ≤ p_i ≤ n.
0 ≤ c_i ≤ n-1), where p_i is the parent of vertex i or 0 if vertex i is root, and c_i is the number of vertices j in the subtree of vertex i, such that a_j < a_i.

It is guaranteed that the values of p_i describe a rooted tree with n vertices.

Output

If a solution exists, in the first line print "YES", and in the second line output n integers a_i (1 ≤ a_i ≤ {10}^{9}). If there are several solutions, output any of them. One can prove that if there is a solution, then there is also a solution in which all a_i are between 1 and 10^9.

If there are no solutions, print "NO".

Examples

Input

3
2 0
0 2
2 0

Output

YES
1 2 1 

Input

5
0 1
1 3
2 1
3 0
2 0

Output

YES
2 3 2 1 2
Solve the task in PYTHON3.

=====
Give me a Python program to print "YES", and in the second line output n integers a_i (1 ≤ a_i ≤ {10}^{9})?
assistant
#Here is Python program to print "YES", and in the second line output n integers a_i (1 ≤ a_i ≤ {10}^{9}).

from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
 
# M = mod = 998244353
def factors(n):return sorted(list(set(reduce(list.__add__,([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))))
# def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split(' ')]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n').split(' ')]
def li3():return [int(i) for i in input().rstrip('\n')]

va = 10**7
helpl = defaultdict(deque)
def dfs(i):
    global va
    curr = []
    # print('currnode : ',i)
    for j in d[i]:
        curr.extend(dfs(j))
    curr = sorted(list(curr))
    # print('currlen : ',curr,'c value : ',c[i-1])
    if len(curr) < c[i-1]:
        print('NO')
        exit()
    if not len(curr):
        curr.append(va)
        helpl[va].append(i-1)
        va -= 2000
    else:
        # if c[i-1] == 0:
        #     # curr.append(curr[0] - 1)
        #     helpl[curr[0]].append(i-1)
        
        # print(curr)
        for j in range(c[i-1]):
            helpl[curr[j] - 1].append(helpl[curr[j]].popleft())
            curr[j] -= 1
        for j in range(len(curr)-1,c[i-1]-1,-1):
            helpl[curr[j] + 1].append(helpl[curr[j]].popleft())
            helpl[curr[j]] = deque()
            curr[j] += 1
        # print(curr,c[i-1])
        
        
        if c[i-1] == len(curr):curr.append(curr[-1] + 1)
        else:curr = curr[:c[i-1]] + [curr[c[i-1]]-1] + curr[c[i-1]:]
        helpl[curr[c[i-1]]].append(i-1)
        # print(helpl)
        # for i in helpl:
            
        #     if len(helpl[i]):
        #         helpl[i] = deque(sorted(helpl[i]))
    return curr

n = val()
d = defaultdict(list)
c = []
a = [0 for i in range(n)]
for i in range(n):
    x,y = li()
    d[x].append(i + 1)
    c.append(y)
# print(d)
root =...