AtCoder Regular Contest 063 - Integers on a Tree

We have a tree with N vertices. The vertices are numbered 1, 2, ..., N. The i-th (1 ≦ i ≦ N - 1) edge connects the two vertices A_i and B_i.
Takahashi wrote integers into K of the vertices. Specifically, for each 1 ≦ j ≦ K, he wrote the integer P_j into vertex V_j. The remaining vertices are left empty. After that, he got tired and fell asleep.
Then, Aoki appeared. He is trying to surprise Takahashi by writing integers into all empty vertices so that the following condition is satisfied:
 - Condition: For any two vertices directly connected by an edge, the integers written into these vertices differ by exactly 1.
Determine if it is possible to write integers into all empty vertices so that the condition is satisfied. If the answer is positive, find one specific way to satisfy the condition.

-----Constraints-----
 - 1 ≦ N ≦ 10^5
 - 1 ≦ K ≦ N
 - 1 ≦ A_i, B_i ≦ N (1 ≦ i ≦ N - 1)
 - 1 ≦ V_j ≦ N (1 ≦ j ≦ K) (21:18, a mistake in this constraint was corrected)
 - 0 ≦ P_j ≦ 10^5 (1 ≦ j ≦ K)
 - The given graph is a tree.
 - All v_j are distinct.

-----Input-----
The input is given from Standard Input in the following format:
N
A_1 B_1
A_2 B_2
:
A_{N-1} B_{N-1}
K
V_1 P_1
V_2 P_2
:
V_K P_K

-----Output-----
If it is possible to write integers into all empty vertices so that the condition is satisfied, print Yes. Otherwise, print No.
If it is possible to satisfy the condition, print N lines in addition. The v-th (1 ≦ v ≦ N) of these N lines should contain the integer that should be written into vertex v. If there are multiple ways to satisfy the condition, any of those is accepted.

-----Sample Input-----
5
1 2
3 1
4 3
3 5
2
2 6
5 7

-----Sample Output-----
Yes
5
6
6
5
7

The figure below shows the tree when Takahashi fell asleep. For each vertex, the integer written beside it represents the index of the vertex, and the integer written into the vertex is the integer written by Takahashi.
Aoki can, for example, satisfy the condition by writing integers into the remaining vertices as follows:
This corresponds to Sample Output 1. Note that other outputs that satisfy the condition will also be accepted, such as:
Yes
7
6
8
7
7

Difficulty: HARD

Starter code:

Solutions:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5 + 100)
from collections import *

def dfs(v, pv, de):
	for nv in G[v]:
		if nv == pv:
			continue
		dfs(nv, v, de + 1)
		left[v] = max(left[v], left[nv] - 1)
		right[v] = min(right[v], right[nv] + 1)
	if v in d:
		if d[v] < left[v] or right[v] < d[v] or (d[v] - d[root]) % 2 != de % 2:
			print('No')
			exit()
		else:
			left[v] = d[v]
			right[v] = d[v]

def dfs2(v, pv, now):
	ans[v] = now
	for nv in G[v]:
		if nv == pv:
			continue
		if left[nv] <= now - 1 <= right[nv]:
			dfs2(nv, v, now - 1)
		elif left[nv] <= now + 1 <= right[nv]:
			dfs2(nv, v, now + 1)
		else:
			print('No')
			exit()
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
	(A, B) = map(int, input().split())
	G[A - 1].append(B - 1)
	G[B - 1].append(A - 1)
d = defaultdict(int)
K = int(input())
for _ in range(K):
	(V, P) = map(int, input().split())
	d[V - 1] = P
	root = V - 1
left = [-10 ** 18] * N
right = [10 ** 18] * N
dfs(root, -1, 0)
ans = [-1] * N
dfs2(root, -1, d[root])
print('Yes')
for ans_i in ans:
	print(ans_i)


import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
G = [[] for i in range(N)]
for i in range(N - 1):
	(A, B) = map(int, input().split())
	G[A - 1].append(B - 1)
	G[B - 1].append(A - 1)
M = {}
K = int(input())
for i in range(K):
	(V, P) = map(int, input().split())
	M[V - 1] = P
memo = [0] * N

def dfs(v, p, x, y):
	if v in M:
		x = y = M[v]
	x0 = x
	y0 = y
	for w in G[v]:
		if p == w:
			continue
		(s, t) = dfs(w, v, x - 1, y + 1)
		x0 = max(x0, s - 1)
		y0 = min(y0, t + 1)
	memo[v] = (x0, y0)
	return (x0, y0)

def dfs1(v, p, x, y, c):
	if v in M:
		x = y = M[v]
		if c != M[v] % 2:
			return 0
	(x0, y0) = memo[v]
	x = max(x, x0)
	y = min(y, y0)
	for w in G[v]:
		if p == w:
			continue
		if not dfs1(w, v, x - 1, y + 1, c ^ 1):
			return 0
	memo[v] = (x, y)
	return 1
INF = 10 ** 18
f = list(M.keys())[0]
dfs(f, -1, -INF, INF)
ok = dfs1(f, -1, -INF, INF, M[f] % 2)
for i in range(N):
	(x, y) = memo[i]
	if not x <= y:
		ok = 0
if ok:
	print('Yes')
	print(*map(lambda x: x[1], memo), sep='\n')
else:
	print('No')


import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]
K = int(sys.stdin.buffer.readline())
VP = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(K)]
graph = [[] for _ in range(N)]
for (a, b) in AB:
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
mins = [-INF] * N
maxes = [INF] * N
for (v, p) in VP:
	v -= 1
	mins[v] = p
	maxes[v] = p
root = VP[0][0] - 1

def dfs(v, p=None, p_max=INF, p_min=-INF):
	p_max = min(p_max + 1, maxes[v])
	p_min = max(p_min - 1, mins[v])
	c_max = maxes[v]
	c_min = mins[v]
	for u in graph[v]:
		if u == p:
			continue
		(ma, mi) = dfs(u, v, p_max, p_min)
		c_max = min(c_max, ma + 1)
		c_min = max(c_min, mi - 1)
	maxes[v] = min(p_max, c_max)
	mins[v] = max(p_min, c_min)
	return (c_max, c_min)
dfs(root)
ok = True
for (ma, mi) in zip(maxes, mins):
	ok &= ma >= mi
if not ok:
	print('No')
	exit()
ans = [None] * N
ans[root] = maxes[root]
stack = [(root, None)]
while stack:
	(v, p) = stack.pop()
	a = ans[v]
	for u in graph[v]:
		if u == p:
			continue
		if mins[u] <= a - 1 <= maxes[u]:
			ans[u] = a - 1
		elif mins[u] <= a + 1 <= maxes[u]:
			ans[u] = a + 1
		else:
			print('No')
			exit()
		stack.append((u, v))
print('Yes')
print(*ans, sep='\n')


from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

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

def reads():
	return [int(x) for x in input().split()]

def inc(x):
	if x == 'No':
		return 'No'
	elif x == 'Any':
		return 'Any'
	else:
		(a, b, p) = x
		return (a - 1, b + 1, (p + 1) % 2)

def imin(x, y):
	if x == 'No' or y == 'No':
		return 'No'
	elif y == 'Any':
		return x
	elif x == 'Any':
		return y
	else:
		(a1, b1, p1) = x
		(a2, b2, p2) = y
		if p1 != p2 or b1 < a2 or b2 < a1:
			return 'No'
		else:
			return (max(a1, a2), min(b1, b2), p1)
setrecursionlimit(1000000)
N = read()
edges = [[] for i in range(N)]
for i in range(N - 1):
	(A, B) = reads()
	(A, B) = (A - 1, B - 1)
	edges[A].append(B)
	edges[B].append(A)
K = read()
d = ['Any'] * N
for i in range(K):
	(V, P) = reads()
	V = V - 1
	d[V] = (P, P, P % 2)
children = [[] for i in range(N)]
parent = [0] * N
parent[0] = None

def walk(n):
	children[n] = list(edges[n])
	if n != 0:
		children[n].remove(parent[n])
	for i in children[n]:
		parent[i] = n
		walk(i)
	d[n] = reduce(imin, (inc(d[i]) for i in children[n]), d[n])
walk(0)
f = [0] * N

def walk2(n, k=None):
	if d[n] == 'No':
		print('No')
		exit()
	elif d[n] == 'Any':
		f[n] = k + 1
	else:
		(a, b, p) = d[n]
		if k == None:
			if a % 2 == p:
				f[n] = a
			else:
				f[n] = a + 1
		elif a <= k - 1 <= b:
			f[n] = k - 1
		elif a <= k + 1 <= b:
			f[n] = k + 1
		else:
			print('No')
			exit()
	for i in children[n]:
		walk2(i, f[n])
walk2(0)
print('Yes')
for i in range(N):
	print(f[i])


def shortestPath(g, s, dist, prev):
	n = len(g) - 1
	Q = []
	heapq.heappush(Q, (0, -2, s))
	while Q:
		e = heapq.heappop(Q)
		if prev[e[2]] != -1:
			continue
		prev[e[2]] = e[1]
		for f in g[e[2]]:
			if dist[f[2]] > e[0] + f[0]:
				dist[f[2]] = e[0] + f[0]
				heapq.heappush(Q, (e[0] + f[0], f[1], f[2]))
import sys, heapq
if sys.version_info[0] >= 3:
	raw_input = input
n = int(raw_input())
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(a, b) = map(int, raw_input().split())
	g[a - 1] += [(1, a - 1, b - 1)]
	g[b - 1] += [(1, b - 1, a - 1)]
z = [-1] * n
for _ in range(int(raw_input())):
	(a, b) = map(int, raw_input().split())
	g[n] += [(b, n, a - 1)]
	z[a - 1] = b
a = [1000000000.0] * n + [0]
shortestPath(g, n, a, [-1] * (n + 1))
if any((z[i] >= 0 and z[i] != a[i] for i in range(n))):
	print('No')
	sys.exit()
for _ in g:
	if any((e[1] != n and abs(a[e[1]] - a[e[2]]) != 1 for e in _)):
		print('No')
		sys.exit()
print('Yes')
print('\n'.join(map(str, a[:n])))


def main():
	n = int(input())
	ab = [list(map(int, input().split())) for _ in [0] * (n - 1)]
	k = int(input())
	vp = [list(map(int, input().split())) for _ in [0] * k]
	g = [[] for _ in [0] * n]
	[g[a - 1].append(b - 1) for (a, b) in ab]
	[g[b - 1].append(a - 1) for (a, b) in ab]
	parity = [-1] * n
	root = vp[0][0] - 1
	p = vp[0][1] % 2
	parity[root] = p
	q = [root]
	while q:
		p ^= 1
		qq = []
		while q:
			i = q.pop()
			for j in g[i]:
				if parity[j] == -1:
					parity[j] = p
					qq.append(j)
		q = qq
	for (v, p) in vp:
		if p % 2 != parity[v - 1]:
			print('No')
			return
	ans_range = [[-10 ** 10, 10 ** 10] for _ in [0] * n]
	q = [root]
	vp = {v - 1: p for (v, p) in vp}
	M = 10 ** 10
	m = -10 ** 10
	g2 = [set(gg) for gg in g]
	while q:
		i = q[-1]
		if i in vp:
			if m <= vp[i] <= M:
				M = vp[i]
				m = M
				ans_range[i] = [m, M]
			else:
				print('No')
				return
		else:
			(m2, M2) = ans_range[i]
			if M2 < m or M < m2:
				print('No')
				return
			m = max(m, m2)
			M = min(M, M2)
			ans_range[i] = [m, M]
		if g2[i]:
			j = g2[i].pop()
			g2[j].remove(i)
			q.append(j)
		else:
			q.pop()
		m -= 1
		M += 1
	q = [root]
	now = vp[root]
	ans = [None] * n
	g = [set(gg) for gg in g]
	while q:
		i = q[-1]
		if ans[i] != None:
			now = ans[i]
		else:
			if ans_range[i][1] < now:
				now -= 2
			ans[i] = now
		if g[i]:
			j = g[i].pop()
			g[j].remove(i)
			q.append(j)
		else:
			q.pop()
		now += 1
	print('Yes')
	for i in ans:
		print(i)
main()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
graph = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)
K = int(input())
v_to_p = [None] * (N + 1)
for _ in range(K):
	(v, p) = map(int, input().split())
	v_to_p[v] = p
rng = [None] * (N + 1)

def calc_rng(v=1, parent=None):
	x = v_to_p[v]
	y = x
	for c in graph[v]:
		if c == parent:
			continue
		ret = calc_rng(c, v)
		if ret == False:
			return False
		(x1, y1) = ret
		if x1 is None:
			continue
		if x is None:
			(x, y) = (x1 - 1, y1 + 1)
			continue
		if not x - x1 & 1:
			return False
		if x < x1 - 1:
			x = x1 - 1
		if y > y1 + 1:
			y = y1 + 1
	if x is not None and x > y:
		return False
	rng[v] = (x, y)
	return (x, y)

def set_value(v=1, parent=None):
	if v_to_p[v] is None:
		p = v_to_p[parent]
		(x, y) = rng[v]
		if x is None:
			v_to_p[v] = p + 1
		elif x <= p + 1 <= y:
			v_to_p[v] = p + 1
		else:
			v_to_p[v] = p - 1
	for c in graph[v]:
		if c == parent:
			continue
		set_value(c, v)
ret = calc_rng()
if ret == False:
	print('No')
else:
	v_to_p[1] = rng[1][0]
	set_value()
	print('Yes')
	print('\n'.join(map(str, v_to_p[1:])))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
NUM = [-1] * N
K = int(input())
for _ in range(K):
	(a, b) = map(int, input().split())
	NUM[a - 1] = b
	root = a - 1
MIN = [None] * N
MAX = [None] * N
rootnum = NUM[root]
checked = [False] * N

def dfs(p, d):
	checked[p] = True
	(minnum, maxnum) = (rootnum - d, rootnum + d)
	ok = True
	for np in graph[p]:
		if not checked[np]:
			ok = dfs(np, d + 1) and ok
			if MIN[np] % 2 == minnum % 2 or MAX[np] % 2 == minnum % 2:
				ok = False
			minnum = max(minnum, MIN[np] - 1)
			maxnum = min(maxnum, MAX[np] + 1)
	if maxnum < minnum:
		ok = False
	if NUM[p] != -1:
		if not minnum <= NUM[p] <= maxnum:
			ok = False
		MAX[p] = NUM[p]
		MIN[p] = NUM[p]
	else:
		MAX[p] = maxnum
		MIN[p] = minnum
	return ok
if not dfs(root, 0):
	print('No')
else:
	print('Yes')
	checked = [False] * N
	q = [root]
	while q:
		qq = []
		for p in q:
			pnum = NUM[p]
			for np in graph[p]:
				if not checked[np]:
					if NUM[np] == -1:
						if MIN[np] <= pnum + 1 <= MAX[np]:
							NUM[np] = pnum + 1
						else:
							NUM[np] = pnum - 1
					qq.append(np)
					checked[np] = True
		q = qq
	print(*NUM, sep='\n')


import sys
read = sys.stdin.read
readline = sys.stdin.readline
(n,) = map(int, readline().split())
g = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, readline().split())
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
order = []
parent = [-1] * n
st = [0]
while st:
	v = st.pop()
	order.append(v)
	for c in g[v]:
		if parent[v] != c:
			parent[c] = v
			st.append(c)
INF = 1 << 30
high = [INF] * n
low = [-INF] * n
val = [INF] * n
(k,) = map(int, readline().split())
for _ in range(k):
	(v, p) = map(int, readline().split())
	high[v - 1] = low[v - 1] = val[v - 1] = p
for v in order[:0:-1]:
	p = parent[v]
	(h, l) = (high[v] + 1, low[v] - 1)
	if h >= INF:
		pass
	elif high[p] >= INF:
		high[p] = h
		low[p] = l
	elif high[p] - h & 1 == 0:
		if h < high[p]:
			high[p] = h
		if l > low[p]:
			low[p] = l
		if high[p] < low[p]:
			print('No')
			break
	else:
		print('No')
		break
else:
	print('Yes')
	for v in order:
		if val[v] == INF:
			val[v] = low[v]
		for c in g[v]:
			high[c] = min(high[c], val[v] + 1)
			low[c] = max(low[c], val[v] - 1)
	print(*val, sep='\n')


import sys
sys.setrecursionlimit(500000)
N = int(input())
E = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b) = list(map(int, input().split()))
	E[a].append(b)
	E[b].append(a)
K = int(input())
L = [-float('inf')] * (N + 1)
R = [float('inf')] * (N + 1)
for _ in range(K):
	(v, p) = list(map(int, input().split()))
	L[v] = p
	R[v] = p
tour = []

def dfs(v, p):
	tour.append(v)
	for u in E[v]:
		if u != p:
			dfs(u, v)
			tour.append(v)
dfs(v, 0)
(l, r) = (L[v], R[v])
odd = p % 2
for v in tour[1:]:
	l -= 1
	r += 1
	odd = 1 - odd
	(l_, r_) = (L[v], R[v])
	if r_ != float('inf') and r_ % 2 != odd:
		print('No')
		return
	l = max(l, l_)
	r = min(r, r_)
	L[v] = l
	R[v] = r
for v in tour[-2::-1]:
	l -= 1
	r += 1
	odd = 1 - odd
	(l_, r_) = (L[v], R[v])
	l = max(l, l_)
	r = min(r, r_)
	if l > r:
		print('No')
		return
	L[v] = l
	R[v] = r
Ans = [-1] * (N + 1)
print('Yes')
print('\n'.join(map(str, L[1:])))


import heapq
f = lambda : map(int, input().split())
n = int(input())
g = [[] for _ in range(n + 1)]
z = [-1] * n
d = [1000000000.0] * n + [0]
q = [-1] * (n + 1)
r = ''
Q = []
heapq.heappush(Q, (0, -2, n))
for _ in range(n - 1):
	(a, b) = f()
	a -= 1
	b -= 1
	g[a] += [(1, a, b)]
	g[b] += [(1, b, a)]
for _ in range(int(input())):
	(a, b) = f()
	a -= 1
	g[n] += [(b, n, a)]
	z[a] = b
while Q:
	e = heapq.heappop(Q)
	if q[e[2]] != -1:
		continue
	q[e[2]] = e[1]
	for f in g[e[2]]:
		if d[f[2]] > e[0] + f[0]:
			d[f[2]] = e[0] + f[0]
			heapq.heappush(Q, (e[0] + f[0], f[1], f[2]))
for _ in g:
	if any((e[1] != n and abs(d[e[1]] - d[e[2]]) != 1 for e in _)):
		r = 'No'
else:
	if any((z[i] >= 0 and z[i] != d[i] for i in range(n))):
		r = 'No'
print(r or 'Yes\n' + '\n'.join(map(str, d[:n])))


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

def solve(tree, vp):
	adj = tree.adj
	n = tree.n_vertices
	q = [v - 1 for (v, p) in vp]
	ranges = [None] * n
	for (v, p) in vp:
		ranges[v - 1] = (p, p)
	while q:
		nq = []
		for v in q:
			(a, b) = ranges[v]
			(na, nb) = (a - 1, b + 1)
			for u in adj[v]:
				if ranges[u] is None:
					ranges[u] = (na, nb)
					nq.append(u)
				else:
					(c, d) = ranges[u]
					if (c + na) % 2 == 1:
						return None
					(x, y) = (max(na, c), min(nb, d))
					if x > y:
						return None
					ranges[u] = (x, y)
					if (x, y) != (c, d):
						nq.append(u)
		q = nq
	return [a for (a, b) in ranges]

def __starting_point():
	n = int(input())
	edges = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(n - 1)]
	k = int(input())
	vp = [tuple(map(int, input().split())) for _ in range(k)]
	tree = Graph(n, edges, False)
	res = solve(tree, vp)
	if res is None:
		print('No')
	else:
		print('Yes')
		print(*res, sep='\n')
__starting_point()


import sys
from collections import defaultdict as dd
from collections import deque as dq
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
input = sys.stdin.readline
N = int(input())
e = dd(list)
for _ in range(N - 1):
	(u, v) = map(int, input().split())
	e[u].append(v)
	e[v].append(u)
K = int(input())
ls = [-10 ** 10] * (N + 1)
rs = [10 ** 10] * (N + 1)
Q = dq([])
h = []
res = [-10 ** 10] * (N + 1)
for _ in range(K):
	(x, v) = map(int, input().split())
	ls[x] = v
	rs[x] = v
	hpush(h, (v, x))
	res[x] = v
	Q.append(x)
vis = [0] * (N + 1)
while len(Q):
	x = Q.popleft()
	if vis[x]:
		continue
	vis[x] = 1
	for y in e[x]:
		ls[y] = max(ls[y], ls[x] - 1)
		rs[y] = min(rs[y], rs[x] + 1)
		if ls[y] % 2 == ls[x] % 2:
			print('No')
			exit(0)
		if vis[y]:
			continue
		Q.append(y)
for x in range(1, N + 1):
	if ls[x] > rs[x]:
		print('No')
		exit(0)
while len(h):
	(_, x) = hpop(h)
	for y in e[x]:
		if res[y] != -10 ** 10:
			continue
		res[y] = res[x] + 1
		hpush(h, (res[y], y))
print('Yes')
for r in res[1:]:
	print(r)


import sys
sys.setrecursionlimit(10 ** 6)
INF = 10 ** 7
n = int(input())
edge = [[] for _ in range(n)]
for i in range(n - 1):
	(u, v) = [int(item) - 1 for item in input().split()]
	edge[u].append(v)
	edge[v].append(u)
k = int(input())
number = [-INF] * n
for i in range(k):
	(v, c) = [int(item) for item in input().split()]
	number[v - 1] = c
min_c = [-INF] * n
max_c = [INF] * n
odd = [-1] * n

def dfs(v, prev):
	if len(edge[v]) == 1 and prev is not -1:
		if number[v] != -INF:
			min_c[v] = number[v]
			max_c[v] = number[v]
			odd[v] = number[v] % 2
		return
	l = -INF
	r = INF
	for item in edge[v]:
		if item == prev:
			continue
		dfs(item, v)
		if odd[v] == -1 and odd[item] != -1:
			odd[v] = (odd[item] + 1) % 2
		l = max(l, min_c[item] - 1)
		r = min(r, max_c[item] + 1)
		if odd[item] is not -1 and odd[v] == odd[item]:
			print('No')
			exit()
	min_c[v] = l
	max_c[v] = r
	if l > r:
		print('No')
		exit()
	if r == l and r % 2 != odd[v]:
		print('No')
		exit()
	if number[v] != -INF:
		if not l <= number[v] <= r:
			print('No')
			exit()
		min_c[v] = number[v]
		max_c[v] = number[v]
		odd[v] = number[v] % 2
	return
ans = [-INF] * n

def build(v, prev):
	if prev == -1:
		for item in range(min_c[v], max_c[v] + 1):
			if item % 2 == odd[v] or odd[v] == -1:
				ans[v] = item
				break
	elif min_c[v] <= ans[prev] + 1 <= max_c[v]:
		ans[v] = ans[prev] + 1
	else:
		ans[v] = ans[prev] - 1
	for item in edge[v]:
		if item == prev:
			continue
		build(item, v)
	return
dfs(0, -1)
print('Yes')
build(0, -1)
for item in ans:
	print(item)


from collections import deque
import sys
sys.setrecursionlimit(int(10000000.0))

def inpl():
	return list(map(int, input().split()))
N = int(input())
G = [[] for _ in range(N + 1)]
X = [-1 for _ in range(N + 1)]
U = [10000000.0 for _ in range(N + 1)]
L = [-10000000.0 for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b) = inpl()
	G[a].append(b)
	G[b].append(a)
K = int(input())
for _ in range(K):
	(v, p) = inpl()
	(U[v], L[v], X[v]) = (p, p, p % 2)
searched = [0] * (N + 1)

def dfs(u, l, x, i):
	searched[i] = True
	if X[i] >= 0 and X[i] != x:
		X[i] = 2
		return (-10000000.0, 10000000.0)
	U[i] = min(U[i], u)
	L[i] = max(L[i], l)
	X[i] = x
	for j in G[i]:
		if searched[j]:
			continue
		(nu, nl) = dfs(U[i] + 1, L[i] - 1, (X[i] + 1) % 2, j)
		U[i] = min(U[i], nu + 1)
		L[i] = max(L[i], nl - 1)
	return (U[i], L[i])
dfs(U[v], L[v], X[v], v)
Q = [v]
searched = [0] * (N + 1)
answer = [0] * (N + 1)
answer[v] = U[v]
OK = True
if max(X) == 2:
	OK = False
	Q = []
while Q:
	p = Q.pop()
	for q in G[p]:
		if searched[q]:
			continue
		searched[q] = True
		Q.append(q)
		if L[q] <= answer[p] + 1 <= U[q]:
			answer[q] = answer[p] + 1
		elif L[q] <= answer[p] - 1 <= U[q]:
			answer[q] = answer[p] - 1
		else:
			OK = False
			Q = []
			break
if OK:
	print('Yes')
	print(*answer[1:], sep='\n')
else:
	print('No')


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	edge[a].append(b)
	edge[b].append(a)
K = int(input())
res = [-1] * N
for i in range(K):
	(v, p) = map(int, input().split())
	v -= 1
	if i == 0:
		root = v
	res[v] = p
dist = [-1] * N
parent = [-1] * N
dist[root] = 0
order = []
node = [root]
bm = (dist[root] ^ res[root]) & 1
while node:
	s = node.pop()
	order.append(s)
	if res[s] != -1 and bm != (dist[s] ^ res[s]) & 1:
		print('No')
		exit()
	for t in edge[s]:
		if dist[t] != -1:
			continue
		parent[t] = s
		dist[t] = dist[s] + 1
		node.append(t)
inf = 10 ** 18
inf = float('inf')
U = [inf] * N
L = [-inf] * N
for v in order[::-1]:
	if res[v] != -1:
		if res[v] < L[v] or U[v] < res[v]:
			print('No')
			exit()
		U[v] = res[v]
		L[v] = res[v]
	if v != root:
		p = parent[v]
		if L[v] - 1 > U[p] or U[v] + 1 < L[p]:
			print('No')
			exit()
		L[p] = max(L[p], L[v] - 1)
		U[p] = min(U[p], U[v] + 1)
for v in order[1:]:
	p = parent[v]
	if L[v] <= res[p] + 1 <= U[v]:
		res[v] = res[p] + 1
	else:
		res[v] = res[p] - 1
print('Yes')
print(*res, sep='\n')


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict
import queue
INF = float('inf')

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

class Graph(object):

	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

class BFS(object):

	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		self.visit = ['No'] * N
		self.visit[s] = 'Yes'
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == 'No':
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = 'Yes'

def DFS(G, MAX, MIN, visit, node):
	for i in G.graph[node]:
		if visit[i] != 'Yes':
			visit[i] = 'Yes'
			DFS(G, MAX, MIN, visit, i)
			MAX[node] = min(MAX[node], MAX[i] + 1)
			MIN[node] = max(MIN[node], MIN[i] - 1)

class BFS2(object):

	def __init__(self, graph, s, N, MAX, MIN):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.visit = ['No'] * N
		self.visit[s] = 'Yes'
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == 'No':
					self.visit[i] = 'Yes'
					self.Q.put(i)
					MAX[i] = min(MAX[i], MAX[v] + 1)
					MIN[i] = max(MIN[i], MIN[v] - 1)

def main():
	N = int(input())
	G = Graph()
	for i in range(N - 1):
		(a, b) = getlist()
		a -= 1
		b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)
	K = int(input())
	MAX = [INF] * N
	MIN = [-INF] * N
	for i in range(K):
		(V, P) = getlist()
		V -= 1
		MAX[V] = P
		MIN[V] = P
	BF = BFS(G, V, N)
	dist = BF.dist
	odd_even = [0, 0]
	for i in range(N):
		if MAX[i] != INF:
			if MAX[i] & 1 == dist[i] & 1:
				odd_even[0] += 1
			else:
				odd_even[1] += 1
	if odd_even[0] * odd_even[1] > 0:
		print('No')
		return
	visit = ['No'] * N
	visit[V] = 'Yes'
	DFS(G, MAX, MIN, visit, V)
	BF2 = BFS2(G, V, N, MAX, MIN)
	judge = 'Yes'
	for i in range(N):
		if MAX[i] < MIN[i]:
			judge = 'No'
			break
	if judge == 'No':
		print(judge)
		return
	print('Yes')
	for i in MAX:
		print(i)
main()


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
tr = [list() for _ in range(n)]
num = [None] * n
ran = [0] * n
dep = [0] * n
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	tr[a].append(b)
	tr[b].append(a)
k = int(input())
(root, c) = map(int, input().split())
root -= 1
num[root] = c

def dfs(v, p, dep):
	for x in tr[v]:
		if x == p:
			continue
		dep[x] = dep[v] + 1
		dfs(x, v, dep)
	return
dfs(root, -1, dep)
for _ in range(k - 1):
	(v, c) = map(int, input().split())
	v -= 1
	if abs(c - num[root]) > dep[v] or dep[v] % 2 != (c - num[root]) % 2:
		print('No')
		exit(0)
	num[v] = c

def dfs2(v, p, ran):
	cur = [-10 ** 9, 10 ** 9] if num[v] is None else [num[v], num[v]]
	if tr[v] == [p]:
		ran[v] = tuple(cur)
		return
	for x in tr[v]:
		if x == p:
			continue
		dfs2(x, v, ran)
		if ran[x][0] > cur[0]:
			cur[0] = ran[x][0]
		if ran[x][1] < cur[1]:
			cur[1] = ran[x][1]
	cur[0] -= 1
	cur[1] += 1
	ran[v] = tuple(cur)
	return
dfs2(root, None, ran)
q = [(root, None)]
while q:
	(v, p) = q.pop()
	for x in tr[v]:
		if x == p:
			continue
		if ran[x][0] <= num[v] + 1 <= ran[x][1]:
			num[x] = num[v] + 1
		elif ran[x][0] <= num[v] - 1 <= ran[x][1]:
			num[x] = num[v] - 1
		else:
			print('No')
			exit(0)
		q.append((x, v))
print('Yes')
for c in num:
	print(c)


import sys
readline = sys.stdin.readline

def getpar(Edge, p):
	N = len(Edge)
	par = [0] * N
	par[0] = -1
	par[p] - 1
	stack = [p]
	visited = set([p])
	while stack:
		vn = stack.pop()
		for vf in Edge[vn]:
			if vf in visited:
				continue
			visited.add(vf)
			par[vf] = vn
			stack.append(vf)
	return par

def topological_sort_tree(E, r):
	Q = [r]
	L = []
	visited = set([r])
	while Q:
		vn = Q.pop()
		L.append(vn)
		for vf in E[vn]:
			if vf not in visited:
				visited.add(vf)
				Q.append(vf)
	return L

def getcld(p):
	res = [[] for _ in range(len(p))]
	for (i, v) in enumerate(p[1:], 1):
		res[v].append(i)
	return res

def check(L, Par, wri, even):
	for i in range(len(Par)):
		if wri[i] and wri[i] % 2 == even[i]:
			return False
	inf = 10 ** 9 + 7
	dpu = [w if w is not None else inf for w in wri]
	dpd = [w if w is not None else -inf for w in wri]
	for l in L[::-1][:-1]:
		if dpu[l] == inf:
			continue
		if dpd[l] > dpu[l]:
			return False
		p = Par[l]
		dpu[p] = min(dpu[p], dpu[l] + 1)
		dpd[p] = max(dpd[p], dpd[l] - 1)
	if dpd[root] > dpu[root]:
		return False
	ans = [None] * N
	ans[root] = wri[root]
	for l in L[1:]:
		p = Par[l]
		if ans[p] - 1 >= dpd[l]:
			ans[l] = ans[p] - 1
		else:
			ans[l] = ans[p] + 1
	return ans
N = int(readline())
Edge = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, readline().split())
	a -= 1
	b -= 1
	Edge[a].append(b)
	Edge[b].append(a)
K = int(readline())
VP = [tuple(map(lambda x: int(x), readline().split())) for _ in range(K)]
wri = [None] * N
for (v, p) in VP:
	wri[v - 1] = p
root = VP[0][0] - 1
Par = getpar(Edge, root)
L = topological_sort_tree(Edge, root)
even = [True] * N
even[root] = wri[root] % 2 == 0
for l in L[1:]:
	p = Par[l]
	even[l] = not even[p]
ans = check(L, Par, wri, even)
if ans == False:
	print('No')
else:
	print('Yes')
	print('\n'.join(map(str, ans)))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
G = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(A, B) = map(int, input().split())
	G[A].append(B)
	G[B].append(A)
K = int(input())
num = [-1] * (N + 1)
for _ in range(K):
	(V, P) = map(int, input().split())
	num[V] = P
stack = [1]
depth = [-1] * (N + 1)
depth[1] = 0
while stack:
	v = stack.pop()
	for c in G[v]:
		if depth[c] == -1:
			depth[c] = depth[v] + 1
			stack.append(c)
parity = [set(), set()]
for i in range(1, N + 1):
	if num[i] != -1:
		parity[depth[i] % 2].add(num[i] % 2)
if len(parity[0]) == 2 or len(parity[1]) == 2:
	print('No')
	exit()
INF = 10 ** 9
lb = [-INF] * (N + 1)
ub = [INF] * (N + 1)

def dfs1(v, p):
	for c in G[v]:
		if c == p:
			continue
		dfs1(c, v)
		lb[v] = max(lb[v], lb[c] - 1)
		ub[v] = min(ub[v], ub[c] + 1)
	if num[v] != -1:
		lb[v] = ub[v] = num[v]
dfs1(1, 0)

def dfs2(v, p):
	if lb[v] > ub[v]:
		print('No')
		exit()
	for c in G[v]:
		if c == p:
			continue
	for c in G[v]:
		if c == p:
			continue
		lb[c] = max(lb[c], lb[v] - 1)
		ub[c] = min(ub[c], ub[v] + 1)
		if lb[c] <= num[v] - 1:
			num[c] = num[v] - 1
		else:
			num[c] = num[v] + 1
		dfs2(c, v)
num[1] = lb[1]
dfs2(1, 0)
print('Yes')
print(*num[1:], sep='\n')


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

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

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

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

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

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

def SI():
	return sys.stdin.readline()[:-1]

def main():

	def imp():
		print('No')
		exit()
	n = II()
	to = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = MI1()
		to[u].append(v)
		to[v].append(u)
	k = II()
	pp = [-1] * n
	for _ in range(k):
		(v, p) = MI()
		pp[v - 1] = p
	dp = [[-1, -1, -1] for _ in range(n)]

	def dfs(u=0, pu=-1):
		par = mn = mx = -1
		for v in to[u]:
			if v == pu:
				continue
			dfs(v, u)
			(pv, mnv, mxv) = dp[v]
			if pv == -1:
				continue
			if par == -1:
				(par, mn, mx) = (1 - pv, mnv - 1, mxv + 1)
			else:
				if par ^ pv == 0:
					imp()
				mn = max(mn, mnv - 1)
				mx = min(mx, mxv + 1)
				if mn > mx:
					imp()
		p = pp[u]
		if p == -1:
			dp[u] = [par, mn, mx]
		elif par != -1 and (p & 1 != par or p < mn or p > mx):
			imp()
		else:
			dp[u] = [p & 1, p, p]
	dfs()
	for p0 in range(dp[0][1], dp[0][2] + 1):
		if p0 & 1 == dp[0][0]:
			pp[0] = p0
			break
	else:
		imp()

	def dfs2(u=0, pu=-1):
		if pp[u] == -1:
			p = pp[pu]
			for d in [1, -1]:
				if dp[u][0] == -1 or dp[u][1] <= p + d <= dp[u][2]:
					pp[u] = p + d
					break
		for v in to[u]:
			if v == pu:
				continue
			dfs2(v, u)
	dfs2()
	print('Yes')
	for p in pp:
		print(p)
main()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N = int(input())
edge = {i: [] for i in range(1, N + 1)}
for i in range(0, N - 1):
	(a, b) = map(int, input().split())
	edge[a].append(b)
	edge[b].append(a)
K = int(input())
dic = {}
for i in range(K):
	(v, p) = map(int, input().split())
	dic[v] = 0
	dic[v] = p
memo = {i: [] for i in range(1, N + 1)}
flag = {i: True for i in range(2, N + 1)}

def dfs(num):
	flag[num] = False
	if memo[num]:
		return memo[num]
	if num != 1 and len(edge[num]) == 1:
		if num in dic.keys():
			memo[num] = [dic[num], dic[num], dic[num] % 2]
			return memo[num]
		else:
			memo[num] = [-float('inf'), float('inf'), 2]
		return memo[num]
	ansl = -float('inf')
	ansr = float('inf')
	anseo = 2
	if num in dic.keys():
		ansl = dic[num]
		ansr = dic[num]
		anseo = dic[num] % 2
	for i in edge[num]:
		if flag[i]:
			(l, r, eo) = dfs(i)
			if eo != 2:
				eo = (eo + 1) % 2
			if anseo == 2:
				ansr = min(ansr, r + 1)
				ansl = max(ansl, l - 1)
				anseo = eo
				if ansl > ansr:
					print('No')
					exit()
			else:
				ansr = min(ansr, r + 1)
				ansl = max(ansl, l - 1)
				if ansl > ansr or (eo != 2 and eo != anseo):
					print('No')
					exit()
	memo[num] = [ansl, ansr, anseo]
	return memo[num]
(l, r, eo) = dfs(1)
print('Yes')
ans = {i: -float('inf') for i in range(1, N + 1)}
flag = {i: True for i in range(2, N + 1)}
ans[1] = l
flag[1] = False
q = set([(1, ans[1])])
sub = set([])
while q:
	while q:
		(node, num) = q.pop()
		for i in edge[node]:
			if flag[i]:
				flag[i] = False
				(l, r, eo) = memo[i]
				if r >= num - 1 >= l:
					ans[i] = num - 1
				else:
					ans[i] = num + 1
				sub.add((i, ans[i]))
		if not q:
			q = sub
			sub = set([])
			break
for i in range(1, N + 1):
	print(ans[i])


import sys
sys.setrecursionlimit(10 ** 7)

def dfs(v, parent, odd):
	hi = INF
	lo = -INF
	if fixed[v] != INF:
		if odd_even[v] != odd:
			print('No')
			exit()
		hi = lo = fixed[v]
	for u in links[v]:
		if u == parent:
			continue
		(chi, clo) = dfs(u, v, odd ^ 1)
		if hi < clo or chi < lo:
			print('No')
			exit()
		hi = min(hi, chi)
		lo = max(lo, clo)
	upper[v] = hi
	lower[v] = lo
	return (hi + 1, lo - 1)

def fill(v, parent, pp):
	if pp + 1 > upper[v]:
		assert pp - 1 >= lower[v]
		vp = fixed[v] = pp - 1
	else:
		vp = fixed[v] = pp + 1
	for u in links[v]:
		if u == parent:
			continue
		fill(u, v, vp)
inp = list(map(int, sys.stdin.buffer.read().split()))
n = inp[0]
links = [set() for _ in range(n)]
for (a, b) in zip(inp[1:2 * n - 1:2], inp[2:2 * n - 1:2]):
	a -= 1
	b -= 1
	links[a].add(b)
	links[b].add(a)
INF = 10 ** 9
k = inp[2 * n - 1]
fixed = [INF] * n
odd_even = {}
fixed_v = 0
for (v, p) in zip(inp[2 * n::2], inp[2 * n + 1::2]):
	v -= 1
	fixed[v] = p
	odd_even[v] = p % 2
	fixed_v = v
lower = [-INF] * n
upper = [INF] * n
dfs(fixed_v, -1, odd_even[fixed_v])
fill(fixed_v, -1, fixed[fixed_v] + 1)
print('Yes')
print('\n'.join(map(str, fixed)))


def N():
	return int(input())

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

def L():
	return list(NM())

def LN(n):
	return [N() for i in range(n)]

def LL(n):
	return [L() for i in range(n)]
n = N()
edge = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	edge[a].append(b)
	edge[b].append(a)
INF = float('inf')
ma = [INF] * (n + 1)
mi = [-INF] * (n + 1)
k = N()
vp = LL(k)
for (v, p) in vp:
	ma[v] = p
	mi[v] = p
import sys
sys.setrecursionlimit(10 ** 6)

def dfs(v, d, hi, lo):
	dep[v] = d
	ma[v] = min(ma[v], hi)
	mi[v] = max(mi[v], lo)
	hi = ma[v]
	lo = mi[v]
	for i in edge[v]:
		if dep[i] == -1:
			(hi, lo) = dfs(i, d + 1, hi + 1, lo - 1)
			ma[v] = min(ma[v], hi)
			mi[v] = max(mi[v], lo)
			hi = ma[v]
			lo = mi[v]
	return (hi + 1, lo - 1)
for i in range(2):
	dep = [-1 for i in range(n + 1)]
	dfs(v, 0, p, p)
for (i, j) in zip(mi, ma):
	if i > j or (i - j) % 2 == 1:
		print('No')
		break
else:
	print('Yes')
	for i in mi[1:]:
		print(i)


import sys
sys.setrecursionlimit(5 * 10 ** 5)
N = int(input())
lis = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	lis[a].append(b)
	lis[b].append(a)
l = [float('-inf')] * N
r = [float('inf')] * N
K = int(input())
for i in range(K):
	(V, P) = map(int, input().split())
	V -= 1
	l[V] = P
	r[V] = P

def dfs(v, p):
	for nex in lis[v]:
		if nex != p:
			(nl, nr) = dfs(nex, v)
			if l[v] != float('-inf') and nl != float('-inf') and (l[v] % 2 != nl % 2):
				print('No')
				sys.exit()
			l[v] = max(l[v], nl)
			r[v] = min(r[v], nr)
			if l[v] > r[v]:
				print('No')
				sys.exit()
	return (l[v] - 1, r[v] + 1)
dfs(0, 0)
from collections import deque
q = deque([0])
unvisit = [True] * N
ans = [None] * N
ans[0] = l[0]
while len(q) > 0:
	v = q.popleft()
	unvisit[v] = False
	if l[v] > r[v]:
		print('No')
		sys.exit()
	for nex in lis[v]:
		if unvisit[nex]:
			if l[nex] != float('-inf') and l[v] != float('-inf') and (l[v] % 2 == l[nex] % 2):
				print('No')
				sys.exit()
			l[nex] = max(l[nex], l[v] - 1)
			r[nex] = min(r[nex], r[v] + 1)
			ans[nex] = l[nex]
			q.append(nex)
print('Yes')
for i in ans:
	print(i)


import heapq
import sys
input = sys.stdin.readline
INF = 10 ** 18
n = int(input())
edges = [list(map(int, input().split())) for i in range(n - 1)]
k = int(input())
info = [list(map(int, input().split())) for i in range(k)]
tree = [[] for i in range(n)]
for (a, b) in edges:
	a -= 1
	b -= 1
	tree[a].append(b)
	tree[b].append(a)
ans = [INF] * n
q = []
for (v, val) in info:
	v -= 1
	ans[v] = val
	heapq.heappush(q, (-val, v))
	for nxt_v in tree[v]:
		if ans[nxt_v] != INF and abs(ans[v] - ans[nxt_v]) != 1:
			print('No')
			return
while q:
	(val, v) = heapq.heappop(q)
	val = -val
	for nxt_v in tree[v]:
		if ans[nxt_v] == INF:
			ans[nxt_v] = val - 1
			heapq.heappush(q, (-(val - 1), nxt_v))
		elif abs(ans[v] - ans[nxt_v]) != 1:
			print('No')
			return
print('Yes')
for val in ans:
	print(val)


import sys
sys.setrecursionlimit(10 ** 7)

def main0(n, ab, k, vp):
	ki = [[] for _ in range(n)]
	for (a, b) in ab:
		(a, b) = (a - 1, b - 1)
		ki[a].append(b)
		ki[b].append(a)
	lrf = [[-1, -1, -1] for _ in range(n)]
	for (v, p) in vp:
		v -= 1
		lrf[v] = [p, p, p % 2]
	flg = [True]

	def func(p, v):
		if lrf[v][2] != -1:
			(l, r, f) = lrf[v]
			if p >= 0:
				(pl, pr, pf) = lrf[p]
				if pl - 1 <= l <= pr + 1 and pf ^ f == 1:
					pass
				else:
					flg[0] = False
		else:
			(pl, pr, pf) = lrf[p]
			(l, r, f) = (pl - 1, pr + 1, pf ^ 1)
			lrf[v] = [l, r, f]
		(l, r, f) = lrf[v]
		for nv in ki[v]:
			if nv == p:
				continue
			(nl, nr, nf) = func(v, nv)
			if f ^ nf == 0:
				flg[0] = False
			l = max(l, nl - 1)
			r = min(r, nr + 1)
			if l > r:
				flg[0] = False
		lrf[v] = [l, r, f]
		return (l, r, f)
	func(-1, vp[0][0] - 1)
	if not flg[0]:
		return []
	ret = [0] * n

	def func0(p, v):
		(l, r, f) = lrf[v]
		np = ret[p]
		if l <= np - 1 <= r and (np - 1) % 2 == f:
			ret[v] = np - 1
		elif l <= np + 1 <= r and (np + 1) % 2 == f:
			ret[v] = np + 1
		else:
			flg[0] = False
		for nv in ki[v]:
			if nv != p:
				func0(v, nv)
	ret[vp[0][0] - 1] = vp[0][1]
	for nv in ki[vp[0][0] - 1]:
		func0(vp[0][0] - 1, nv)
	if flg[0]:
		return ret
	else:
		return []

def __starting_point():
	n = int(input())
	ab = [list(map(int, input().split())) for _ in range(n - 1)]
	k = int(input())
	vp = [list(map(int, input().split())) for _ in range(k)]
	ret0 = main0(n, ab, k, vp)
	if len(ret0) == 0:
		print('No')
	else:
		print('Yes')
		for x in ret0:
			print(x)
__starting_point()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 10
n = int(input())
T = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	T[a].append(b)
	T[b].append(a)
k = int(input())
VP = tuple((tuple(map(int, input().split())) for _ in range(k)))
P = [-1] * (n + 1)
A = [-1] * (n + 1)
(r, c) = VP[0]
for (v, p) in VP:
	P[v] = p

def dfs1(v, par=-1, color=c % 2):
	if P[v] == -1:
		l = -INF
		r = INF
	else:
		l = P[v]
		r = P[v]
	for nv in T[v]:
		if nv == par:
			continue
		(nl, nr) = dfs1(nv, v, color ^ 1)
		l = max(l, nl - 1)
		r = min(r, nr + 1)
	if l & 1 ^ color:
		l += 1
	if r & 1 ^ color:
		r -= 1
	if l > r:
		print('No')
		exit()
	P[v] = (l, r)
	return P[v]
dfs1(r)

def dfs2(v, ini, par=-1):
	(l, r) = P[v]
	if l == r:
		A[v] = l
	elif l <= ini - 1 <= r:
		A[v] = ini - 1
	else:
		A[v] = ini + 1
	for nv in T[v]:
		if nv == par:
			continue
		dfs2(nv, A[v], v)
dfs2(r, P[r][0])
print('Yes')
print(*A[1:], sep='\n')


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul
mod = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
INF = 10 ** 13

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

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

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
n = I()
G = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = LI()
	G[a - 1] += [b - 1]
	G[b - 1] += [a - 1]
cond = [(-INF, INF) for _ in range(n)]
k = I()
for _ in range(k):
	(v, p) = LI()
	cond[v - 1] = (p, p)
ans = [0] * n
visited = [0] * n

def f(u):
	visited[u] = 1
	max_ret = cond[u][1]
	min_ret = cond[u][0]
	u_flg = max_ret % 2 if max_ret == min_ret else -1
	for v in G[u]:
		if visited[v]:
			continue
		(x, y, flg) = f(v)
		if flg != -1 and u_flg == flg:
			print('No')
			exit()
		max_ret = min(max_ret, y + 1)
		min_ret = max(min_ret, x - 1)
	if min_ret > max_ret:
		print('No')
		exit()
	cond[u] = (min_ret, max_ret)
	return (min_ret, max_ret, u_flg)
f(0)
print('Yes')
visited = [0] * n
ans = [-1] * n
ans[0] = cond[0][0]

def f2(u):
	visited[u] = 1
	for v in G[u]:
		if visited[v]:
			continue
		ans[v] = ans[u] + 1 if cond[v][0] <= ans[u] + 1 <= cond[v][1] else ans[u] - 1
		f2(v)
f2(0)
print(*ans, sep='\n')


from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
adj = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(A, B) = map(int, input().split())
	adj[A].append(B)
	adj[B].append(A)
K = int(input())
ans = [[-10 ** 10 + 0.5, 10 ** 10 + 0.5] for _ in range(N + 1)]
for _ in range(K):
	(V, P) = map(int, input().split())
	ans[V] = [P, P]

def check(par, chi):
	(par_min, par_max) = ans[par]
	(chi_min, chi_max) = ans[chi]
	if (par_min - chi_min) % 2 == 0:
		print('No')
		sys.exit()
	if par_min - 1 > chi_max or par_max + 1 < chi_min:
		print('No')
		sys.exit()
	ans[chi] = [max(par_min - 1, chi_min), min(par_max + 1, chi_max)]
que = deque()
que.append(V)
seen = [0] * (N + 1)
parent = [0] * (N + 1)
v_list = []
while que:
	v = que.pop()
	seen[v] = 1
	v_list.append(v)
	for u in adj[v]:
		if seen[u] == 0:
			parent[u] = v
			check(v, u)
			que.append(u)
v_list.reverse()
for v in v_list[:-1]:
	u = parent[v]
	check(v, u)
que = deque()
que.append(V)
seen = [0] * (N + 1)
while que:
	v = que.pop()
	seen[v] = 1
	for u in adj[v]:
		if seen[u] == 0:
			check(v, u)
			que.append(u)
print('Yes')
for i in range(1, N + 1):
	print(ans[i][0])


import sys
input = lambda : sys.stdin.readline().rstrip()
from collections import deque
N = int(input())
X = [[] for i in range(N)]
for i in range(N - 1):
	(x, y) = map(int, input().split())
	X[x - 1].append(y - 1)
	X[y - 1].append(x - 1)
Y = [(-10 ** 9, 10 ** 9) for _ in range(N)]
K = int(input())
for _ in range(K):
	(v, p) = map(int, input().split())
	Y[v - 1] = (p, p)
P = [-1] * N
Q = deque([0])
R = []
while Q:
	i = deque.popleft(Q)
	R.append(i)
	for a in X[i]:
		if a != P[i]:
			P[a] = i
			X[a].remove(i)
			deque.append(Q, a)

def calc():
	for i in R[::-1]:
		(e, o) = (0, 0)
		(l, r) = Y[i]
		if r != 10 ** 9:
			if l % 2:
				o = 1
			else:
				e = 1
		for j in X[i]:
			(a, b) = Y[j]
			if b == 10 ** 9:
				continue
			if a % 2:
				e = 1
			else:
				o = 1
			l = max(l, a - 1)
			r = min(r, b + 1)
		if e and o or l > r:
			print('No')
			return 0
		elif e or o:
			Y[i] = (l, r)
	for i in R[1:]:
		if Y[P[i]][0] - 1 >= Y[i][0]:
			Y[i] = (Y[P[i]][0] - 1, 0)
		else:
			Y[i] = (Y[P[i]][0] + 1, 0)
	print('Yes')
	for i in range(N):
		print(Y[i][0])
calc()


import sys
input = sys.stdin.readline
N = int(input())
e = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(u, v) = map(int, input().split())
	e[u].append(v)
	e[v].append(u)
s = [1]
color = [0] * (N + 1)
color[1] = 1
while len(s):
	x = s.pop()
	for y in e[x]:
		if color[y]:
			if color[x] == color[y]:
				break
			continue
		s.append(y)
		color[y] = color[x] ^ 2
	else:
		continue
	print('No')
	exit(0)
res = [-1] * (N + 1)
mx = 0
for _ in range(int(input())):
	(v, p) = map(int, input().split())
	res[v] = p
	mx = max(mx, p)
table = [[] for _ in range(mx + 1 + N + 1)]
for i in range(N + 1):
	if res[i] != -1:
		table[res[i]].append(i)
for i in range(mx + N + 1):
	while len(table[i]):
		x = table[i].pop()
		for y in e[x]:
			if res[y] == -1:
				res[y] = res[x] + 1
				table[i + 1].append(y)
			elif abs(res[x] - res[y]) != 1:
				break
		else:
			continue
		break
	else:
		continue
	break
else:
	print('Yes')
	for r in res[1:]:
		print(r)
	exit(0)
print('No')


class Tree:

	def __init__(self, n, edge, indexed=1):
		self.n = n
		self.tree = [[] for _ in range(n)]
		for e in edge:
			self.tree[e[0] - indexed].append(e[1] - indexed)
			self.tree[e[1] - indexed].append(e[0] - indexed)

	def setroot(self, root):
		self.root = root
		self.parent = [None for _ in range(self.n)]
		self.parent[root] = -1
		self.depth = [None for _ in range(self.n)]
		self.depth[root] = 0
		self.order = []
		self.order.append(root)
		stack = [root]
		while stack:
			node = stack.pop()
			for adj in self.tree[node]:
				if self.parent[adj] is None:
					self.parent[adj] = node
					self.depth[adj] = self.depth[node] + 1
					self.order.append(adj)
					stack.append(adj)
INF = 10 ** 18
import sys
input = sys.stdin.readline
N = int(input())
E = [tuple(map(int, input().split())) for _ in range(N - 1)]
num = [None for _ in range(N)]
K = int(input())
for _ in range(K):
	(v, p) = map(int, input().split())
	num[v - 1] = p
tree = Tree(N, E)
tree.setroot(v - 1)
even = []
odd = []
for i in range(N):
	if num[i] is not None:
		if tree.depth[i] % 2 == 0:
			even.append(num[i] % 2)
		else:
			odd.append(num[i] % 2)
if not ((all(even) or not any(even)) and (all(odd) or not any(odd))):
	print('No')
else:
	I = [[-INF, INF] for _ in range(N)]
	for i in range(N):
		if num[i] is not None:
			I[i] = [num[i], num[i]]
	for node in tree.order[::-1]:
		(lt, rt) = I[node]
		for adj in tree.tree[node]:
			lt = max(lt, I[adj][0] - 1)
			rt = min(rt, I[adj][1] + 1)
		if lt > rt:
			print('No')
			break
		I[node] = [lt, rt]
	else:
		stack = [v - 1]
		visited = [0 for _ in range(N)]
		visited[v - 1] = 1
		while stack:
			node = stack.pop()
			for adj in tree.tree[node]:
				if visited[adj]:
					continue
				visited[adj] = 1
				if I[adj][0] <= num[node] - 1 <= I[adj][1]:
					num[adj] = num[node] - 1
				elif I[adj][0] <= num[node] + 1 <= I[adj][1]:
					num[adj] = num[node] + 1
				else:
					print('No')
					break
				stack.append(adj)
			else:
				continue
			break
		else:
			print('Yes')
			print('\n'.join(map(str, num)))