트리 위의 게임
시간 제한1초메모리 제한256 MB
루트가 1인 트리에서 앨리스가 흰 정점 하나에 칩을 놓고, 두 사람이 번갈아 칩을 아직 검지 않은 조상이나 자손 정점으로 옮기며 그 정점을 검게 칠한다. 더 옮길 수 없는 사람이 지질 때 승자를 판정한다.
문제
Alice와 Bob이 트리에서 게임을 한다. 처음에는 모든 노드가 흰색이다.
Alice가 먼저 움직인다. Alice는 아무 노드나 골라 그 위에 칩을 놓는다. 그 노드는 검은색이 된다. 그다음부터는 번갈아 가며 턴을 진행한다. 각 턴에서 플레이어는 칩을 현재 위치에서 조상이나 자손 노드로 옮기는데, 그 노드가 검은색이 아니어야 한다. 옮긴 노드도 검은색이 된다. 칩을 옮길 수 없는 플레이어가 진다.
누가 이기는가?
루트가 있는 트리에서 노드 v의 조상은 v와 트리의 루트 사이 경로에 있는 모든 노드다.
루트가 있는 트리에서 노드 v의 자손은 노드 v가 w와 트리의 루트 사이 경로에 있는 모든 노드 w다.
트리의 루트는 1이다.
입력
첫째 줄에 정수 n (1 ≤ n ≤ 100 000)이 주어진다. n은 노드의 수다.
다음 n − 1개 줄에 두 정수 u와 v (1 ≤ u, v ≤ n)가 주어진다. u와 v는 트리의 간선이다. 이 간선들이 트리를 이룸이 보장된다.
출력
Alice가 이기면 한 줄에 “Alice”를 출력한다. 그렇지 않으면 “Bob”을 출력한다.
힌트
첫 번째 테스트에서 트리는 일직선이고 노드가 4개이므로, Bob은 항상 마지막 흰색 노드를 고를 수 있다.
두 번째 테스트에서 Alice의 최적 전략은 칩을 3에 놓는 것이다. 이 노드는 검은색이 된다. Bob은 노드 1을 골라야 한다. Alice는 4, 5, 6, 7 중 아무 노드나 고를 수 있다. Bob은 2만 고를 수 있다. Alice는 2의 흰색 자식 중 아무 노드나 고르고, Bob은 움직일 수 없다.