#include <bits/stdc++.h>
#include <variant>
using namespace std;
const int maxn = 10, logm = 4;
vector<int> adjlist[maxn];
vector<int> down[maxn], up[maxn];
pair<int, int> arrpii[maxn];
int state[maxn], disc[maxn], depth[maxn];
vector<int> side, extra;
int lca[logm][maxn];
int tim = 0, dep = 0;
void dfs(int cur) {
state[cur] = 1;
disc[cur] = tim++;
depth[cur] = dep;
for (auto a : adjlist[cur])
if (state[arrpii[a].second] == 1)
up[cur].push_back(a);
else if (state[arrpii[a].second] == 0) {
lca[0][arrpii[a].second] = cur;
down[cur].push_back(a);
dep++;
dfs(arrpii[a].second);
dep--;
}
else if (disc[arrpii[a].second] > disc[cur])
extra.push_back(a);
else
side.push_back(a);
state[cur] = 2;
}
struct cmp
{
bool operator()(int a, int b) const {
return disc[a] > disc[b];
}
};
using sidcp = set<int, cmp>*;
vector<int> cyc[maxn];
int highdisc[maxn];
sidcp dfs2(int cur) {
highdisc[cur] = -1;
vector<sidcp> vsd;
for (auto a : down[cur]) {
vsd.push_back(dfs2(arrpii[a].second));
auto it = vsd.back()->find(cur);
if (vsd.back()->count(cur)) {
highdisc[cur] = cur;
vsd.back()->erase(cur);
cyc[cur].push_back(a);
}
}
sidcp maxi = new set<int, cmp>;
if (!vsd.empty())
maxi = *max_element(vsd.begin(), vsd.end(),
[](sidcp a, sidcp b) { return a->size() < b->size(); });
for (auto a : vsd)
if (a != maxi)
for (auto b : *a) maxi->insert(b);
for (auto a : up[cur]) maxi->insert(arrpii[a].second);
if (!maxi->empty()) highdisc[cur] = *maxi->begin();
return maxi;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U,
vector<int> V) {
for (int i = 0; i < M; i++) {
arrpii[i] = { U[i], V[i] };
adjlist[U[i]].push_back(i);
}
dfs(0);
dfs2(0);
lca[0][0] = 0;
for (int i = 1; i < logm; i++)
for (int j = 0; j < N; j++) lca[i][j] = lca[i - 1][lca[i - 1][j]];
for (auto a : extra) {
pair<int, int> pii = arrpii[a];
if (highdisc[pii.second] != -1)
if (disc[highdisc[pii.second]] >= disc[pii.first]) {
return true;
// good
}
}
for (auto a : side) {
pair<int, int> pii = arrpii[a];
if (highdisc[pii.second] != -1) {
int lci;
int tmpa = pii.first, tmpb = pii.second;
if (depth[tmpa] < depth[tmpb]) {
for (int i = logm - 1; i >= 0; i--)
if ((1 << i) & (depth[tmpb] - depth[tmpa])) tmpb = lca[i][tmpb];
}
else if (depth[tmpa] > depth[tmpb]) {
for (int i = logm - 1; i >= 0; i--)
if ((1 << i) & (depth[tmpa] - depth[tmpb])) tmpa = lca[i][tmpa];
}
for (int i = logm - 1; i >= 0; i--)
if (lca[i][tmpa] != lca[i][tmpb]) {
tmpa = lca[i][tmpa], tmpb = lca[i][tmpb];
}
if (tmpa != tmpb) {
tmpa = lca[0][tmpa], tmpb = lca[0][tmpb];
}
lci = tmpa;
if (disc[lci] <= disc[highdisc[pii.second]]) return true;
}
}
for (int i = 0; i < N; i++)
if (cyc[i].size() >= 2) return true;
return false;
}
// int main() {
// int N, M;
// assert(2 == scanf("%d %d", &N, &M));
// std::vector<int> U(M), V(M);
// for (int i = 0; i < M; ++i) {
// assert(2 == scanf("%d %d", &U[i], &V[i]));
// }
// std::variant<bool, std::vector<int>> result = find_journey(N, M, U, V);
// if (result.index() == 0) {
// printf("0\n");
// if (std::get<bool>(result)) {
// printf("1\n");
// }
// else {
// printf("0\n");
// }
// }
// else {
// printf("1\n");
// std::vector<int>& canoes = std::get<std::vector<int>>(result);
// printf("%d\n", static_cast<int>(canoes.size()));
// for (int i = 0; i < static_cast<int>(canoes.size()); ++i) {
// if (i > 0) {
// printf(" ");
// }
// printf("%d", canoes[i]);
// }
// printf("\n");
// }
// return 0;
// }
