This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
from collections import defaultdict
import sys
n = int(input())
mp = [[] for _ in range(n)]
for _ in range(n - 1):
a, b = map(int, input().split())
mp[a-1].append(b-1)
mp[b-1].append(a-1)
a = list(map(int,input().split()))
for i in range(n):
a[i] = True if a[i] == 1 else False
can = False
for i in range(n):
q = []
q.append([i, a])
level = 0
while q:
l = len(q)
for _ in range(l):
top = q.pop(0)
if not any(top[1]):
can = True
print(level)
sys.exit()
cp = top[1][:]
cp[top[0]] = not cp[top[0]]
for nxt in mp[top[0]]:
cp[nxt] = not cp[nxt]
for j in range(n):
q.append([j, cp])
level += 1
if level >= 6:
break
if not can:
print("IMPOSSIBLE")
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |