Problem:


Score : 1100 points

Problem Statement

There is a tree with N vertices numbered 1, 2, ..., N.
The edges of the tree are denoted by (x_i, y_i).

On this tree, Alice and Bob play a game against each other.
Starting from Alice, they alternately perform the following operation:

Select an existing edge and remove it from the tree, disconnecting it into two separate connected components. Then, remove the component that does not contain Vertex 1.

A player loses the game when he/she is unable to perform the operation.
Determine the winner of the game assuming that both players play optimally.

Constraints

2 \leq N \leq 100000

1 \leq x_i, y_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_{N-1} y_{N-1}

Output

Print Alice if Alice wins; print Bob if Bob wins.

Sample Input 1

5
1 2
2 3
2 4
4 5

Sample Output 1

Alice

If Alice first removes the edge connecting Vertices 1 and 2, the tree becomes a single vertex tree containing only Vertex 1.
Since there is no edge anymore, Bob cannot perform the operation and Alice wins.

Sample Input 2

5
1 2
2 3
1 4
4 5

Sample Output 2

Bob

Sample Input 3

6
1 2
2 4
5 1
6 3
3 2

Sample Output 3

Alice

Sample Input 4

7
1 2
3 7
4 6
2 3
2 4
1 5

Sample Output 4

Bob



Sample input:
5
1 2
2 3
2 4
4 5


Sample output:
Alice

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.buffer.readline())
mp = map(int, sys.stdin.buffer.read().split())
links = [set() for _ in range(n)]
for x, y in zip(mp, mp):
    x -= 1
    y -= 1
    links[x].add(y)
    links[y].add(x)

stack = [(0, -2)]
grundy = [0] * n
while stack:
    v, p = stack.pop()
    if p == -1:
        g = 0
        # second visit (aggregate children and calculate self grundy)
        for u in links[v]:
            g ^= grundy[u] + 1
        grundy[v] = g
    else:
        # first visit (stack children and remove parent)
        links[v].discard(p)
        stack.append((v, -1))
        for u in links[v]:
            stack.append((u, v))

if grundy[0] == 0:
    print('Bob')
else:
    print('Alice')

Submission status: Accepted

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    N, A, B, C, D = LI()
    for i in range(N-1):
        low = A + i*C - (N-1-i)*D
        up = A + i*D - (N-1-i)*C
        if low<=B<=up:
            print("YES")
            return
    print("NO")
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        x, y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        V[y].append(x)
    def dfs(s,p):
        grundy = 0
        judge = len(V[s])
        if p==-1:
            judge += 1
        if judge==1:
            return grundy
        if judge==2:
            for v in V[s]:
                if v == p:
                    continue
                cur = dfs(v, s)
                grundy = cur+1
            return grundy
        for v in V[s]:
            if v==p:
                continue
            cur = dfs(v,s)+1
            #print(cur)
            grundy ^= cur

        return grundy
    ans = "Alice"
    if dfs(0,-1)==0:
        ans = "Bob"
    print(ans)
    return

def examE():
    N, H = LI()
    A = [LI()for _ in range(N)]


    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)


if __name__ == '__main__':
    examD()

"""

"""

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    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]
    root = 0  # 根
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq
    grundy = [0]*n

    dd = [j for i, j in sorted([(j, i) for i, j in enumerate(d)])[::-1]]

    for i in dd:
        dist = d[i]
        xorlist = []
        xor = 0
        for j in g[i]:
            if d[j] > dist:
                xorlist.append(grundy[j]+1)
        for j in xorlist:
            xor ^= j
        grundy[i] = xor

    if grundy[0]:
        print("Alice")
    else:
        print("Bob")


main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    q = [0]
    q2 = []
    g = [0]*n
    bfs = [1]*n
    bfs[0] = 0
    d = [0]*n
    while q:
        x = q.pop()
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                d[x] += 1
                q.append(y)
                q2.append((x,y))
    while q2:
        x,y = q2.pop()
        g[x] ^= g[y]+1
    ans = g[0]
    if ans:
        print("Alice")
    else:
        print("Bob")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0]*(n+1)
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
deg[1] += 1
dp = [[] for i in range(n+1)]
mark = [0]*(n+1)
stack = []
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
    mark[i] = 1
while stack:
  x = stack.pop()
  if dp[x]:
    t = 0
    for z in dp[x]:
      t ^= z
    mark[x] = t+1
  if x == 1:
    break
  for y in graph[x]:
    if deg[y] > 1:
      dp[y].append(mark[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
if mark[1] == 1:
  print("Bob")
else:
  print("Alice")

Submission status: Accepted

Solution code:
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)

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)

G = [0] * N
for i in R[::-1]:
    s = 0
    for j in X[i]:
        s ^= G[j]
    G[i] = s + 1

print("Bob" if G[0] == 1 else "Alice")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for x,y in XY:
    x,y = x-1,y-1
    es[x].append(y)
    es[y].append(x)

def grundy(v,p=-1):
    x = 0
    for to in es[v]:
        if to==p: continue
        x ^= (grundy(to,v) + 1)
    return x
print('Alice' if grundy(0) else 'Bob')

Submission status: Accepted

Solution code:
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())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)

nim = [-1 for i in range(N)]

def dfs(cur,par):
	val = 0
	for dst in g[cur]:
		if dst == par:
			continue
		val ^= dfs(dst,cur) + 1
	nim[cur] = val
	return val

dfs(0 , -1)
#print(nim)
if nim[0] == 0:
	print('Bob')
else:
	print('Alice')

Submission status: Accepted

Solution code:
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)

checked = [False]*N
def dfs(p):
    checked[p] = True
    g = 0
    for np in graph[p]:
        if not checked[np]:
            g ^= dfs(np)+1
    return g

if dfs(0) == 0:
    print("Bob")
else:
    print("Alice")

Submission status: Accepted

Solution code:
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
# MOD = 998244353


N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)


# @debug
def solve(v, parent=None):
    # 子供の grundy とったらいい
    xor = 0
    for u in graph[v]:
        if parent == u:
            continue
        xor ^= solve(u, parent=v) + 1
    return xor


ans = solve(0)
if ans == 0:
    print('Bob')
else:
    print('Alice')

Submission status: Accepted

Solution code:
from collections import deque
import heapq

N = int(input())

gr = [None] * N
child = [0] * N
dic = {}

q = []


for i in range(N-1):

    x,y = map(int,input().split())
    x -= 1
    y -= 1

    if x not in dic:
        dic[x] = []
    if y not in dic:
        dic[y] = []

    dic[x].append(y)
    dic[y].append(x)
    child[x] += 1
    child[y] += 1

dep = [float("inf")] * N
dep[0] = 0
dq = deque([0])
while len(dq) > 0:
    n = dq.popleft()

    for i in dic[n]:
        if dep[i] > dep[n] + 1:
            dep[i] = dep[n] + 1


for i in range(N):

    if child[i] == 1:
        child[i] = 0
        gr[i] = 0
        heapq.heappush(q,[-1 * dep[i] , i])

while len(q) > 0:

    ngr = 0
    no = heapq.heappop(q)
    now = no[1]

    for i in dic[now]:
        if gr[i] != None:
            ngr ^= (gr[i] + 1)
        else:
            child[i] -= 1

            if child[i] <= 1 and gr[i] == None:
                heapq.heappush(q,[-1 * dep[i] , i])

    gr[now] = ngr

#print (gr)

if gr[0] == 0:
    print ("Bob")
else:
    print ("Alice")

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.buffer.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)

seen = [0] * (N+1)
seen[1] = 1
seq = []
que = deque()
que.append(1)
child = [[] for _ in range(N+1)]
while que:
    v = que.pop()
    seq.append(v)
    for u in adj[v]:
        if seen[u] == 0:
            seen[u] = 1
            child[v].append(u)
            que.appendleft(u)

grundy = [0] * (N+1)
for v in reversed(seq):
    tmp = 0
    for u in child[v]:
        tmp ^= grundy[u] + 1
    grundy[v] = tmp

if grundy[1]:
    print('Alice')
else:
    print('Bob')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)
N = int(input())
E = [[] for _ in range(N+1)]
for _ in range(N-1):
    x, y = map(int, input().split())
    E[x].append(y)
    E[y].append(x)

def dfs(v, p):
    res = 0
    for u in E[v]:
        if u != p:
            res ^= dfs(u, v) + 1
    return res

print("Alice" if dfs(1, 0) else "Bob")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(readline())
XY = (tuple(int(x)-1 for x in line.split()) for line in readlines())

graph = [[] for _ in range(N)]
for x,y in XY:
    graph[x].append(y)
    graph[y].append(x)

visited = [True] + [False] * (N-1)
q = [0]
ord = [0]
par = [0] * N
while q:
    x = q.pop()
    for y in graph[x]:
        if visited[y]:
            continue
        ord.append(y)
        par[y] = x
        visited[y] = True
        q.append(y)

G = [0] * (N+1)
for x in ord[:0:-1]:
    p = par[x]
    G[p] ^= (G[x]+1)

answer = 'Alice' if G[0] != 0 else 'Bob'
print(answer)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(readline())
XY = [tuple(int(x) for x in line.split()) for line in readlines()]

graph = [[] for _ in range(N+1)]
for x,y in XY:
    graph[x].append(y)
    graph[y].append(x)

visited = [False] * (N+1)
visited[1] = True
q = [1]
ord = [1]
par = [0] * (N+1)
while q:
    x = q.pop()
    for y in graph[x]:
        if visited[y]:
            continue
        ord.append(y)
        par[y] = x
        visited[y] = True
        q.append(y)

G = [0] * (N+1)
for x in ord[::-1]:
    p = par[x]
    G[p] ^= (G[x]+1)

answer = 'Alice' if G[1] != 0 else 'Bob'
print(answer)

Submission status: Accepted

Solution code:
import sys
        
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

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

P = getpar(Edge, 0)
L = topological_sort_tree(Edge, 0)

dp = [0]*N
for l in L[1:][::-1]:
    p = P[l]
    dp[p] ^= (dp[l] + 1)


print('Alice' if dp[0] else 'Bob')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	x, y = map(int, input().split())
	adj[x-1].append(y-1)
	adj[y-1].append(x-1)

visited = [False for _ in range(n)]
def dfs(x):
	global visited
	nim = 0
	for v in adj[x]:
		if visited[v] == False:
			visited[v] = True
			nim ^= dfs(v)+1
	return nim

visited[0] = True
if dfs(0) == 0:
	print("Bob")
else:
	print("Alice")

Submission status: Accepted

Solution code:
import sys
n=input()
sys.setrecursionlimit(n+1000)
adj=[[] for i in range(n+1)]
for i in range(n-1):
	x, y=map(int, raw_input().split())
	adj[x].append(y)
	adj[y].append(x)
def dfs(cur, father):
	result=0
	for to in adj[cur]:
		if to!=father:
			result^=dfs(to, cur)+1
	return result
print "Alice" if dfs(1, -1) else "Bob"

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

N = input()
E = [[] for i in range(N)]

for i in range(N - 1):
    x, y = map(int, raw_input().split())
    x, y = x - 1, y - 1
    E[x].append(y)
    E[y].append(x)

def func(pos, pre):
    ret = 0
    for to in E[pos]:
        if to != pre:
            ret ^= func(to, pos)
    return ret + 1

if func(0, -1) != 1:
    print "Alice"
else:
    print "Bob"

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
def dfs(u, fa = -1):
	res = 0
	for v in adj[u]:
		if v != fa:
			res ^= dfs(v, u) + 1
	return res
n = int(raw_input())
adj = [[] for i in xrange(n)]
for i in xrange(n - 1):
	x, y = [int(t) - 1 for t in raw_input().split()]
	adj[x].append(y)
	adj[y].append(x)
print 'Alice' if dfs(0) else 'Bob'

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce

INF = float("inf")
sys.setrecursionlimit(10 ** 7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


def dfs(n, p, grundy, graph):
    g = 0
    for x in graph[n]:
        if x != p:
            g ^= dfs(x, n, grundy, graph) + 1
    grundy[n] = g
    return g


def solve(N, graph):
    grundy = [None] * (N + 1)
    dfs(1, 0, grundy, graph)
    return grundy[1] != 0


def main():
    N = int(input())
    graph = defaultdict(list)
    for _ in range(N - 1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    print("Alice" if solve(N, graph) else "Bob")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    e = collections.defaultdict(set)
    for i in range(n-1):
        a,b = LI()
        e[a].add(b)
        e[b].add(a)

    def f(i,c):
        r = 0
        for j in e[i]:
            if j == c:
                continue
            t = f(j,i)
            r ^= t
        return r + 1

    if f(1,-1) == 1:
        return 'Bob'
    return 'Alice'


print(main())

Submission status: Accepted

Solution code:
import sys
import random


sys.setrecursionlimit(10 ** 5 + 5)
random.seed = 1

# sys.stdin = open('d1.in')


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


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


a = None


def dfs(root, parent):
    res = 0
    for i in a[root]:
        if i != parent:
            res ^= 1 + dfs(i, root)
    return res


def read_tree(check=False):

    if check:
        n, p = gen()
    else:
        n = read_int()
        p = [read_int_list() for i in range(n - 1)]

    global a
    a = [[] for _ in range(n)]
    for x, y in p:
        x -= 1
        y -= 1
        a[x].append(y)
        a[y].append(x)


def gen():
    n = random.randint(5, 30)

    inside = [1]
    outside = list(range(2, n + 1))
    p = []
    for i in range(n - 1):
        x = random.choice(inside)
        y = random.choice(outside)
        p.append([x, y])
        outside.remove(y)
        inside.append(y)
    return n, p


def solve():
    read_tree(check=False)
    return ['Bob', 'Alice'][dfs(0, -1) > 0]


def check():
    for i in range(1000):
        res = solve()
        print(i, res)


def main():
    # check()
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n = int(stdin.readline())
    dat = map(int, stdin.read().split(), repeat(10, 2 * n - 2))
    la = [None] * (n + 1)
    xt = [None] * len(dat)
    j = 0
    for i in xrange(n - 1):
        x, y = dat[j], dat[j+1]
        xt[j] = la[y]
        la[y] = j
        j += 1
        xt[j] = la[x]
        la[x] = j
        j += 1
    g = [None] * (n + 1)
    st = [1]
    pu = st.append
    po = st.pop
    while st:
        x = po()
        if g[x] is None:
            g[x] = -1
            pu(x)
            y = la[x]
            while y is not None:
                if g[dat[y]] is None:
                    pu(dat[y])
                y = xt[y]
        else:
            f = 0
            y = la[x]
            while y is not None:
                if g[dat[y]] != -1:
                    f ^= g[dat[y]] + 1
                y = xt[y]
            g[x] = f
    print "Alice" if g[1] else "Bob"
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)


def main():

    def nim(i, parent=None):
        ret = 0
        for j in edges[i]:
            if j == parent:
                continue
            ret ^= nim(j, i) + 1
        return ret

    n = int(raw_input())
    edges = [[] for i in xrange(n)]
    for i in xrange(n - 1):
        x, y = [int(_) - 1 for _ in raw_input().split()]
        edges[x].append(y)
        edges[y].append(x)
    if nim(0) == 0:
        return "Bob"
    else:
        return "Alice"


if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

Solution code:
N = int(input())
adj = [[] for _ in range(N)]
for i in range(N - 1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    adj[x].append(y)
    adj[y].append(x)


def dfs(v, p):
    nim = 0
    for u in adj[v]:
        if u == p:
            continue
        nim ^= dfs(u, v)
    if p == -1:
        return nim
    nim += 1
    return nim

res = dfs(0, -1)

if res:
    print("Alice")
else:
    print("Bob")

Submission status: Runtime Error

Solution code:
N = int(input())
Edges = list([] for _ in range(N))
for n in range (N-1):
    x, y = map(int, input().split())
    Edges[x-1].append(y-1)
    Edges[y-1].append(x-1)

def dfs(cur_node, parent_node):
    grundy = 0
    for child_node in Edges[cur_node]:
        if child_node == parent_node:
            continue
        else:
            grundy ^= (dfs(child_node, cur_node) + 1)
    return grundy

G = dfs(0, -1)
if G == 0:
    print("Bob")
else:
    print("Alice")

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
sys.setrecursionlimit(n)
T=[[]for _ in"_"*(n+1)]
for _ in range(n-1):a,b=map(int,input().split());T[a]+=b,;T[b]+=a,
def d(v,p):
 r=0
 for s in T[v]:
  if s!=p:r^=d(s,v)+1
 return r
print("ABloibc e"[d(1,1)<1::2])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(k:=2*n)
n=int(input())
T=[[]for _ in"_"*k]
for _ in range(n-1):a,b=map(int,input().split());T[a]+=b,;T[b]+=a,
def d(v,p):
 r=0
 for s in T[v]:
  if s!=p:r^=d(s,v)+1
 return r
print("ABloibc e"[d(1,1)<1::2])

Submission status: Runtime Error

Solution code:
import sys

input=sys.stdin.readline

N=int(input())
edge=[[] for i in range(N)]
for i in range(N-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)

def grundy(v,pv):
    if v==0:
        if len(edge[v])==1:
            return grundy(edge[0][0],0)+1
        else:
            res=0
            for nv in edge[v]:
                if nv!=pv:
                    res^=grundy(nv,v)
            return res
    else:
        if len(edge[v])==1:
            return 0
        elif len(edge[v])==2:
            for nv in edge[v]:
                if nv!=pv:
                    return grundy(nv,v)+1
        else:
            res=0
            for nv in edge[v]:
                if nv!=pv:
                    res^=grundy(nv,v)
            return res


ans=grundy(0,-1)
if ans!=0:
    print("Alice")
else:
    print("Bob")

Submission status: Runtime Error

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    N, A, B, C, D = LI()
    for i in range(N-1):
        low = A + i*C - (N-1-i)*D
        up = A + i*D - (N-1-i)*C
        if low<=B<=up:
            print("YES")
            return
    print("NO")
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        x, y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        V[y].append(x)
    def dfs(s,p):
        grundy = 0
        judge = len(V[s])
        if p==-1:
            judge += 1
        if judge==1:
            return grundy
        if judge==2:
            for v in V[s]:
                if v == p:
                    continue
                cur = dfs(v, s)
                grundy = cur+1
            return grundy
        for v in V[s]:
            if v==p:
                continue
            cur = dfs(v,s)
            grundy ^= cur

        return grundy
    ans = "Alice"
    if dfs(0,-1)==0:
        ans = "Bob"
    print(ans)
    return

def examE():
    N, H = LI()
    A = [LI()for _ in range(N)]


    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Runtime Error

Solution code:
N=int(input())
g = [[] for i in range(N)]
for i in range(N-1):
	a,b=map(int,input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)

nim = [-1 for i in range(N)]

def dfs(cur,par):
	val = 0
	for dst in g[cur]:
		if dst == par:
			continue
		val ^= dfs(dst,cur) + 1
	nim[cur] = val
	return val

dfs(0 , -1)
#print(nim)
if nim[0] == 0:
	print('Bob')
else:
	print('Alice')

Submission status: Runtime Error

Solution code:
N=int(input())
g = [[] for i in range(N)]
for i in range(N-1):
	a,b=map(int,input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)

nim = [-1 for i in range(N)]

def dfs(cur,par):
	val = 0
	for dst in g[cur]:
		if dst == par:
			continue
		val ^= dfs(dst,cur) + 1
	nim[cur] = val
	return val

dfs(0 , -1)
print(nim)
if nim[0] == 0:
	print('Bob')
else:
	print('Alice')

Submission status: Runtime Error

Solution code:
def dfs(u, fa = 0):
	global adj
	res = 0
	for v in adj[u]:
		if v != fa:
			res ^= dfs(v, u) + 1
	return res

n = int(raw_input())
adj = [[] for i in range(n + 1)]
for i in range(n - 1):
	x, y = map(int, raw_input().split())
	adj[x].append(y)
	adj[y].append(x)
print 'Alice' if dfs(1) else 'Bob'

Submission status: Runtime Error

Solution code:
import sys
import random

random.seed = 1

# sys.stdin = open('d1.in')


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


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


a = None


def dfs(root, parent):
    res = 0
    for i in a[root]:
        if i != parent:
            res ^= 1 + dfs(i, root)
    return res


def read_tree(check=False):

    if check:
        n, p = gen()
    else:
        n = read_int()
        p = [read_int_list() for i in range(n - 1)]

    global a
    a = [[] for _ in range(n)]
    for x, y in p:
        x -= 1
        y -= 1
        a[x].append(y)
        a[y].append(x)


def gen():
    n = random.randint(5, 30)

    inside = [1]
    outside = list(range(2, n + 1))
    p = []
    for i in range(n - 1):
        x = random.choice(inside)
        y = random.choice(outside)
        p.append([x, y])
        outside.remove(y)
        inside.append(y)
    return n, p


def solve():
    read_tree(check=False)
    return ['Bob', 'Alice'][dfs(0, -1) > 0]


def check():
    for i in range(1000):
        res = solve()
        print(i, res)


def main():
    # check()
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

# sys.stdin = open('d1.in')


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


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


a = None


def dfs(root, parent):
    res = 0
    for i in a[root]:
        if i != parent:
            res ^= 1 + dfs(i, root)
    return res


def solve():
    n = read_int()
    global a
    a = [[] for _ in range(n)]
    for i in range(n - 1):
        x, y = read_int_list()
        x -= 1
        y -= 1
        a[x].append(y)
        a[y].append(x)
    return ['Bob', 'Alice'][dfs(0, -1) > 0]


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter
from collections import defaultdict
N = int(input())

XY = [list(map(int,input().split())) for _ in range(N-1)]

node_count = list(zip(*XY))[0]+list(zip(*XY))[1]
counter= Counter(node_count)
d = defaultdict(list)
for x,y in XY:
    d[x].append(y)
    d[y].append(x)


def is_taisho(last,node):
    nodes = list(set(d[node]) - set([last]))
    #print(last,node,d[node],nodes)
    if not nodes:
        return 1
    if len(nodes)%2 and len(nodes)>=3:
        print("Alice")
        exit(0)
    if not any(v%2 for v in Counter(is_taisho(node,new_node) for new_node in nodes).values()):
        return is_taisho(node,nodes[0])+1
    else:
        print("Alice")
        exit(0)

(is_taisho(0,1))
print("Bob")




def check(node,last):
    if last !=0:
        pass

def check():
    print(counter)
    if counter[1]%2!=0:
        return True
    for i in range(2,N+1):
        if counter[i]%2!=1:
            return True
    return False

Submission status: Runtime Error

Solution code:
from collections import Counter
from collections import defaultdict
N = int(input())

XY = [list(map(int,input().split())) for _ in range(N-1)]

node_count = list(zip(*XY))[0]+list(zip(*XY))[1]
counter= Counter(node_count)
d = defaultdict(list)
for x,y in XY:
    d[x].append(y)
    d[y].append(x)


def is_taisho(last,node):
    nodes = list(set(d[node]) - set([last]))
    #print(last,node,d[node],nodes)
    if not nodes:
        return 1
    if len(nodes)%2 and len(nodes)>=3:
        print("Alice")
        exit(0)
    if all(is_taisho(node,new_node) for new_node in nodes):
        return is_taisho(node,nodes[0])+1
    else:
        print("Alice")
        exit(0)

(is_taisho(0,1))
print("Bob")

def check(node,last):
    if last !=0:
        pass

def check():
    print(counter)
    if counter[1]%2!=0:
        return True
    for i in range(2,N+1):
        if counter[i]%2!=1:
            return True
    return False