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

Submission status: Runtime Error

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