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

Solution (Python):
class Tree():
    def __init__(self, n, decrement=1):
        self.n = n
        self.edges = [[] for _ in range(n)]
        self.root = None
        self.depth = [-1]*n
        self.size = [1]*n       
        self.decrement = decrement

    def add_edge(self, u, v):
        u, v = u-self.decrement, v-self.decrement
        self.edges[u].append(v)
        self.edges[v].append(u)

    def add_edges(self, edges):
        for u, v in edges:
            u, v = u-self.decrement, v-self.decrement
            self.edges[u].append(v)
            self.edges[v].append(u)

    def set_root(self, root):
        root -= self.decrement
        self.root = root
        self.par = [-1]*self.n
        self.depth[root] = 0
        self.order = [root]     
        next_set = [root]
        while next_set:
            p = next_set.pop()
            for q in self.edges[p]:
                if self.depth[q] != -1: continue
                self.par[q] = p
                self.depth[q] = self.depth[p]+1
                self.order.append(q)
                next_set.append(q)
        for p in self.order[::-1]:
            for q in self.edges[p]:
                if self.par[p] == q: continue
                self.size[p] += self.size[q]



import sys
input = sys.stdin.readline

N = int(input())
T = Tree(N, decrement=1)
for _ in range(N-1):
    x, y = map(int, input().split())
    T.add_edge(x, y)
T.set_root(1)

grundy = [0]*N
for p in T.order[::-1]:
    for q in T.edges[p]:
        if T.par[p]==q: continue
        grundy[p]^=grundy[q]+1

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
edges = [[] for i in range(n)]
for i in range(n - 1):
    x, y = map(int, input().split())
    edges[x - 1].append(y - 1)
    edges[y - 1].append(x - 1)
def grundy_dfs(cur, prev):
    res = 0
    for next_ in edges[cur]:
        if next_ == prev:
            continue
        res ^= grundy_dfs(next_, cur) + 1
    return res
if grundy_dfs(0, -1) > 0:
    print("Alice")
else:
    print("Bob")

Solution (Python):
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.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.order.append(adj)
                    stack.append(adj)

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

tree = Tree(N, edge)
tree.setroot(0)

grundy = [0 for _ in range(N)]

for node in tree.order[::-1]:
    for adj in tree.tree[node]:
        if tree.parent[node] == adj:
            continue
        grundy[node] ^= grundy[adj] + 1

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

nim = [0] * N

def dfs(v, p):
    for c in G[v]:
        if c != p:
            dfs(c, v)
            nim[v] ^= nim[c]
    nim[v] += 1

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

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



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

Solution (Python):
import sys
sys.setrecursionlimit(pow(10,6))

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:
            grundy ^= (dfs(child_node, cur_node) + 1)
    return grundy

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

Solution (Python):
import sys
sys.setrecursionlimit(pow(10,6))

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

Solution (Python):
def topological_sort(tree: list, root) -> list:
    """根付き木をトポロジカルソートする"""
    n = len(tree)
    visited = [False] * n
    visited[root] = True
    tp_sorted = [root]
    stack = [root]
    while stack:
        v = stack.pop()
        for nxt_v in tree[v]:
            if visited[nxt_v]:
                continue
            visited[nxt_v] = True
            stack.append(nxt_v)
            tp_sorted.append(nxt_v)
    return tp_sorted


def get_par(tree: list, root: int) -> list:
    """根付き木の頂点それぞれの親を求める"""
    n = len(tree)
    visited = [False] * n
    visited[root] = True
    par = [-1] * n
    stack = [root]
    while stack:
        v = stack.pop()
        for nxt_v in tree[v]:
            if visited[nxt_v]:
                continue
            visited[nxt_v] = True
            stack.append(nxt_v)
            par[nxt_v] = v
    return par


n = int(input())
edges = [list(map(int, input().split())) for i in range(n - 1)]


tree = [[] for i in range(n)]
root = 0
for a, b in edges:
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

tp_sorted = topological_sort(tree, root)
par = get_par(tree, root)
grandy = [0] * n

for v in tp_sorted[::-1]:
    par_v = par[v]
    if par_v == -1:
        continue
    grandy[par_v] ^= grandy[v] + 1

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

Solution (Python):
import sys
n=int(input())
sys.setrecursionlimit(k:=2*n)
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])

Solution (Python):
import sys
n=int(input())
sys.setrecursionlimit(k:=2*n)
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])

Solution (Python):
import sys
sys.setrecursionlimit(9**9)
n=int(input())
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])

Solution (Python):
def examA():
    N = I()
    A = LI()
    D = defaultdict(int)
    for a in A:
        D[a] += 1
    ans = 0
    for key,d in D.items():
        if key>d:
            ans += d
        else:
            ans += d - key
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    S = [0]*(N+1)
    for i in range(N):
        S[i+1] = S[i]+A[i]
    D = defaultdict(int)
    for s in S:
        D[s] += 1
    ans = 0
    for d in D.values():
        ans += d*(d-1)//2
    print(ans)
    return

def examC():
    N, A, B, C = LI()
    L = [I()for _ in range(N)]
    loop = (1<<(2*N))
    ans = inf
    for l in range(loop):
        cost = 0
        bamboo_A = 0
        bamboo_B = 0
        bamboo_C = 0
        for j in range(N):
            if l&(1<<(2*j))>0:
                if l&(1<<(2*j+1))>0:
                    cost += 10
                    bamboo_A += L[j]
                else:
                    cost += 10
                    bamboo_B += L[j]
            else:
                if l&(1<<(2*j+1))>0:
                    cost += 10
                    bamboo_C += L[j]
        if bamboo_A==0 or bamboo_B==0 or bamboo_C==0:
            continue
        cost += abs(A-bamboo_A) + abs(B-bamboo_B) + abs(C-bamboo_C) - 30
        ans = min(ans,cost)

    print(ans)
    return

def examD():
    N = I()
    P = LI()
    O_ = [-1]*N
    start = P[0]-1
    for i in range(N):
        O_[P[i]-1] = i
    
    A = [1]*N
    B = [1]*N
    for i in range(start+1,N):
        cur = O_[i]-O_[i-1]
        if cur>0:
            A[i] = A[i-1] + (cur+1)
            B[i] = B[i-1] - 1
        else:
            A[i] = A[i-1] + 1
            B[i] = B[i-1] - (-cur+1)
    for i in range(start)[::-1]:
        cur = O_[i]-O_[i+1]
        if cur>0:
            B[i] = B[i+1] + (cur+1)
            A[i] = A[i+1] - 1
        else:
            B[i] = B[i+1] + 1
            A[i] = A[i+1] - (-cur+1)
    if A[0]<1:
        add = (1-A[0])
        for i in range(N):
            A[i] += add
    if B[-1]<1:
        add = (1-B[-1])
        for i in range(N):
            B[i] += add

    print(" ".join(map(str,A)))
    print(" ".join(map(str,B)))
    return

def examE():
    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=-1):
        loop = 0
        grundy = 0
        children = []
        for v in V[s]:
            if v==p:
                continue
            loop += 1
            children.append(dfs(v,s)+1)
        if loop==1:
            grundy = children[0]
        elif loop>1:
            for c in children:
                grundy ^= c
        return grundy
    if dfs(0):
        print("Alice")
    else:
        print("Bob")
    return

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


from decimal import getcontext,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 = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
9
7 3 9 1 8 4 5 6 2
"""

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
def dfs(v, par=-1):
  res = 0
  for nv in T[v]:
    if nv == par:
      continue
    res ^= dfs(nv, v)+1
  return res
if dfs(0) == 0:
  print("Bob")
else:
  print("Alice")

Solution (Python):
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
        
        for u in links[v]:
            g ^= grundy[u] + 1
        grundy[v] = g
    else:
        
        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')

Solution (Python):
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
            
            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()

"""

"""

Solution (Python):
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:  
        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()

Solution (Python):

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


if __name__ == "__main__":
    solve()

Solution (Python):
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")

Solution (Python):
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")

Solution (Python):
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')

Solution (Python):
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)

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

Solution (Python):
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")

Solution (Python):
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)]

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



def solve(v, parent=None):
    
    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')

Solution (Python):
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



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

Solution (Python):

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)


from collections import defaultdict


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

def DFS(G, XOR, visit, node):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			DFS(G, XOR, visit, i)
			XOR[node] ^= XOR[i] + 1


def main():
	N = int(input())
	G = Graph()
	for i in range(N - 1):
		x, y = getlist()
		x -= 1
		y -= 1
		G.add_edge(x, y)
		G.add_edge(y, x)

	
	XOR = [0] * N
	visit = ["No"] * N
	visit[0] = "Yes"
	DFS(G, XOR, visit, 0)
	if XOR[0] == 0:
		print("Bob")
	else:
		print("Alice")
	

if __name__ == '__main__':
	main()

Solution (Python):
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')

Solution (Python):
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")

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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')

Solution (Python):
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")

Solution (Python):
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"

Solution (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"

Solution (Python):
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'

Solution (Python):
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)


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

Solution (Python):
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())

Solution (Python):
import sys
import random


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




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():
    
    res = solve()
    print(res)


if __name__ == '__main__':
    main()