Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02582 (python)

Fixed submission:
A = list(input())

n = A.count('R')
if n != 2:
    print(n)
else:
    m = A.index('S')
    if m == 1:
        print(1)
    else:
        print(2)

Buggy submission (verdict: Runtime Error):
N = int(input())
L = list(int, input())
count = 0

for i in range(N-2):
    Li = L[i]
    for j in range(i+1, N-1):
        Lj = L[j]
        for k in range(j+1, N):
            Lk = L[k]
            if (Li == Lj) or (Lj == Lk) or (Lk == Li):
                continue
            else:
                if ((Li + Lj) >= Lk) and ((Li + Lk) >= Lj) and ((Lk + Lj) >= Li):
                    count = count + 1
print(count)

Buggy submission (verdict: Runtime Error):
N = int(input())
L = list(int, input().split())
count = 0

for i in range(N-2):
    Li = L[i]
    for j in range(i+1, N-1):
        Lj = L[j]
        for k in range(j+1, N):
            Lk = L[k]
            if (Li == Lj) or (Lj == Lk) or (Lk == Li):
                continue
            else:
                if ((Li + Lj) >= Lk) and ((Li + Lk) >= Lj) and ((Lk + Lj) >= Li):
                    count = count + 1
print(count)

Buggy submission (verdict: Runtime Error):
N = int(input())
L = list(input().split())
count = 0

for i in range(N-2):
    Li = L[i]
    for j in range(i+1, N-1):
        Lj = L[j]
        for k in range(j+1, N):
            Lk = L[k]
            if (Li == Lj) or (Lj == Lk) or (Lk == Li):
                continue
            else:
                if ((Li + Lj) >= Lk) and ((Li + Lk) >= Lj) and ((Lk + Lj) >= Li):
                    count = count + 1
print(count)

Buggy submission (verdict: Runtime Error):
a,b,c = input().split()

if a == R:
    if b == R:
        if c == R:
            print(3)
        else:
            print(2)
    else:
        print(1)
else:
    if b == R:
        if c == R:
            print(2)
        else:
            print(1)
    else:
        if c == R:
            print(1)
        else:
            print(0)

Buggy submission (verdict: Runtime Error):
a, b, c = input()

if a == R:
    if b == R:
        if c == R:
            print(3)
        else:
            print(2)
    else:
        print(1)
else:
    if b == R:
        if c == R:
            print(2)
        else:
            print(1)
    else:
        if c == R:
            print(1)
        else:
            print(0)

Buggy submission (verdict: Runtime Error):
a, b, c = input().split()

if a == R:
    if b == R:
        if c == R:
            print(3)
        else:
            print(2)
    else:
        print(1)
else:
    if b == R:
        if c == R:
            print(2)
        else:
            print(1)
    else:
        if c == R:
            print(1)
        else:
            print(0)

Buggy submission (verdict: Runtime Error):
a,b,c = map(input().split())

if a == R:
    if b == R:
        if c == R:
            print(3)
        else:
            print(2)
    else:
        print(1)
else:
    if b == R:
        if c == R:
            print(2)
        else:
            print(1)
    else:
        if c == R:
            print(1)
        else:
            print(0)
Problem p02583 (python)

Fixed submission:
N =int(input())
L=list(map(int, input().split()))
LL = sorted(L)
count=0
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if LL[i]+LL[j]>LL[k]:
                if (LL[i]!=LL[j])and(LL[j]!=LL[k]):
                    count += 1
print(count)

Buggy submission (verdict: Runtime Error):
N = input()
L = list(input())
count = 0

for i in range(N-2):
    Li = L[i]
    for j in range(i+1, N-1):
        Lj = L[j]
        for k in range(j+1, N):
            Lk = L[k]
            if (Li == Lj) or (Lj == Lk) or (Lk == Li):
                continue
            else:
                if ((Li + Lj) >= Lk) and ((Li + Lk) >= Lj) and ((Lk + Lj) >= Li):
                    count = count + 1
print(count)
Problem p03434 (python)

Fixed submission:
# 088 B
N = int(input())
a = list(map(int, input().split()))
A = 0
B = 0
aa = sorted(a)
for i in range(0, N, 2):
    A += aa[-i-1]
    if (i+2)<=N:
        B += aa[-i-2]
print(A-B)

Buggy submission (verdict: Runtime Error):
# 088 B
N = int(input())
a = list(map(int, input().split()))
A = 0
B = 0
aa = sorted(a)
for i in range(0, N, 2):
    A += aa[-i-1]
    B += aa[-i-2]
print(A-B)
Problem p03471 (python)

Fixed submission:
# 085 C
N,Y = map(int, input().split())
x,y,z = -1,-1,-1
for i in range(N+1):
    for j in range(N+1):
        if ((10000*i + 5000*j + 1000*(N-i-j)) == Y)and(N-i-j>=0):
            x,y = i,j
            z = N - i - j
            break
    else:
        continue
    break
print(x,y,z)

Buggy submission (verdict: Runtime Error):
# 085 C
N,Y = map(int, input().split())
for x in range(N):
    for y in range(N):
        for z inrange(N):
            if ((10000*x + 5000*y + 1000*z) == Y) and ((x + y + z) == N):
                print(x' 'y' 'z' ')
                exit()
print('-1 -1 -1')
Problem p02573 (python)

Fixed submission:
N,M=map(int, input().split())

class UnionFind():
    def __init__(self, n):
        self.n = n # ノード数
        self.parents = [-1]*n # 各ノードごとのparent

    def find(self, x):
        # 自身が根であれば
        if self.parents[x]<0:
            return x
        # そうでなければ、再帰的に繰り返し、自身の根を探索
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        # それぞれの根
        x = self.find(x)
        y = self.find(y)

        # 根が同一であれば
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x,y = y,x
        self.parents[x]+=self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(N)
for _ in range(M):
    i, j = map(int, input().split())
    i-=1
    j-=1
    uf.union(i,j)

max_size = 0
for i in range(N):
    if uf.parents[i]<0:
        size = uf.size(i)
        if max_size<size:
            max_size = size
print(max_size)

Buggy submission (verdict: Runtime Error):
N,M=map(int, input().split())

groups = [1e10 for i in range(N)]
new_group = 0
for _ in range(M):
    i, j = map(int, input().split())
    i-=1
    j-=1
    if groups[i]==1e10 and groups[j]==1e10:
        groups[i] = new_group
        groups[j] = new_group
        new_group+=1
    elif groups[i]==1e10:
        group = groups[j]
        groups[i]=group
    else:
        group = groups[i]
        groups[j]=group

group_nums = [0 for _ in range(new_group)]
for g in groups:
    if g!=1e10:
        group_nums[g]+=1
print(max(group_nums))
Problem p02658 (python)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
 
tmp = 1
for num in A:
    tmp *= num
    if tmp > 1e18:
      break
  
if tmp <= 1e18:
    print(tmp)
elif 0 in A:
    print(0)
else:
    print(-1)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
 
tmp = 1
for num in A:
    tmp *= num
    if tmp > 1e18:
      break
  
if tmp <= 1e18:
    print(tmp)
elif 0 in tmp:
    print(0)
else:
    print(-1)
Problem p02683 (python)

Fixed submission:
import numpy as np

N,M,X = map(int, input().split())

values = []
scores = []
for _ in range(N):
    tmp = list(map(int, input().split()))
    values.append(tmp[0])
    scores.append(tmp[1:])
scores = np.array(scores)
values = np.array(values)

def df(arg, score, tmp,args):
    tmps = []
    if arg==N:
        if len(np.where(score>=X)[0]) == M:
            return tmp
        else:
            return 0
    check = df(arg+1, score, tmp, args)
    if check:
        if type(check)==list:
            tmps.extend(check)
        else:
            tmps.append(check)
    check = df(arg+1, score+scores[arg], tmp+values[arg], args+[arg])
    if check:
        if type(check)==list:
            tmps.extend(check)
        else:
            tmps.append(check)
    if tmps == []:
        return 0
    else:
        return tmps

tmp = df(0, np.zeros(M), 0, [])
if tmp != 0:
    print(min(tmp))
else:
    print(-1)

Buggy submission (verdict: Runtime Error):
import numpy as np

N,M,X = map(int, input().split())

values = []
scores = []
for _ in range(N):
    tmp = list(map(int, input().split()))
    values.append(tmp[0])
    scores.append(tmp[1:])
scores = np.array(scores)
values = np.array(values)

def df(arg, score, tmp,args):
    tmps = []
    if arg==N:
        if len(np.where(score>=X)[0]) == M:
            return tmp
        else:
            return 0
    check = df(arg+1, score, tmp, args)
    if check:
        if type(check)==list:
            tmps.extend(check)
        else:
            tmps.append(check)
    check = df(arg+1, score+scores[arg], tmp+values[arg], args+[arg])
    if check:
        if type(check)==list:
            tmps.extend(check)
        else:
            tmps.append(check)
    if tmps == []:
        return 0
    else:
        return tmps

tmp = df(0, np.zeros(M), 0, [])
if tmp != []:
    print(min(tmp))
else:
    print(-1)

Buggy submission (verdict: Runtime Error):
import numpy as np

N,M,X = map(int, input().split())

values = []
scores = []
greedy = []
for _ in range(N):
    tmp = list(map(int, input().split()))
    values.append(tmp[0])
    scores.append(tmp[1:])
    greedy.append(np.sum(scores)/tmp[0])

values = np.array(values)
scores = np.array(scores)

selected = []
finished = []
finisheds = np.zeros(M)
ans = 0
while len(finished) != M and np.sum(greedy)!=0:
    arg = np.argmax(greedy)
    selected.append(arg)
    finisheds += scores[arg]
    ans += values[arg]
    scores[selected] = 0
    args = np.where(finisheds>=X)[0]
    finished.extend(list(args))
    finished = list(set(finished))
    for arg in args:
        scores[:, arg] = 0
    greedy = np.sum(scores, axis=1)/values
    for arg in finished:
        greedy[arg] = 0

if len(finished) == M:
    print(ans)
else:
    print(-1)
Problem p02687 (python)

Fixed submission:
string = input()

if string=="ABC":
    print("ARC")
elif string=="ARC":
    print("ABC")

Buggy submission (verdict: Runtime Error):
string = int(input())

if string=="ABC":
    print("ARC")
elif string=="ARC":
    print("ABC")
Problem p02936 (python)

Fixed submission:
import sys
sys.setrecursionlimit(2*10**9)

N,Q=map(int, input().split())

adj_list = [[] for _ in range(N)]
counter = [0 for _ in range(N)]
reached = [0 for _ in range(N)]

for _ in range(N-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    adj_list[a].append(b)
    adj_list[b].append(a)

def df(current, score):
    next_nodes = adj_list[current]
    reached[current]=1
    for node in next_nodes:
        if reached[node]==0:
            counter[node]+=score
            df(node, counter[node])

for _ in range(Q):
    p,x=map(int, input().split())
    counter[p-1]+=x
df(0, counter[0])
print(*counter)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2*10**5)

N,Q=map(int, input().split())

adj_list = [[] for _ in range(N)]
counter = [0 for _ in range(N)]
reached = [0 for _ in range(N)]

for _ in range(N-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    adj_list[a].append(b)
    adj_list[b].append(a)

def df(current, score):
    next_nodes = adj_list[current]
    reached[current]=1
    for node in next_nodes:
        if reached[node]==0:
            counter[node]+=score
            df(node, counter[node])

for _ in range(Q):
    p,x=map(int, input().split())
    counter[p-1]+=x
df(0, counter[0])
print(*counter)

Buggy submission (verdict: Runtime Error):
N,Q=map(int, input().split())

adj_list = [[] for _ in range(N)]
counter = [0 for _ in range(N)]
reached = [0 for _ in range(N)]

for _ in range(N-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    adj_list[a].append(b)
    adj_list[b].append(a)

def df(current, score):
    next_nodes = adj_list[current]
    reached[current]=1
    for node in next_nodes:
        if reached[node]==0:
            counter[node]+=score
            df(node, counter[node])

for _ in range(Q):
    p,x=map(int, input().split())
    counter[p-1]+=x
df(0, counter[0])
print(*counter)

Buggy submission (verdict: Runtime Error):
N,Q=map(int, input().split())

adj_list = [[] for _ in range(N)]
counter = [0 for _ in range(N)]

for _ in range(N-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    adj_list[a].append(b)
    adj_list[b].append(a)

def df(current, score, residual):
    counter[current]+=score
    residual = list(set(residual)-set([current]))

    next_nodes = adj_list[current]
    next_nodes = [node for node in next_nodes
            if node in residual]
    for node in next_nodes:
        df(node, score, residual)

for _ in range(Q):
    p,x=map(int, input().split())
    residual = list(set(range(N))-set(range(0,p-1)))
    df(p-1,x,residual)

result = ""
for i in range(N):
    result+="%d"%(counter[i])
    if i!=N-1:
        result+=" "
print(result)
Problem p02705 (python)

Fixed submission:
# coding: utf-8
import math


def solve(*args: str) -> str:
    r = int(args[0])

    return str(2*math.pi*r)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import math


def solve(*args: str) -> str:
    r = int(args[0])

    return str(2*math.pi()*r)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import math


def solve(*args: str) -> str:
    r = int(args[0])

    return str(2*math.pi()*r)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Problem p02733 (python)

Fixed submission:
import numpy as np


def solve(*args: str) -> str:
    h, w, k = map(int, args[0].split())
    white = np.array([[n for n in map(int, S)] for S in args[1:]])

    ret = h*w
    for b in range(2**(h-1)):
        h_cuts = list(i+1 for i in range(h-1) if (b >> i) & 1 == 1)
        count = len(h_cuts)
        if ret < count:
            continue

        A = np.array(list(x.sum(axis=0) for x in np.vsplit(white, h_cuts)))
        if (k < A).any():
            continue

        S = np.zeros((1, len(A)), dtype=int)
        for x in range(w):
            S += A[:, x]
            if (k < S).any():
                S = A[:, x]
                count += 1
                if ret < count:
                    break

        ret = min(ret, count)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Buggy submission (verdict: Runtime Error):
import numpy as np


def solve(*args: str) -> str:
    h, w, k = map(int, args[0].split())
    white = np.array([[n for n in map(int, S)] for S in args[1:]])

    ret = h*w
    for b in range(2**(h-1)):
        h_cuts = set(i+1 for i in range(h-1) if (b >> i) & 1 == 1)
        count = len(h_cuts)
        if ret < count:
            continue

        A = np.array(tuple(x.sum(axis=0) for x in np.vsplit(white, h_cuts)))
        if (k < A).any():
            continue

        S = np.zeros((1, len(A)), dtype=int)
        for x in range(w):
            S += A[:, x]
            if (k < S).any():
                S = A[:, x]
                count += 1
                if ret < count:
                    break

        ret = min(ret, count)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Buggy submission (verdict: Runtime Error):
import numpy as np


def solve(*args: str) -> str:
    h, w, k = map(int, args[0].split())
    white = np.array([[n for n in map(int, S)] for S in args[1:]])

    ret = h*w
    for b in range(2**(h-1)):
        h_cuts = set(i+1 for i in range(h-1) if (b >> i) & 1 == 1)
        count = len(h_cuts)
        if ret < count:
            continue

        A = np.array(tuple(x.sum(axis=0) for x in np.vsplit(white, h_cuts)))
        if k < np.max(A):
            continue

        S = np.zeros((1, len(A)), dtype=int)
        for x in range(w):
            S += A[:, x]
            if (k < S).any():
                S = A[:, x]
                count += 1
                if ret < count:
                    break

        ret = min(ret, count)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Problem p02866 (python)

Fixed submission:
# coding: utf-8


def solve(*args: str) -> str:
    _ = int(args[0])
    D = list(map(int, args[1].split()))

    max_d = max(D)

    nodes = [0]*(max_d+1)
    for d in D:
        nodes[d] += 1

    ret = 0
    if D[0] == 0 and nodes.count(0) == 0 and nodes[0] == 1:
        ret = 1
        for i in range(2, max_d+1):
            ret *= pow(nodes[i-1], nodes[i], 998244353)

    return str(ret % 998244353)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import math


def solve(*args: str) -> str:
    _ = int(args[0])
    D = sorted(list(map(int, args[1].split())))

    max_d = D[-1]

    nodes = [0]*(max_d+1)
    for d in D:
        nodes[d] += 1

    ret = 1
    for i in range(max_d+1):
        if i < 2:
            ret *= 1 if 0 < nodes[i] else 0
        else:
            h = math.factorial(nodes[i-1] + nodes[i]-1)
            h //= math.factorial(nodes[i])
            ret *= h

    return str(ret % 998244353)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
Problem p02874 (python)

Fixed submission:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    LR = [tuple(map(int, a.split())) for a in args[1:]]
    L, R = zip(*LR)

    ret = 0

    p, q = np.argmax(L), np.argmin(R)
    lp, rq = L[p], R[q]

    ret = max(0, 1+rq-lp) + max(0, max(1+r-l for l, r in LR))

    AB = [[max(0, 1+r-lp), max(0, 1+rq-l)] for l, r in LR]
    AB.sort(key=lambda x: (x[0], -x[1]))
    A, B = map(list, zip(*AB))

    # for i in range(1, n):
    #     ret = max(ret, min(A[i:]) + min(B[:i]))
    b_min = 1+10**9
    for i in range(n-1):
        b_min = min(b_min, B[i])
        ret = max(ret, b_min + A[i+1])

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Buggy submission (verdict: Runtime Error):
# coding: utf-8
from functools import lru_cache
import sys


def solve(*args: str) -> str:
    n = int(args[0])
    LR = []
    for a in args[1:]:
        LR.append(tuple(map(int, a.split())))

    dp = DP(LR)

    sys.setrecursionlimit(10**5)
    return str(dp.search_max(0, 0, 10**9, 0, 10**9))


class DP:
    def __init__(self, LR: list):
        self.LR = LR

    @lru_cache(maxsize=None)
    def search_max(self, index: int, l1: int, r1: int, l2: int, r2: int)\
            -> int:
        ret = 0

        if index < len(self.LR):
            l, r = self.LR[index]
            ret = max(
                self.search_max(index+1, max(l, l1), min(r, r1), l2, r2),
                self.search_max(index+1, l1, r1, max(l, l2), min(r, r2))
            )
        else:
            if l1 == 0 or l2 == 0:
                ret = 0
            else:
                ret = max(0, (r1-l1)) + max(0, (r2-l2) + 2)

        return ret


if __name__ == "__main__":
    n = input()
    print(solve(*([n]+[input() for _ in range(int(n))])))

Buggy submission (verdict: Runtime Error):
# coding: utf-8
from functools import lru_cache


def solve(*args: str) -> str:
    n = int(args[0])
    LR = []
    for a in args[1:]:
        LR.append(tuple(map(int, a.split())))

    dp = DP(LR)

    return str(dp.search_max(0, 0, 10**9, 0, 10**9))


class DP:
    def __init__(self, LR: list):
        self.LR = LR

    @lru_cache(maxsize=None)
    def search_max(self, index: int, l1: int, r1: int, l2: int, r2: int)\
            -> int:
        ret = 0

        if index < len(self.LR):
            l, r = self.LR[index]
            ret = max(
                self.search_max(index+1, max(l, l1), min(r, r1), l2, r2),
                self.search_max(index+1, l1, r1, max(l, l2), min(r, r2))
            )
        else:
            if l1 == 0 or l2 == 0:
                ret = 0
            else:
                ret = max(0, (r1-l1)) + max(0, (r2-l2) + 2)
        # print((l1, r1, l2, r2))
        return ret


if __name__ == "__main__":
    n = input()
    print(solve(*([n]+[input() for _ in range(int(n))])))
Problem p02909 (python)

Fixed submission:
# coding: utf-8


def solve(*args: str) -> str:
    s = args[0]
    r = ''
    if(s == 'Sunny'):
        r = 'Cloudy'
    elif(s == 'Cloudy'):
        r = 'Rainy'
    elif(s == 'Rainy'):
        r = 'Sunny'

    return str(r)


if __name__ == "__main__":
    print(solve(*[input() for _ in range(1)]))

Buggy submission (verdict: Runtime Error):
# coding: utf-8


def solve(*args: str) -> str:
    n, k, q = map(int, args[0].split())
    A = list(map(int, args[1:]))
    ret = ''
    p = 0
    for a in sorted(set(A)):
        ret += ('Yes\n' if 0 < k-q else 'No\n')*(a-p-1)
        ret += ('Yes' if 0 < k - (q - A.count(a)) else 'No') + '\n'
        p = a

    ret += ('Yes\n' if 0 < k-q else 'No\n')*(n-p)
    return ret.rstrip('\n')


if __name__ == "__main__":
    nkq = input()
    _, _, q = map(int, nkq.split())
    print(solve(*([nkq]+[input() for _ in range(q)])))
Problem p03603 (python)

Fixed submission:
# coding: utf-8
from collections import defaultdict, deque

import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    P = list(map(int, args[1].split()))
    X = list(map(int, args[2].split()))

    T = defaultdict(set)
    for i, p in enumerate(P):
        T[p-1].add(i+1)

    stack = []
    Q = deque()
    Q.append(0)
    while Q:
        i = Q.popleft()
        stack.append(i)
        for c in T[i]:
            Q.append(c)

    ret = 'POSSIBLE'
    inf = 2**32-1
    Y = [0]*n
    for i in stack[::-1]:
        prev = np.full(X[i]+1, inf, np.int64)
        prev[0] = 0
        x_acc, y_acc = 0, 0
        for c in T[i]:
            cur = np.full(X[i]+1, inf, np.int64)
            x, y = X[c], Y[c]
            x_acc += x
            y_acc += y
            cur[x:] = np.minimum(cur[x:], y+prev[:-x if 0 < x else len(prev)])
            cur[y:] = np.minimum(cur[y:], x+prev[:-y if 0 < y else len(prev)])
            prev = np.copy(cur)

        y = np.min(prev)
        if y < inf:
            Y[i] = y
        else:
            ret = 'IMPOSSIBLE'
            break

    return ret


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Buggy submission (verdict: Runtime Error):
# coding: utf-8
from collections import defaultdict, deque

import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    P = list(map(int, args[1].split()))
    X = list(map(int, args[2].split()))

    T = defaultdict(set)
    for i, p in enumerate(P):
        T[p-1].add(i+1)

    stack = []
    Q = deque()
    Q.append(0)
    while Q:
        i = Q.popleft()
        stack.append(i)
        for c in T[i]:
            Q.append(c)

    ret = 'POSSIBLE'
    inf = 2**32-1
    Y = [0]*n
    for i in stack[::-1]:
        dp = np.full(X[i]+1, inf, np.int64)
        dp[0] = 0
        x_acc, y_acc = 0, 0
        for c in T[i]:
            x, y = X[c], Y[c]
            x_acc += x
            y_acc += y
            dp = np.minimum(
                np.concatenate((dp[:x], dp[:-x]+y)),
                np.concatenate((dp[:y], dp[:-y if 0 < y else len(dp)]+x))
            )

        A = np.sort(dp[1:])
        if len(T[i]) == 0:
            Y[i] = 0
        elif A[0] < inf:
            Y[i] = A[0]
        elif y_acc != 0:
            ret = 'IMPOSSIBLE'
            break
        else:
            Y[i] = x_acc

    return ret


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))