#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
private:
    bool detectCycle(int start, vector<vector<int>>& adj, vector<int>& vis) {
        queue<pair<int, int>> q;
        vis[start] = 1;
        q.push({start, -1});

        while (!q.empty()) {
            int node = q.front().first;
            int parent = q.front().second;
            q.pop();

            for (int neighbour : adj[node]) {
                if (!vis[neighbour]) {
                    vis[neighbour] = 1;
                    q.push({neighbour, node});
                } else if (neighbour != parent) {
                    return true;
                }
            }
        }
        return false;
    }

public:
    bool isCycle(int V, vector<vector<int>>& edgeList) {
        vector<vector<int>> adj(V);
        for (auto& edge : edgeList) {
            int u = edge[0], v = edge[1];
            adj[u].push_back(v);
            adj[v].push_back(u);  // undirected
        }

        // Print the adjacency list
        cout << "Adjacency List:\n";
        for (int i = 0; i < V; i++) {
            cout << i << " -> ";
            for (auto neighbor : adj[i]) {
                cout << neighbor << " ";
            }
            cout << "\n";
        }

        vector<int> vis(V, 0);
        for (int i = 0; i < V; ++i) {
            if (!vis[i] && detectCycle(i, adj, vis)) {
                return true;
            }
        }
        return false;
    }
};

int main() {
    Solution s;

    // Example Test
    int V = 4;
    vector<vector<int>> edges = {
        {1, 2},
        {2, 3}
    };

    bool hasCycle = s.isCycle(V, edges);
    cout << (hasCycle ? "Cycle detected" : "No cycle") << '\n';
    return 0;
}