1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

#define COLOR_BLACK "\x1b[30m"
#define COLOR_RED "\x1b[31m"
#define COLOR_GREEN "\x1b[32m"
#define COLOR_YELLOW "\x1b[33m"
#define COLOR_BLUE "\x1b[34m"
#define COLOR_MAGENTA "\x1b[35m"
#define COLOR_CYAN "\x1b[36m"
#define COLOR_WHITE "\x1b[37m"
#define COLOR_RESET "\x1b[0m"

#define COLOR_BOLDBLACK "\033[1m\033[30m"
#define COLOR_BOLDRED "\033[1m\033[31m"
#define COLOR_BOLDGREEN "\033[1m\033[32m"
#define COLOR_BOLDYELLOW "\033[1m\033[33m"
#define COLOR_BOLDBLUE "\033[1m\033[34m"
#define COLOR_BOLDMAGENTA "\033[1m\033[35m"
#define COLOR_BOLDCYAN "\033[1m\033[36m"
#define COLOR_BOLDWHITE "\033[1m\033[37m"

const std::vector<const char*> colors{
    COLOR_RED,        COLOR_GREEN,    COLOR_YELLOW,      COLOR_BLUE,
    COLOR_MAGENTA,    COLOR_CYAN,     COLOR_BOLDRED,     COLOR_BOLDGREEN,
    COLOR_BOLDYELLOW, COLOR_BOLDBLUE, COLOR_BOLDMAGENTA, COLOR_BOLDCYAN};

#define NDEBUG

#ifndef NDEBUG
#include <fstream>
#include <cstring>
struct MemChecker {
  ~MemChecker() {
    std::ifstream infile("/proc/self/status");
    std::string line;
    while (std::getline(infile, line)) {
      if (line.compare(0, 6, "VmPeak") == 0) {
        int rv = 0;
        for (int i = 0; i < line.size(); ++i) {
          if (line[i] >= '0' && line[i] <= '9') {
            rv = 10 * rv + (line[i] - '0');
          }
        }
        std::cerr << "memory: " << rv << " kB" << std::endl;
        return;
      }
    }
    std::cerr << "memory stats not found" << std::endl;
  }
} __mem_checker;

#define cdebug \
  cerr << colors[std::hash<std::string>()(std::string(__func__)) % colors.size()] << __func__ << COLOR_RESET << ":" << __LINE__ << ": "

#else

class DebugStream {};
template <typename T>
DebugStream& operator<<(DebugStream& s, T) {
  return s;
}

DebugStream cdebug;

#endif

constexpr int MAXN = 500010;
constexpr int INF = 2000000000;
int N;
vector<int> neis[MAXN];
vector<int> results;
vector<int> can_appends;
int in_time[MAXN];
int out_time[MAXN];
int depth[MAXN];
int low[MAXN];
int high[MAXN];
int Time = 1;
int EraStart = 1;

void read_data() {
  int m;
  scanf("%d%d", &N, &m);
  while (m--) {
    int a, b;
    scanf("%d%d", &a, &b);
    neis[a - 1].push_back(b - 1);
  }
  fill(low, low + N, -1);
  fill(high, high + N, MAXN);
}

// @param can_append if you can append to "results" (i.e. if a cycle has been found)
bool dfs(const int node, const bool can_append) {
  cdebug << "dfs(" << node << " [" << depth[node] << "], " << can_append << ") Time = " << Time << "\n";
  in_time[node] = Time++;
  if (can_append) {
    can_appends.push_back(node);
  }
  bool my_rv = false;
  for (const auto nei : neis[node]) {
    cdebug << "[" << node << "] " << COLOR_BOLDRED << "nei " << nei << COLOR_RESET << "\n";
    if (out_time[nei] > 0 && out_time[nei] < EraStart) {
      cdebug << "[" << node << "] nei " << nei << " WRONG ERA\n";
      continue;
    }
    int remove_depth = -1;
    if (in_time[nei] == 0) {
      // tree edge; new node; out_time == 0
      depth[nei] = depth[node] + 1;
      bool rv = dfs(nei, can_append && low[node] == -1);
      low[node] = max(low[node], low[nei]);
      high[node] = min(high[node], high[nei]);
      my_rv = my_rv || rv;
      if (rv && low[nei] > depth[node] && !can_append) {
        // found a cycle below, when there was already a cycle somewhere else
        // the result will be zero, period.
        cdebug << "cycle below detected when can_append == false, clearing and exiting\n";
        results.clear();
        break;
      }
      cdebug << "[" << node << "] updated lo hi to " << low[node] << " " << high[node] << "\n";
    } else if (out_time[nei] == 0) {
      // up edge
      low[node] = max(low[node], depth[nei]);
      high[node] = min(high[node], depth[nei]);
      cdebug << "[" << node << "] UP EDGE updated lo hi to " << low[node] << " " << high[node] << "\n";
      // remove everything
      results.clear();
      my_rv = true;
      cdebug << "[" << node << "] removd ALL\n";
    } else if (out_time[nei] < in_time[node]) {
      // skew edge
      low[node] = max(low[node], low[nei]);
      high[node] = min(high[node], high[nei]);
      cdebug << "[" << node << "] SKEW EDGE updated lo hi to " << low[node] << " " << high[node] << "\n";
      cdebug << "    can appends back: " << can_appends.back() << "\n";
      // remove everything in the results above level depth[nei] it it reaches above their
      // lca (last node with can_append is sufficient)
      if (high[nei] <= depth[can_appends.back()]) {
        remove_depth = depth[nei];
      }
    } else {
      // down_edge
      cdebug << "[" << node << "] DOWN EDGE low[nei] = " << low[nei] << " high[nei] = " << high[nei] << "\n";
      if (high[nei] <= depth[node] && can_append) {
        remove_depth = depth[nei];
      }
    }
    cdebug << "[" << node << "] REMOVING " << remove_depth << "\n";
    while (!results.empty() && depth[results.back()] < remove_depth) {
      cdebug << "[" << node << "] removing  " << results.back() << "\n";
      results.pop_back();
    }
    cdebug << "[" << node << "] REMOVEDDDDDD\n";
  }
  cdebug << "[" << node << "] end rv = " << low[node] << " " << high[node] << " low " << low[node] << " out Time " << Time << "\n";
  if (low[node] != -1 && low[node] <= depth[node] && can_append) {
    cdebug << "[" << node << "] appending\n";
    results.push_back(node);
  }
  out_time[node] = Time++;
  if (can_appends.back() == node) {
    can_appends.pop_back();
  }
  return my_rv;
}


bool find_cycles() {
  bool cycle_found = false;
  for (int i = 0; i < N; ++i) {
    if (in_time[i] > 0) {
      continue;
    }
    depth[i] = 1;
    EraStart = Time++;
    if (dfs(i, !cycle_found)) {
      if (cycle_found) {
        // cycles in different components
        results.clear();
        return true;
      } else {
        cycle_found = true;
      }
    }
  }
  return cycle_found;
}

int main() {
  cerr.setf(ios::boolalpha);
  read_data();

  if (find_cycles()) {
    sort(results.begin(), results.end());
    printf("%d\n", results.size());
    for (int r : results) {
      printf("%d ", r + 1);
    }
    if (!results.empty()) {
      printf("\n");
    }
  } else {
    printf("NIE\n");
  }
}