enum class Colour { White, Grey, Black };

template <bool IsOriented>  // NOLINT
class Graph {
 private:
  int number_of_vertex_ = 0;
  vector<vector<int>> neighbours_;
  vector<int> parent_;
  vector<Colour> colour_;
  vector<int> cycle_;
  int flag_;

 public:
  Graph(int num_of_vert)
    : number_of_vertex_(num_of_vert),
      neighbours_(vector<vector<int>>(num_of_vert)),
      parent_(vector<int>(num_of_vert)),
      colour_(vector<Colour>(num_of_vert, Colour::White)),
      flag_(0) {}

  void AddEdge(int begin, int end) {
    if constexpr (!IsOriented) {
      neighbours_[begin - 1].push_back(end - 1);
    }
    neighbours_[end - 1].push_back(begin - 1);
  }

  std::optional<vector<int>> TryFindCycleInComponent(int vertex, int parent) {
    parent_[vertex] = parent;
    colour_[vertex] = Colour::Grey;
    for (int to : neighbours_[vertex]) {
      if (flag_ == 1) {
        break;
      }
      if (colour_[to] == Colour::Black) {
        continue;
      }
      if (colour_[to] == Colour::Grey) {
        std::cout << "YES\n";
        flag_ = 1;
        vector<int> cycle;
        int start_cycle = vertex;
        while (start_cycle != to) {
          cycle.push_back(start_cycle + 1);
          start_cycle = parent_[start_cycle];
        }
        cycle.push_back(to + 1);
        for (int i = cycle.size() - 1; i >= 0; --i) {
          std::cout << cycle[i] << " ";
        }
        colour_[vertex] = Colour::Black;
        return {cycle};
      }
      TryFindCycleInComponent(to, vertex);
    }
    colour_[vertex] = Colour::Black;
    return {};
  }

  std::optional<vector<int>> TryFindCycleInGraph() {
    for (int i = 0; i < number_of_vertex_; ++i) {
      if (colour_[i] == Colour::White) {
        TryFindCycleInComponent(i, -1);
      }
      if (flag_ == 1) {
        return TryFindCycleInComponent(i, -1);
      }
    }
    return {};
  }
};