Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import Counter
from math import gcd

n = int(input())
xys = [tuple(map(int, input().split())) for _ in range(n)]
MOD = 998244353

excludes = 0
for i, (x1, y1) in enumerate(xys):
    slopes = []
    for x2, y2 in xys[i + 1:]:
        dx, dy = x2 - x1, y2 - y1
        if dx == 0:
            slopes.append(1j)
        elif dy == 0:
            slopes.append(1)
        else:
            m = gcd(dx, dy)
            slopes.append(dx // m + dy // m * 1j)
    for c in Counter(slopes).values():
        if c > 1:
            excludes += 2 ** c - c - 1
    excludes %= MOD

print((pow(2, n, MOD) - excludes - (n * (n - 1) // 2) - n - 1) % MOD)


Fixed submission:
from collections import Counter
from fractions import gcd

n = int(input())
xys = [tuple(map(int, input().split())) for _ in range(n)]
MOD = 998244353

excludes = 0
for i, (x1, y1) in enumerate(xys):
    slopes = []
    for x2, y2 in xys[i + 1:]:
        dx, dy = x2 - x1, y2 - y1
        if dx == 0:
            slopes.append(1j)
        elif dy == 0:
            slopes.append(1)
        else:
            m = gcd(dx, dy)
            slopes.append(dx // m + dy // m * 1j)
    for c in Counter(slopes).values():
        if c > 1:
            excludes += 2 ** c - c - 1
    excludes %= MOD

print((pow(2, n, MOD) - excludes - (n * (n - 1) // 2) - n - 1) % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappush, heappop

n = int(input())
cities = [tuple(map(int, input().split())) for _ in range(n)]
visited = {0}
x0, y0 = cities[0]
queue = [(min(abs(xi - x0), abs(yi - y0)), i) for i, (xi, yi) in enumerate(cities) if i not in visited]
heapify(queue)
total = 0
while True:
    cost, i = heappop(queue)
    if i in visited:
        continue
    visited.add(i)
    total += cost
    if len(visited) == n:
        break
    xi, yi = cities[i]
    for j, (xj, yj) in enumerate(cities):
        if j in visited:
            continue
        heappush(queue, (min(abs(xj - xi), abs(yj - yi)), j))
print(total)


Fixed submission:
from heapq import heapify, heappush, heappop

n = int(input())
x_loc, y_loc = [], []
for i in range(n):
    x, y = map(int, input().split())
    x_loc.append((x, i))
    y_loc.append((y, i))
x_loc.sort()
y_loc.sort()
links = [set() for _ in range(n)]
for (x1, i1), (x2, i2) in zip(x_loc, x_loc[1:]):
    dist = abs(x1 - x2)
    links[i1].add((dist, i2))
    links[i2].add((dist, i1))
for (y1, i1), (y2, i2) in zip(y_loc, y_loc[1:]):
    dist = abs(y1 - y2)
    links[i1].add((dist, i2))
    links[i2].add((dist, i1))

visited = {0}
queue = list(links[0])
heapify(queue)
total = 0
while True:
    cost, i = heappop(queue)
    if i in visited:
        continue
    visited.add(i)
    total += cost
    if len(visited) == n:
        break
    for cost2, j in links[i]:
        if j in visited:
            continue
        heappush(queue, (cost2, j))
print(total)
Buggy python submission (verdict: Runtime Error):
import sys

import numpy as np


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, k = map(int, input().split())
aaa = np.fromiter(sys.stdin, dtype=np.int64)
aaa = np.insert(aaa, 0, 0)
acc = np.add.accumulate(aaa) - np.arange(0, k * n + 1, k)
dct = {v: i for i, v in enumerate(np.unique(acc), start=1)}
bit = Bit(n)
ans = 0
for d in acc:
    i = dct[d]
    ans += bit.sum(i)
    bit.add(i, 1)
print(ans)


Fixed submission:
import sys

import numpy as np


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, k = map(int, input().split())
aaa = np.fromiter(sys.stdin, dtype=np.int64)
aaa = np.insert(aaa, 0, 0)
acc = np.add.accumulate(aaa) - np.arange(0, k * n + 1, k)
dct = {v: i for i, v in enumerate(np.unique(acc), start=1)}
bit = Bit(len(dct))
ans = 0
for d in acc:
    i = dct[d]
    ans += bit.sum(i)
    bit.add(i, 1)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

n, m, q = map(int, input().split())
sss = [input() for _ in range(n)]
dp1 = [[0] * (m + 1) for _ in range(n + 1)]
dpv = [[0] * (m + 1) for _ in range(n + 1)]
dph = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(n):
    for j in range(m):
        is1 = sss[i][j] == '1'
        additional = 0

        if is1:
            dp1[i + 1][j + 1] = 1

            if i > 0 and sss[i - 1][j] == '1':
                dpv[i + 1][j + 1] = 1
            if j > 0 and sss[i][j - 1] == '1':
                dph[i + 1][j + 1] = 1

for i in range(1, n + 1):
    for j in range(1, m + 1):
        dp1[i][j] += dp1[i][j - 1]
        dpv[i][j] += dpv[i][j - 1]
        dph[i][j] += dph[i][j - 1]

for j in range(1, m + 1):
    for i in range(1, n + 1):
        dp1[i][j] += dp1[i - 1][j]
        dpv[i][j] += dpv[i - 1][j]
        dph[i][j] += dph[i - 1][j]

mp = map(int, sys.stdin.read().split())
buf = []
for x1, y1, x2, y2 in zip(mp, mp, mp, mp):
    cnt1 = dp1[x2][y2] - dp1[x1 - 1][y2] - dp1[x2][y1 - 1] + dp1[x1 - 1][y1 - 1]
    ver1 = dpv[x2][y2] - dpv[x1][y2] - dpv[x2][y1 - 1] + dpv[x1][y1 - 1]
    hor1 = dph[x2][y2] - dph[x1 - 1][y2] - dph[x2][y1] + dph[x1 - 1][y1]

    buf.append(cnt1 - ver1 - hor1)

print('\n'.join(map(str, buf)))


Fixed submission:
import sys

n, m, q = map(int, input().split())
dp1 = [[0] * (m + 1) for _ in range(n + 1)]
dpv = [[0] * (m + 1) for _ in range(n + 1)]
dph = [[0] * (m + 1) for _ in range(n + 1)]

prev_s = '0' * m

for i in range(n):
    s = input()
    for j in range(m):
        is1 = s[j] == '1'
        additional = 0

        if is1:
            dp1[i + 1][j + 1] = 1

            if i > 0 and prev_s[j] == '1':
                dpv[i + 1][j + 1] = 1
            if j > 0 and s[j - 1] == '1':
                dph[i + 1][j + 1] = 1
    prev_s = s

for i in range(1, n + 1):
    for j in range(1, m + 1):
        dp1[i][j] += dp1[i][j - 1]
        dpv[i][j] += dpv[i][j - 1]
        dph[i][j] += dph[i][j - 1]

for j in range(1, m + 1):
    for i in range(1, n + 1):
        dp1[i][j] += dp1[i - 1][j]
        dpv[i][j] += dpv[i - 1][j]
        dph[i][j] += dph[i - 1][j]

mp = map(int, sys.stdin.read().split())
buf = []
for x1, y1, x2, y2 in zip(mp, mp, mp, mp):
    cnt1 = dp1[x2][y2] - dp1[x1 - 1][y2] - dp1[x2][y1 - 1] + dp1[x1 - 1][y1 - 1]
    ver1 = dpv[x2][y2] - dpv[x1][y2] - dpv[x2][y1 - 1] + dpv[x1][y1 - 1]
    hor1 = dph[x2][y2] - dph[x1 - 1][y2] - dph[x2][y1] + dph[x1 - 1][y1]

    buf.append(cnt1 - ver1 - hor1)

print('\n'.join(map(str, buf)))
Buggy python submission (verdict: Time Limit Exceeded):
from queue import deque

n, m = map(int, input().split())
links = [None] + [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    links[a].add(b)
    links[b].add(a)

s = 1
t = links[s].pop()
visited = deque([s, t])
while True:
    s_remains = links[s].difference(visited)
    s_flag, t_flag = True, True
    if s_remains:
        s = s_remains.pop()
        visited.appendleft(s)
        s_flag = False
    t_remains = links[t].difference(visited)
    if t_remains:
        t = t_remains.pop()
        visited.append(t)
        t_flag = False
    if s_flag and t_flag:
        break
print(len(visited))
print(*visited)


Fixed submission:
from queue import deque

n, m = map(int, input().split())
links = [None] + [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    links[a].add(b)
    links[b].add(a)

s = 1
path = deque([s])
visited = {s}

while True:
    s_remains = links[s] - visited
    if s_remains:
        s = s_remains.pop()
        path.appendleft(s)
        visited.add(s)
    else:
        break

t = 1

while True:
    t_remains = links[t] - visited
    if t_remains:
        t = t_remains.pop()
        path.append(t)
        visited.add(t)
    else:
        break

print(len(path))
print(*path)
Buggy python submission (verdict: Time Limit Exceeded):
from queue import deque


def dijkstra(s, d):
    queue = deque([(0, s)])
    paint = set()
    while queue:
        cost, v = queue.popleft()
        if cost > d:
            break
        paint.add(v)
        queue.extend((cost + 1, u) for u in links[v] if u not in paint)
    return paint


n, m = map(int, input().split())
links = [None] + [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    links[a].add(b)
    links[b].add(a)

q = int(input())
queries = [map(int, input().split()) for _ in range(q)]
painted = set()
colors = [0] * (n + 1)
while queries:
    v, d, c = queries.pop()
    paint = dijkstra(v, d) - painted
    for i in paint:
        colors[i] = c
    painted |= paint

for c in colors[1:]:
    print(c)


Fixed submission:
from queue import deque


def paint(s, d, c):
    queue = deque([(d, s)])
    while queue:
        remains, v = queue.popleft()
        if painted[v] >= remains:
            continue
        if colors[v] == 0:
            colors[v] = c
        painted[v] = remains
        if remains:
            queue.extend((remains - 1, u) for u in links[v])


n, m = map(int, input().split())
links = [None] + [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    links[a].add(b)
    links[b].add(a)

q = int(input())
queries = [map(int, input().split()) for _ in range(q)]
colors = [0] * (n + 1)
painted = [-1] * (n + 1)
while queries:
    paint(*queries.pop())

for c in colors[1:]:
    print(c)
Buggy python submission (verdict: Runtime Error):
def memoize(f):
    cache = {}

    def func(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]

    return func


@memoize
def combi(n, r):
    if r == 0 or n == r:
        return 1
    return combi(n - 1, r - 1) + combi(n - 1, r)


n, a, b = map(int, input().split())
items = sorted(map(int, input().split()), reverse=True)
max_ave_list = items[:a]
print(sum(max_ave_list) / len(max_ave_list))

m = max_ave_list.count(max_ave_list[-1])
l = items.count(max_ave_list[-1])
if l == m:
    print(1)
elif max_ave_list[0] != max_ave_list[-1]:
    print(combi(l, m))
else:
    print(sum(combi(l, k) for k in range(m, max(b, l) + 1)))


Fixed submission:
import sys

sys.setrecursionlimit(10000)


def memoize(f):
    cache = {}

    def func(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]

    return func


@memoize
def combi(n, r):
    if r == 0 or n == r:
        return 1
    return combi(n - 1, r - 1) + combi(n - 1, r)


n, a, b = map(int, input().split())
items = sorted(map(int, input().split()), reverse=True)
max_ave_list = items[:a]
print(sum(max_ave_list) / len(max_ave_list))

m = max_ave_list.count(max_ave_list[-1])
l = items.count(max_ave_list[-1])
if l == m:
    print(1)
elif max_ave_list[0] != max_ave_list[-1]:
    print(combi(l, m))
else:
    print(sum(combi(l, k) for k in range(m, min(b, l) + 1)))
Buggy python submission (verdict: Time Limit Exceeded):
x = int(input())
t = 1
ds = {0}
while True:
    dc = ds.copy()
    for d in dc:
        if d + t == x or d - t == x:
            break
        ds.add(d + t)
        ds.add(d - t)
    else:
        t += 1
        continue
    break

print(t)


Fixed submission:
from math import ceil, sqrt

x = int(input())
print(ceil((-1 + sqrt(8 * x + 1)) / 2))
Buggy python submission (verdict: Time Limit Exceeded):
class UnionFind3:
    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                # 小さいほうが個数が多い
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False


n, k, l = map(int, input().split())
ufd, ufr = UnionFind3(n), UnionFind3(n)
for _ in range(k):
    p, q = map(int, input().split())
    ufd.union(p - 1, q - 1)
for _ in range(l):
    r, s = map(int, input().split())
    ufr.union(r - 1, s - 1)
result = [1] * n
for i in range(n):
    for j in range(i + 1, n):
        if ufd.find(i) == ufd.find(j) and ufr.find(i) == ufr.find(j):
            result[i] += 1
            result[j] += 1
print(*result)


Fixed submission:
from collections import defaultdict


class UnionFind3:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.root(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2


n, k, l = map(int, input().split())
ufd, ufr = UnionFind3(n), UnionFind3(n)
for _ in range(k):
    p, q = map(int, input().split())
    ufd.union(p - 1, q - 1)
for _ in range(l):
    r, s = map(int, input().split())
    ufr.union(r - 1, s - 1)
d = defaultdict(int)
for i in range(n):
    d[ufd.root(i), ufr.root(i)] += 1
print(*(d[ufd.root(i), ufr.root(i)] for i in range(n)))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
d = [11, 16, 10, 25, 9, 24, 19, 13, 18, 12, 17]
print(len([x for x in range(d[k], 7 * (n - 1), 11) if x % 7 > 1]))


Fixed submission:
n, k = map(int, input().split())
d = [11, 16, 10, 25, 9, 24, 19, 13, 18, 12, 17]
e = 7 * (n - 1)
r = (e - d[k] - 1) // 77
print(5 * r + len([x for x in range(d[k] + 77 * r, e, 11) if x % 7 > 1]))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = enumerate(map(int, input().split()))
next(p)
a = list(range(1, n + 1))
b = list(range(n, 0, -1))
for c, i in p:
    i -= 1
    a[i:] = [x + c for x in a[i:]]
    b[:i + 1] = [x + c for x in b[:i + 1]]
print(*a)
print(*b)


Fixed submission:
# numpyが使えると聞いて
import numpy as np

n = int(input())
p = enumerate(map(int, input().split()))
next(p)
a = np.arange(1, n + 1)
b = np.arange(n, 0, -1)
for c, i in p:
    i -= 1
    a[i:] += c
    b[:i + 1] += c
print(*a)
print(*b)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = enumerate(map(int, input().split()))
next(p)
a = list(range(1, n + 1))
b = list(range(n, 0, -1))
for c, i in p:
    i -= 1
    a[i:] = map(lambda x: x + c, a[i:])
    b[:i + 1] = map(lambda x: x + c, b[:i + 1])
print(*a)
print(*b)


Fixed submission:
# numpyが使えると聞いて
import numpy as np

n = int(input())
p = enumerate(map(int, input().split()))
next(p)
a = np.arange(1, n + 1)
b = np.arange(n, 0, -1)
for c, i in p:
    i -= 1
    a[i:] += c
    b[:i + 1] += c
print(*a)
print(*b)
Buggy python submission (verdict: Time Limit Exceeded):
from decimal import Decimal

n, d, x = map(Decimal, input().split())
print((d + (2 * n - 1) * x / 2) * sum((n - i) / (i + 1) for i in range(int(n))))


Fixed submission:
def solve(n, d, x):
    ans = 0
    while n:
        ans += d + (2 * n - 1) * x / 2
        d = ((n + 1) * d + 5 * x / 2) / n
        x *= (n + 2) / n
        n -= 1
    return ans


print('{:.10f}'.format(solve(*map(float, input().split()))))

Buggy python submission (verdict: Time Limit Exceeded):
from decimal import Decimal


def solve(n, d, x):
    ans = 0
    while n:
        ans += d + (2 * n - 1) * x / 2
        d = ((n + 1) * d + 5 * x / 2) / n
        x *= (n + 2) / n
        n -= 1
    return ans


print(solve(*map(Decimal, input().split())))


Fixed submission:
def solve(n, d, x):
    ans = 0
    while n:
        ans += d + (2 * n - 1) * x / 2
        d = ((n + 1) * d + 5 * x / 2) / n
        x *= (n + 2) / n
        n -= 1
    return ans


print('{:.10f}'.format(solve(*map(float, input().split()))))

Buggy python submission (verdict: Time Limit Exceeded):
import sys

from decimal import Decimal

sys.setrecursionlimit(200000)


def solve(n, d, x):
    ans = 0
    while n:
        ans += d + (2 * n - 1) * x / 2
        d = ((n + 1) * d + 5 * x / 2) / n
        x *= (n + 2) / n
        n -= 1
    return ans


print(solve(*map(Decimal, input().split())))


Fixed submission:
def solve(n, d, x):
    ans = 0
    while n:
        ans += d + (2 * n - 1) * x / 2
        d = ((n + 1) * d + 5 * x / 2) / n
        x *= (n + 2) / n
        n -= 1
    return ans


print('{:.10f}'.format(solve(*map(float, input().split()))))

Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(200000)


def solve(n, d, x):
    if not n:
        return 0
    return d + (2 * n - 1) * x / 2 + solve(n - 1, ((n + 1) * d + 5 * x / 2) / n, (n + 2) * x / n)


print(solve(*map(int, input().split())))


Fixed submission:
def solve(n, d, x):
    ans = 0
    while n:
        ans += d + (2 * n - 1) * x / 2
        d = ((n + 1) * d + 5 * x / 2) / n
        x *= (n + 2) / n
        n -= 1
    return ans


print('{:.10f}'.format(solve(*map(float, input().split()))))

Buggy python submission (verdict: Time Limit Exceeded):
import sys

from decimal import Decimal

sys.setrecursionlimit(200000)


def solve(n, d, x):
    if not n:
        return 0
    return d + (2 * n - 1) * x / 2 + solve(n - 1, ((n + 1) * d + 5 * x / 2) / n, (n + 2) * x / n)


print(solve(*map(Decimal, input().split())))


Fixed submission:
def solve(n, d, x):
    ans = 0
    while n:
        ans += d + (2 * n - 1) * x / 2
        d = ((n + 1) * d + 5 * x / 2) / n
        x *= (n + 2) / n
        n -= 1
    return ans


print('{:.10f}'.format(solve(*map(float, input().split()))))
Buggy python submission (verdict: Time Limit Exceeded):
n, e, t = map(int, input().split())
x = list(map(int, input().split()))
dp = [0] + [float('inf')] * n
for i in range(n):
    ndp = dp.copy()
    for j in range(i, n):
        ndp[j + 1] = min(dp[j + 1], dp[i] + max(t, 2 * (x[j] - x[i])))
    dp = ndp
print(e + dp[-1])


Fixed submission:
import sys
from bisect import bisect, bisect_left


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.INF = 10 ** 18
        self.tree = [self.INF] * (n + 1)

    def get_min(self, i):
        s = self.INF
        while i > 0:
            s = min(s, self.tree[i])
            i -= i & -i
        return s

    def update(self, i, x):
        while i <= self.size:
            if self.tree[i] <= x:
                break
            self.tree[i] = x
            i += i & -i


def solve(n, e, t, xxx):
    if n == 1:
        return e + t

    dp1 = [0] * (n + 1)
    dp2 = BinaryIndexedTree(n + 1)
    dp2.update(1, -xxx[0] * 2)

    for i in range(n):
        x = xxx[i]
        j = bisect_left(xxx, x - t // 2, hi=i)
        ex_time = dp1[j] + t
        if j > 0:
            ex_time = min(ex_time, x * 2 + dp2.get_min(j))
        dp1[i + 1] = ex_time
        if i < n - 1:
            dp2.update(i + 2, ex_time - xxx[i + 1] * 2)

    return e + dp1[-1]


n, e, t, *xxx = map(int, sys.stdin.buffer.read().split())
print(solve(n, e, t, xxx))
Buggy python submission (verdict: Runtime Error):
import sys


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)))


Fixed submission:
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)))
Buggy python submission (verdict: Runtime Error):
print(len({input().split()}))


Fixed submission:
print(len(set(input().split())))
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = len(s)
dp = [0]

for i, c in enumerate(s):
    new = [0] * (i + 2)
    km = c == 'g'
    for j in range(i % 2, i + 1, 2):
        new[j + 1] = dp[j] - (not km)
        if j:
            new[j - 1] = max(new[j - 1], dp[j] + km)
    dp = new

print(max(dp))


Fixed submission:
s = input()
print(len(s) // 2 - s.count('p'))

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = len(s)
dp = [0]

for i, c in enumerate(s):
    new = [0] * (i + 2)
    for j in range(i % 2, i + 1, 2):
        new[j + 1] = dp[j] - int(c == 'p')
        if j:
            new[j - 1] = dp[j] + int(c == 'g')
    dp = new

print(max(dp))


Fixed submission:
s = input()
print(len(s) // 2 - s.count('p'))