#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
multiset<int> link[100002], revLink[100002];
bool removeUselessVertices();
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V){
n = N, m = M;
for(int i=0; i<m; i++){
link[U[i]].insert(V[i]);
revLink[V[i]].insert(U[i]);
}
if(removeUselessVertices()) return false;
return true;
}
int deg[100002];
bool removed[100002];
bool seenAsStart[100002];
int s = 0;
vector<int> startList;
bool removeUselessVertices(){
/// outdegree 0 삭제
queue<int> que;
for(int i=0; i<n; i++){
deg[i] = (int)link[i].size();
if(!deg[i] && !removed[i]) removed[i] = 1, que.push(i);
}
while(deg[s] == 1){
for(auto y: revLink[s]){
link[y].erase(link[y].find(s));
deg[y]--;
if(!deg[y] && !removed[y]) removed[y] = 1, que.push(y);
}
revLink[s].clear();
startList.push_back(s);
s = *link[s].begin();
}
while(!que.empty()){
int x = que.front(); que.pop();
deg[x] = 0;
for(auto y: revLink[x]){
deg[y]--;
link[y].erase(link[y].find(x));
if(!deg[y] && !removed[y]) removed[y] = 1, que.push(y);
while(deg[s] == 1){
for(auto y: revLink[s]){
link[y].erase(link[y].find(s));
deg[y]--;
if(!deg[y] && !removed[y]) removed[y] = 1, que.push(y);
}
revLink[s].clear();
startList.push_back(s);
s = *link[s].begin();
}
}
}
if(removed[s]) return true;
return false;
}
