#ifdef NACHIA #define _GLIBCXX_DEBUG #else #define NDEBUG #endif #include #include #include #include #include #include #include #include using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i=0; i--) const i64 INF = 1001001001001001001; using namespace std; #include namespace nachia{ template class CsrArray{ public: struct ListRange{ using iterator = typename std::vector::iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } Elem& operator[](int i) const { return begi[i]; } }; struct ConstListRange{ using iterator = typename std::vector::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const Elem& operator[](int i) const { return begi[i]; } }; private: int m_n; std::vector m_list; std::vector m_pos; public: CsrArray() : m_n(0), m_list(), m_pos() {} static CsrArray Construct(int n, std::vector> items){ CsrArray res; res.m_n = n; std::vector buf(n+1, 0); for(auto& [u,v] : items){ ++buf[u]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.m_list.resize(buf[n]); for(int i=(int)items.size()-1; i>=0; i--){ res.m_list[--buf[items[i].first]] = std::move(items[i].second); } res.m_pos = std::move(buf); return res; } static CsrArray FromRaw(std::vector list, std::vector pos){ CsrArray res; res.m_n = pos.size() - 1; res.m_list = std::move(list); res.m_pos = std::move(pos); return res; } ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } int size() const { return m_n; } int fullSize() const { return (int)m_list.size(); } }; } // namespace nachia namespace nachia{ struct Graph { public: struct Edge{ int from, to; void reverse(){ std::swap(from, to); } int xorval() const { return from ^ to; } }; Graph(int n = 0, bool undirected = false, int m = 0) : m_n(n), m_e(m), m_isUndir(undirected) {} Graph(int n, const std::vector>& edges, bool undirected = false) : m_n(n), m_isUndir(undirected){ m_e.resize(edges.size()); for(std::size_t i=0; i static Graph Input(Cin& cin, int n, bool undirected, int m, bool offset = 0){ Graph res(n, undirected, m); for(int i=0; i> u >> v; res[i].from = u - offset; res[i].to = v - offset; } return res; } int numVertices() const noexcept { return m_n; } int numEdges() const noexcept { return int(m_e.size()); } int addNode() noexcept { return m_n++; } int addEdge(int from, int to){ m_e.push_back({ from, to }); return numEdges() - 1; } Edge& operator[](int ei) noexcept { return m_e[ei]; } const Edge& operator[](int ei) const noexcept { return m_e[ei]; } Edge& at(int ei) { return m_e.at(ei); } const Edge& at(int ei) const { return m_e.at(ei); } auto begin(){ return m_e.begin(); } auto end(){ return m_e.end(); } auto begin() const { return m_e.begin(); } auto end() const { return m_e.end(); } bool isUndirected() const noexcept { return m_isUndir; } void reverseEdges() noexcept { for(auto& e : m_e) e.reverse(); } void contract(int newV, const std::vector& mapping){ assert(numVertices() == int(mapping.size())); for(int i=0; i induce(int num, const std::vector& mapping) const { int n = numVertices(); assert(n == int(mapping.size())); for(int i=0; i indexV(n), newV(num); for(int i=0; i= 0) indexV[i] = newV[mapping[i]]++; std::vector res; res.reserve(num); for(int i=0; i= 0) res[mapping[e.to]].addEdge(indexV[e.from], indexV[e.to]); return res; } CsrArray getEdgeIndexArray(bool undirected) const { std::vector> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(int i=0; i::Construct(numVertices(), src); } CsrArray getEdgeIndexArray() const { return getEdgeIndexArray(isUndirected()); } CsrArray getAdjacencyArray(bool undirected) const { std::vector> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(auto e : m_e){ src.emplace_back(e.from, e.to); if(undirected) src.emplace_back(e.to, e.from); } return CsrArray::Construct(numVertices(), src); } CsrArray getAdjacencyArray() const { return getAdjacencyArray(isUndirected()); } private: int m_n; std::vector m_e; bool m_isUndir; }; } // namespace nachia namespace nachia{ struct DfsTree{ std::vector dfsOrd; std::vector parent; template static DfsTree Construct(const CsrArray& adj, int root = 0){ DfsTree res; int n = adj.size(); res.dfsOrd.resize(n); int Oi = 0; std::vector eid(n, 0), parent(n, -2); for(int s=root; Oi static DfsTree Construct(const Graph& g, int root = 0){ return Construct(g.getAdjacencyArray(), root); } }; } // namespace nachia namespace nachia{ struct TwoEdgeConnectedComponents{ Graph mG; int m_numComponent; std::vector m_color; TwoEdgeConnectedComponents(Graph G = Graph(0, true)){ assert(G.isUndirected()); int n = G.numVertices(), m = G.numEdges(); if(n == 0){ mG = G; m_numComponent = 0; return; } std::vector P, ord, I(n); { auto dfsTree = DfsTree::Construct(G); P = std::move(dfsTree.parent); ord = std::move(dfsTree.dfsOrd); for(int i=0; i rev = I, PE(n, -1); for(int e=0; e=0; i--){ int v = ord[i], w = P[v]; if(w >= 0) rev[w] = std::min(rev[w], rev[v]); } m_numComponent = 0; m_color.resize(n); for(int v : ord){ if(rev[v] == I[v]) m_color[v] = m_numComponent++; else m_color[v] = m_color[P[v]]; } mG = std::move(G); } int numComponents() const noexcept { return m_numComponent; } int operator[](int v) const { return m_color[v]; } CsrArray getTeccVertices() const { int n = mG.numVertices(); std::vector> res(n); for(int i=0; i::Construct(numComponents(), res); } // bridge : -1 std::vector getEdgeMapping() const { std::vector res(mG.numEdges(), -1); for(int i=0; i getVertexMapping() const { return m_color; } }; } namespace nachia { struct DsuFast{ private: std::vector w; public: DsuFast(int n = 0) : w(n, -1) {} int leader(int u){ if(w[u] < 0) return u; return w[u] = leader(w[u]); } int operator[](int u){ return leader(u); } int merge(int u, int v){ u = leader(u); v = leader(v); if(u == v) return u; if(-w[u] < -w[v]) std::swap(u, v); w[u] += w[v]; w[v] = u; return u; } int size(int u){ return -w[leader(u)]; } bool same(int u, int v){ return leader(u) == leader(v); } }; } // namespace nachia namespace nachia{ struct ConnectedComponents{ ConnectedComponents(const CsrArray& adj){ int n = adj.size(); DsuFast dsu(n); for(int v=0; v& getMapping() const { return m_color; } CsrArray getCsr() const { std::vector> buf(m_color.size()); for(int i=0; i<(int)m_color.size(); i++){ buf[i] = std::make_pair(m_color[i], i); } return CsrArray::Construct(numComponents(), std::move(buf)); } private: int m_numC; std::vector m_color; }; } // namespace nachia void testcase(){ int N; cin >> N; auto graph = nachia::Graph::Input(cin, N, true, N-1, 0); auto tecc = nachia::TwoEdgeConnectedComponents(graph).numComponents(); auto cc = nachia::ConnectedComponents(graph).numComponents(); if(cc == 1 || tecc <= 2){ cout << "Bob\n"; } else cout << "Alice\n"; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); testcase(); return 0; }