Alice and Bob are playing a game with a rooted tree. The tree has $N$ vertices and the first node, $1$, is always the root. Here are the basic rules:

They move in alternating turns, and both players always move optimally.
During each move, a player removes an edge from the tree, disconnecting one of its leaves or branches. The leaf or branch that was disconnected from the rooted tree is removed from the game. 
The first player to be unable to make a move loses the game.
Alice always makes the first move. 

For example, the diagram below shows a tree of size $n=7$, where the root is node $1$:

Now, if a player removes the edge between $1$ and $4$, then nodes $4$ and $7$ become disconnected from the root and are removed from the game:

Given the structure of the tree, determine and print the winner of the game. If Alice wins, print $\textbf{Alice}$; otherwise print $\textbf{Bob}$.

Input Format

The first line contains a single integer, $\mathbf{T}$, denoting the number of test cases. 

For each test case, the first line contains an integer, $N$, denoting the number of nodes in the tree. 

Each of the $N-1$ subsequent lines contains $2$ space-separated integers, $\mbox{u}$ and $v$, defining an edge connecting nodes $\mbox{u}$ and $v$.

Constraints

$1\leq T\leq100$
$1\leq N\leq500$
$1\leq u,v\leq N$

Output Format

For each test case, print the name of the winner (i.e., $\textbf{Alice}$ or $\textbf{Bob}$) on a new line.

Sample Input
1
5
1 2
3 1
3 4
4 5

Sample Output
Alice

Explanation

Test Case 0:

Alice removes the edge connecting node $3$ to node $4$, effectively trimming nodes $4$ and $5$ from the tree. Now the only remaining edges are $1\leftrightarrow2$ and $1\leftrightarrow3$. Because Bob can't remove both of them, Alice will make the last possible move. Because the last player to move wins, we print $\textbf{Alice}$ on a new line.

Source: hackerrank | Difficulty: MEDIUM
Tags: Game theory


Solutions:
def hackenbush(i, p):
	v = 0
	for x in g[i]:
		if x == p:
			continue
		v = v ^ hackenbush(x, i) + 1
	return v
t = int(input())
for _ in range(t):
	try:
		n = int(input())
		g = {}
		for i in range(1, n + 1):
			g[i] = []
		for i in range(n - 1):
			(a, b) = map(int, input().split())
			g[a].append(b)
			g[b].append(a)
		if hackenbush(1, 0):
			print('Alice')
		else:
			print('Bob')
	except EOFError:
		break


from bisect import insort

class Node:

	def __init__(self, val=0):
		self.val = val
		self.children = []

def connect(n1, n2):
	if nodes[n1] is None:
		nodes[n1] = Node()
		nodes[n2].children.append(nodes[n1])
	else:
		nodes[n2] = Node()
		nodes[n1].children.append(nodes[n2])

def makeTree(n1):
	for n2 in tree[n1]:
		if visited[n2]:
			continue
		connect(n1, n2)
		visited[n1] = True
		makeTree(n2)

def reduceNode(node):
	current = node
	while len(current.children) == 1:
		node.val += 1
		current = current.children[0]
	node.children = current.children

def getGrundy(node):
	grundy = 0
	for child in node.children:
		if child.children:
			grundy ^= getGrundy(child) + 1
		else:
			grundy ^= child.val + 1
	node.val = grundy
	return grundy

def report():
	for i in range(1, n + 1):
		print(i, ':', nodes[i].val)
		print(nodes[i].children)
		print()
for _ in range(int(input())):
	n = int(input())
	nodes = [None] * (n + 1)
	grundy = {}
	root = Node()
	nodes[1] = root
	tree = [[] for _ in range(n + 1)]
	visited = [False] * (n + 1)
	for _ in range(n - 1):
		(n1, n2) = [int(x) for x in input().split(' ')]
		tree[n1].append(n2)
		tree[n2].append(n1)
	makeTree(1)
	g = getGrundy(root)
	print('Alice' if g else 'Bob')


class PriorityQueue:

	def __init__(self, iterable, initial_cost_fn=lambda x: 0):
		self._queue = list(iterable)
		self._costs = [initial_cost_fn(x) for x in self._queue]
		self._queue_index = {x: i for (i, x) in enumerate(self._queue)}
		self._build_heap()

	def __len__(self):
		return len(self._queue)

	def __contains__(self, item):
		return item in self._queue_index

	def peek(self):
		return self._queue[0]

	def pop(self):
		front = self.peek()
		self._swap(0, len(self._queue) - 1)
		self._queue.pop()
		self._costs.pop()
		del self._queue_index[front]
		self._heapify(0)
		return front

	def decrement_cost(self, item):
		item_index = self._queue_index[item]
		self._costs[item_index] -= 1
		self._bubble(item_index)

	def _swap(self, i, j):
		if i != j:
			(self._queue[i], self._queue[j]) = (self._queue[j], self._queue[i])
			(self._costs[i], self._costs[j]) = (self._costs[j], self._costs[i])
			self._queue_index[self._queue[i]] = i
			self._queue_index[self._queue[j]] = j

	def _heapify(self, i):
		while True:
			least_i = i
			for poss_i in range(2 * i + 1, min(2 * i + 3, len(self._queue))):
				if self._costs[poss_i] < self._costs[least_i]:
					least_i = poss_i
			if least_i == i:
				return
			self._swap(i, least_i)
			i = least_i

	def _bubble(self, i):
		while i > 0:
			parent_i = (i - 1) // 2
			if not self._costs[i] < self._costs[parent_i]:
				break
			self._swap(parent_i, i)
			i = parent_i

	def _build_heap(self):
		for i in range((len(self._queue) - 2) // 2, -1, -1):
			self._heapify(i)
T = int(input().strip())
for t in range(T):
	N = int(input().strip())
	neighbors = [set() for i in range(N)]
	for i in range(N - 1):
		(u, v) = (int(x) for x in input().strip().split())
		u -= 1
		v -= 1
		neighbors[u].add(v)
		neighbors[v].add(u)
	nimbers = [0 for i in range(N)]
	queue = PriorityQueue(range(1, N), lambda i: len(neighbors[i]))
	while len(queue) > 0:
		curr = queue.pop()
		parent = next(iter(neighbors[curr]))
		neighbors[curr].remove(parent)
		neighbors[parent].remove(curr)
		if parent in queue:
			queue.decrement_cost(parent)
		nimbers[parent] ^= nimbers[curr] + 1
	nimber = nimbers[0]
	if nimber == 0:
		print('Bob')
	else:
		print('Alice')


from collections import defaultdict

def sg(G, cur_node, parent_node):
	ans = 0
	for child_node in G[cur_node]:
		if child_node != parent_node:
			ans ^= sg(G, child_node, cur_node) + 1
	return ans
for t in range(int(input())):
	N = int(input())
	G = defaultdict(list)
	for i in range(N - 1):
		(u, v) = sorted(map(int, input().split()))
		G[u].append(v)
		G[v].append(u)
	nim_sum = sg(G, 1, -1)
	print(['Bob', 'Alice'][nim_sum > 0])


from collections import defaultdict

def calculate_nimber(node):
	visited.add(node)
	children = list(graph[node] - visited)
	if len(children) == 0:
		return 0 if node == 1 else 1
	elif len(children) == 1:
		return 1 + calculate_nimber(children[0])
	else:
		temp = 0
		for child in children:
			temp ^= calculate_nimber(child)
		return temp if node == 1 else temp + 1
t = int(input())
for _ in range(t):
	graph = defaultdict(set)
	visited = set()
	n = int(input())
	for __ in range(n - 1):
		(i, j) = (int(i) for i in input().split())
		graph[i].add(j)
		graph[j].add(i)
	print('Alice' if calculate_nimber(1) != 0 else 'Bob')


from collections import defaultdict
from functools import reduce
from operator import xor

def grundy(graph, node, parent):
	children = (grundy(graph, child, node) for child in graph[node] if child != parent)
	return reduce(xor, children, 0) + int(parent != 0)
for _ in range(int(input())):
	graph = defaultdict(set)
	for _ in range(int(input()) - 1):
		(x, y) = (int(x) for x in input().split())
		graph[x].add(y)
		graph[y].add(x)
	print('Alice' if grundy(graph, 1, 0) else 'Bob')


from collections import defaultdict

def h_score(tree, parent, node):
	score = 0
	for branch in tree[node]:
		if branch != parent:
			score ^= h_score(tree, node, branch) + 1
	return score
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	tree = defaultdict(set)
	for _ in range(n - 1):
		(u, v) = [int(temp) for temp in input().strip().split(' ')]
		tree[u].add(v)
		tree[v].add(u)
	if h_score(tree, -1, 1) == 0:
		print('Bob')
	else:
		print('Alice')


from collections import defaultdict

def h_score(tree, parent, node):
	score = 0
	for branch in tree[node]:
		if branch != parent:
			score ^= h_score(tree, node, branch) + 1
	return score
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	tree = defaultdict(set)
	for _ in range(n - 1):
		(u, v) = [int(temp) for temp in input().strip().split(' ')]
		tree[u].add(v)
		tree[v].add(u)
	if h_score(tree, -1, 1) == 0:
		print('Bob')
	else:
		print('Alice')


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():
	T = int(input())
	for _ in range(T):
		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')
main()


t = int(input().strip())

def _print(*value):
	if TESTING:
		print(*value)

class Node(object):

	def __init__(self, root, name, parent=None):
		self.name = name
		self.root = root
		self.parent = parent
		self.children = []
		self.nim_sum = None
		if parent is not None:
			parent.add_child(self)

	def add_child(self, child):
		self.children.append(child)
		return child

	def remove_child(self, child):
		self.children.remove(child)
		return child

	def make_child(self, name=None):
		child = Node(self.root, self.root.new_node_name() if name is None else name, self)
		self.root.node_dict[child.name] = child
		_print('new node created:', child.name)
		return child

	def set_parent(self, new_parent):
		_print('new parent:', self.name, self.parent.name, new_parent.name)
		if self.name == new_parent.name:
			self.make_child()
		else:
			self.parent.remove_child(self)
			self.parent = new_parent
			new_parent.add_child(self)

	def path_to_root(self):
		if self.parent is None:
			return [self]
		return [self] + self.parent.path_to_root()

	def get_nim_sum(self):
		if self.nim_sum is not None:
			return self.nim_sum
		nim_sum = 0
		for child in self.children:
			nim_sum ^= child.get_nim_sum()
		self.nim_sum = nim_sum + 1
		_print('nim-sum for node', self.name, 'is:', self.nim_sum)
		return self.nim_sum

class Root(Node):

	def __init__(self):
		super().__init__(self, 1)
		self.node_dict = {1: self}
		self.all_loops = []
		self.hold_edge = []
		self.new_node = 0

	def join_nodes(self, name1, name2):
		n1_exists = name1 in self.node_dict
		n2_exists = name2 in self.node_dict
		same = name1 == name2
		n1 = self.node_dict[name1] if n1_exists else None
		n2 = self.node_dict[name2] if n2_exists else None
		if same and n1_exists:
			n1.make_child()
		elif not same and n1_exists and n2_exists:
			_print('big loop found:', name1, name2)
			self.all_loops.append((n1, n2))
		elif not same and n1_exists:
			n1.make_child(name2)
		elif not same and n2_exists:
			n2.make_child(name1)
		else:
			_print('holding', name1, name2)
			self.hold_edge.append((name1, name2))
			return False
		return True

	def finish_map(self):
		while len(self.hold_edge):
			not_done = []
			_print('still holding:', self.hold_edge)
			for pair in self.hold_edge.copy():
				if not self.join_nodes(*pair):
					not_done.append(pair)
			self.hold_edge = not_done

	def make_into_tree(self):
		for (node1, node2) in self.all_loops:
			(common, path1, path2) = self.find_common_root(node1, node2, paths=True)
			_print('loop', common.name, [n.name for n in path1], [n.name for n in path2])
			for path in [path1[::-1], path2[::-1]]:
				for node in path:
					if node.parent is not None and node.parent.name == common.name:
						for child in node.children.copy():
							child.set_parent(common)
			common.make_child()
		self.all_loops = []

	def find_common_root(self, node1, node2, paths=False):
		path1 = node1.path_to_root()
		path2 = node2.path_to_root()
		for (i, n) in enumerate(path1):
			if n in path2:
				return (n, path1[:i + 1], path2[:path2.index(n) + 1]) if paths else n

	def new_node_name(self):
		self.new_node -= 1
		return self.new_node + 1

	def get_nim_sum(self):
		nim_sum = 0
		for node in self.children:
			nim_sum ^= node.get_nim_sum()
		_print('tree nim-sum:', nim_sum)
		return nim_sum

	def get_first_winner(self):
		nim_sum = self.get_nim_sum()
		if nim_sum == 0:
			return False
		return True
TESTING = False
for _ in range(t):
	n = int(input().strip())
	root = Root()
	for _ in range(n - 1):
		root.join_nodes(*[int(i) for i in input().strip().split(' ')])
	_print([(i, [c.name for c in n.children]) for (i, n) in root.node_dict.items()])
	root.finish_map()
	_print([(i, [c.name for c in n.children]) for (i, n) in root.node_dict.items()])
	root.make_into_tree()
	_print([(i, [c.name for c in n.children]) for (i, n) in root.node_dict.items()])
	print('Alice' if root.get_first_winner() else 'Bob')


import sys
from time import time
vcache = set()
wcache = dict()

def weight(node, g):
	if node in wcache:
		return wcache[node]
	vcache.add(node)
	rval = 0
	for nxt in g[node]:
		if nxt not in vcache:
			rval ^= weight(nxt, g) + 1
	wcache[node] = rval
	print('\tnode=%d rval=%d' % (node, rval), file=sys.stderr)
	return rval

def height_gen(g, root):
	cache = set()
	stack = [(root, 0)]
	while stack:
		(n, h) = stack.pop()
		cache.add(n)
		cnt = 0
		for m in g[n]:
			if m not in cache:
				cnt += 1
				stack.append((m, h + 1))
		yield (n, h, cnt == 0)

def solve(g):
	print('g=%s' % (sorted(g.items()),), file=sys.stderr)
	for (n, h, is_leaf) in height_gen(g, 1):
		print('\tn=%d h=%d %s' % (n, h, is_leaf), file=sys.stderr)
	vcache.clear()
	wcache.clear()
	for n in sorted(g):
		w = weight(n, g)
		print('\tn=%d w=%d' % (n, w), file=sys.stderr)
	return weight(1, g) > 0
tm = time()
t = int(input())
for _ in range(t):
	n = int(input())
	g = {node: set() for node in range(1, n + 1)}
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		for (a, b) in ((u, v), (v, u)):
			g[a].add(b)
	if solve(g):
		print('Alice')
	else:
		print('Bob')
print('time elapsed: %s' % (time() - tm,), file=sys.stderr)


import os
import sys
from collections import defaultdict
from functools import reduce
sys.setrecursionlimit(100000)

def get_breadth_first_nodes(root, nodes=[]):
	stack = [root]
	while stack:
		cur_node = stack[0]
		stack = stack[1:]
		nodes.append(cur_node)
		for child in graph[cur_node]:
			if child not in nodes:
				stack.append(child)
	return nodes
for _ in range(int(input())):
	n = int(input())
	graph = defaultdict(set)
	for _ in range(n - 1):
		e = list(map(int, input().split()))
		if e[0] in graph.keys():
			graph[e[0]].append(e[1])
		else:
			graph[e[0]] = [e[1]]
		if e[1] in graph.keys():
			graph[e[1]].append(e[0])
		else:
			graph[e[1]] = [e[0]]
	bfs = get_breadth_first_nodes(1, [])
	d = defaultdict(list)
	for node in bfs[:0:-1]:
		if d[node] == []:
			graph[graph[node][0]].remove(node)
			d[graph[node][0]].append(1)
			del graph[node]
		else:
			graph[graph[node][0]].remove(node)
			d[graph[node][0]].append(1 + reduce(lambda x, y: x ^ y, d[node]))
			del graph[node]
	if n == 1:
		print('Bob')
	else:
		print('Alice') if reduce(lambda x, y: x ^ y, d[1]) else print('Bob')


def hackenbush(i, p):
	v = 0
	for x in g[i]:
		if x == p:
			continue
		v = v ^ hackenbush(x, i) + 1
	return v
t = int(input())
for _ in range(t):
	try:
		n = int(input())
		g = {}
		for i in range(1, n + 1):
			g[i] = []
		for i in range(n - 1):
			(a, b) = map(int, input().split())
			g[a].append(b)
			g[b].append(a)
		if hackenbush(1, 0):
			print('Alice')
		else:
			print('Bob')
	except EOFError:
		break


from collections import defaultdict
from queue import Queue

def readGraph():
	graph = defaultdict(set)
	for i in range(eval(input()) - 1):
		(v1, v2) = list(map(int, input().split()))
		graph[v1].add(v2)
		graph[v2].add(v1)
	return dict(graph)

def createRootedTree(tree, root):
	(rootedTree, frontier, checked) = (defaultdict(list), Queue(), {root})
	frontier.put(root)
	while not frontier.empty():
		v = frontier.get()
		for i in tree[v]:
			if i not in checked:
				rootedTree[v].append(i)
				checked.add(i)
				frontier.put(i)
	return dict(rootedTree)

def green_hackenbush(tree, node):
	res = 0
	if node in tree:
		for child in tree[node]:
			res ^= 1 + green_hackenbush(tree, child)
	return res
for i in range(eval(input())):
	tree = readGraph()
	rooted_tree = {} if 1 not in tree else createRootedTree(tree, 1)
	print('Alice' if green_hackenbush(rooted_tree, 1) != 0 else 'Bob')


def gr(g, v, p=0):
	x = 0
	for u in g[v]:
		if u != p:
			x ^= gr(g, u, v)
	return x + 1
for _ in range(int(input())):
	n = int(input())
	g = {i: set() for i in range(1, n + 1)}
	for _ in range(1, n):
		(u, v) = map(int, input().split())
		g[u].add(v)
		g[v].add(u)
	print('Alice' if gr(g, 1) - 1 else 'Bob')


def hackenbush(i, p):
	v = 0
	for x in g[i]:
		if x == p:
			continue
		v = v ^ hackenbush(x, i) + 1
	return v
t = int(input())
for _ in range(t):
	try:
		n = int(input())
		g = {}
		for i in range(1, n + 1):
			g[i] = []
		for i in range(n - 1):
			(a, b) = map(int, input().split())
			g[a].append(b)
			g[b].append(a)
		if hackenbush(1, 0):
			print('Alice')
		else:
			print('Bob')
	except EOFError:
		break


def hackenbush(i, p):
	v = 0
	for x in g[i]:
		if x == p:
			continue
		v = v ^ hackenbush(x, i) + 1
	return v
t = int(input())
for _ in range(t):
	try:
		n = int(input())
		g = {}
		for i in range(1, n + 1):
			g[i] = []
		for i in range(n - 1):
			(a, b) = map(int, input().split())
			g[a].append(b)
			g[b].append(a)
		if hackenbush(1, 0):
			print('Alice')
		else:
			print('Bob')
	except EOFError:
		break


def hackenbush(i, p):
	v = 0
	for x in g[i]:
		if x == p:
			continue
		v = v ^ hackenbush(x, i) + 1
	return v
t = int(input())
for _ in range(t):
	try:
		n = int(input())
		g = {}
		for i in range(1, n + 1):
			g[i] = []
		for i in range(n - 1):
			(a, b) = map(int, input().split())
			g[a].append(b)
			g[b].append(a)
		if hackenbush(1, 0):
			print('Alice')
		else:
			print('Bob')
	except EOFError:
		break


def hackenbush(i, p):
	v = 0
	for x in g[i]:
		if x == p:
			continue
		v = v ^ hackenbush(x, i) + 1
	return v
t = int(input())
for _ in range(t):
	try:
		n = int(input())
		g = {}
		for i in range(1, n + 1):
			g[i] = []
		for i in range(n - 1):
			(a, b) = map(int, input().split())
			g[a].append(b)
			g[b].append(a)
		if hackenbush(1, 0):
			print('Alice')
		else:
			print('Bob')
	except EOFError:
		break


def hackenbush(i, p):
	v = 0
	for x in g[i]:
		if x == p:
			continue
		v = v ^ hackenbush(x, i) + 1
	return v
t = int(input())
for _ in range(t):
	try:
		n = int(input())
		g = {}
		for i in range(1, n + 1):
			g[i] = []
		for i in range(n - 1):
			(a, b) = map(int, input().split())
			g[a].append(b)
			g[b].append(a)
		if hackenbush(1, 0):
			print('Alice')
		else:
			print('Bob')
	except EOFError:
		break