HA32_Cycle(11)

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

class Graph {
private:
    int N, M;
    vector<vector<int>> adj;
    vector<int> visited; // 0: не посещенный, 1: посещенный, 2: посещенный
    vector<int> parent;
    bool has_cycle;

public:
    Graph(int n, int m) : N(n), M(m) {
        adj.resize(N + 1);
        visited.resize(N + 1, 0);
        parent.resize(N + 1, -1);
        has_cycle = false;
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    void detectCycle() {
        stack<int> dfs_stack;

        for (int u = 1; u <= N && !has_cycle; ++u) {
            if (visited[u] == 0) {
                dfs_stack.push(u);
                visited[u] = 1;
                parent[u] = -1;

                while (!dfs_stack.empty()) {
                    int top = dfs_stack.top();
                    bool allNeighborsVisited = true;

                    for (int v : adj[top]) {
                        if (visited[v] == 0) {
                            visited[v] = 1;
                            parent[v] = top;
                            dfs_stack.push(v);
                            allNeighborsVisited = false;
                            break;
                        } else if (visited[v] == 1) {
                            stack<int> cycle_stack;
                            cycle_stack.push(v);
                            int temp = top;
                            while (temp != v) {
                                cycle_stack.push(temp);
                                temp = parent[temp];
                            }
                            cout << "YES" << endl;
                            while (!cycle_stack.empty()) {
                                cout << cycle_stack.top() << " ";
                                cycle_stack.pop();
                            }
                            cout << endl;
                            has_cycle = true;
                            return;
                        }
                    }

                    if (allNeighborsVisited) {
                        dfs_stack.pop();
                        visited[top] = 2;
                    }
                }
            }
        }
    }

    void findCycle() {
        detectCycle();
    }

    void printCycle() {
        if (!has_cycle) {
            cout << "NO" << endl;
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M;
    cin >> N >> M;
    Graph graph(N, M);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        graph.addEdge(u, v);
    }
    graph.findCycle();
    graph.printCycle();
    return 0;
}