##################################################################################################### ##### Low Link (二重辺連結成分分解) ##################################################################################################### """ 計算量 O(V+E) 二重辺連結成分分解 閉路のリストに分解する 参考 https://algo-logic.info/bridge-lowlink/ ベンチマーク https://atcoder.jp/contests/abc075/submissions/15110847 """ class Graph: def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]): self.n = n self.directed = directed self.decrement = decrement self.destroy = destroy self.edges = [[] for _ in range(self.n)] self.deg = [0] * n for x, y in edges: self.add_edge(x,y) def add_edge(self, u, v): self.edges[u - self.decrement].append(v - self.decrement) self.edges[v - self.decrement].append(u - self.decrement) self.deg[u - self.decrement] += 1 self.deg[v - self.decrement] += 1 def get_multi_edge(self): res = set() for i, g in enumerate(self.edges): tmp = set((i, v) for v in set(g) if g.count(v) > 1) res |= tmp return res def bfs(self, s, t=None): dist = [None] * self.n dist[s] = 0 prev = [None] * self.n queue = deque([s]) while queue: v = queue.popleft() for adj in self.edges[v]: if dist[adj] is not None:continue dist[adj] = dist[v] + 1 queue.append(adj) if t is None: return dist path = [t] while t != s: t = prev[t] path.append(t) return dist, path[::-1] def lowlink(self): self.ord = [None] * self.n self.low = [None] * self.n self.par = [None] * self.n self.tree = [[] for _ in range(self.n)] group = [None] * self.n medge = self.get_multi_edge() vis = [] ord = 0 cnt = 0 for s in range(self.n): if group[s] is not None: continue stack = [(s, None)] while stack: v, p = stack.pop() if group[v] is not None: continue self.ord[v] = ord group[v] = cnt vis.append(v) ord += 1 if p is not None: self.par[v] = p self.tree[p].append(v) for adj in self.edges[v]: if group[adj] is not None: continue stack.append((adj, v)) cnt += 1 for v in vis[::-1]: self.low[v] = self.ord[v] for adj in self.edges[v]: if self.par[adj] == v: self.low[v] = min(self.low[v], self.low[adj]) elif self.par[v] == adj and (v, adj) not in medge: continue else: self.low[v] = min(self.low[v], self.ord[adj]) def articulation(self): res = [] idx=self.decrement for v in range(self.n): if self.par[v] is None and len(self.tree[v]) > 1: res.append(v) if self.par[v] is None: continue for adj in self.tree[v]: if self.ord[v] <= self.low[adj]: res.append(v+idx) break return res def bridge(self): res = [] idx=self.decrement for v in range(self.n): for adj in self.tree[v]: if self.ord[v] < self.low[adj]: res.append((v+idx, adj+idx)) return res def two_edge_connected(self, bridge): """ decompose graph into list of cycles """ idx=self.decrement bridge = set(bridge) group = [None] * self.n cnt = 0 for s in range(self.n): if group[s] is not None: continue group[s] = cnt stack = [s] while stack: v = stack.pop() for adj in self.edges[v]: if group[adj] is not None or (v+idx, adj+idx) in bridge or (adj+idx, v+idx) in bridge: continue group[adj] = cnt stack.append(adj) cnt += 1 res = [[] for _ in range(cnt)] for i, g in enumerate(group): res[g].append(i+idx) return res def draw(self): """ :return: グラフを可視化 """ import matplotlib.pyplot as plt import networkx as nx if self.directed: G = nx.DiGraph() else: G = nx.Graph() for x in range(self.n): for y in self.edges[x]: G.add_edge(x + self.decrement, y + self.decrement) pos = nx.spring_layout(G) nx.draw_networkx(G, pos, connectionstyle='arc3, rad = 0.1') plt.axis("off") plt.show() class UnionFind: def __init__(self, n): self.n = n self.parents = [-1] * n def find(self, x): """ 根を見つける関数を定義(同時にxを直接根にくっつける操作も行う)""" tmp = [] parents = self.parents while parents[x] >= 0: tmp.append(x) x = parents[x] for y in tmp: parents[y] = x return x def union(self, x, y): """ 二つの木をくっつける(子を多く持つ方を根とした親子関係)。これは破壊的操作を行う。""" x = self.find(x) y = self.find(y) if x == y: return if self.parents[x] > self.parents[y]: x, y = y, x self.parents[x] += self.parents[y] self.parents[y] = x def same(self, x, y): """ xとyが同じ根の子かを判定 """ return self.find(x) == self.find(y) def size(self, x): """ xの根のparent(= 要素数)を返す """ return -self.parents[self.find(x)] def members(self, x): """ xが属するグループの要素をリストとして返す O(N)""" root = self.find(x) return [i for i in range(self.n) if self.find(i) == root] def roots(self): """ 全ての根の要素をリストとして返す O(N)""" return [i for i, x in enumerate(self.parents) if x < 0] def group_count(self): """ グループの数を返す O(N)""" return len(self.roots()) def size_list(self): """ 各グループの要素数のリストを返す(根の番号は返さない) O(N)""" return [-x for x in self.parents if x < 0] def all_group_members(self): """ {根:[根の子(根を含む)のリスト],...}を辞書で返す O(N)""" res = [[] for _ in range(self.n)] for i in range(self.n): x = self.find(i) res[x].append(i) return {r: res[r] for r in self.roots()} def __str__(self): return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots()) ############################################################################################### def example(): global input example = iter( """ 6 1 2 2 3 3 1 4 5 5 6 """ .strip().split("\n")) input = lambda: next(example) ############################################################################################### import sys input = sys.stdin.readline from collections import deque # example() N=int(input()) graph = Graph(N, directed=False, decrement=False, destroy=False) U=UnionFind(N) for _ in range(N-1): x, y = map(int, input().split()) graph.add_edge(x, y) U.union(x,y) graph.lowlink() island=U.group_count() bridge = len(graph.bridge()) if bridge>=1: bridge-=1 island+=1 island-=1 print("Alice" if island>1 else "Bob")