#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void add(vector<int> &A, vector<int> &B, int rev = 0){
if(!rev) for(auto x: B) A.push_back(x);
else for(int i=(int)B.size()-1; i>=0; i--) A.push_back(B[i]);
}
int n, m;
multiset<int> link[100002], revLink[100002];
bool removeUselessVertices();
vector<int> solve();
multimap<pair<int, int>, int> edgeMap;
multimap<pair<int, int>, int> edgeMap2;
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;
vector<int> ret;
vector<int> ans = solve();
for(int i=0; i<m; i++) edgeMap.insert(make_pair(make_pair(U[i], V[i]), i));
for(int i=0; i<(int)ans.size()-1; i++){
int x = ans[i], y = ans[i+1];
auto it = edgeMap2.find(make_pair(x, y));
if(it != edgeMap2.end() && it->first == make_pair(x, y) &&
(!(!ret.empty() && ret.back() == it->second) ||
(next(it) != edgeMap2.end() && next(it)->first == make_pair(x, y)))){
if(!ret.empty() && ret.back() == it->second) ++it;
ret.push_back(it->second);
edgeMap2.erase(it);
edgeMap.insert(make_pair(make_pair(y, x), ret.back()));
}
else{
it = edgeMap.find(make_pair(x, y));
if(!ret.empty() && ret.back() == it->second) ++it;
ret.push_back(it->second);
edgeMap.erase(it);
edgeMap2.insert(make_pair(make_pair(y, x), ret.back()));
}
}
return ret;
}
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);
int ns = *link[s].begin();
link[s].erase(link[s].find(ns));
revLink[ns].erase(revLink[ns].find(s));
s = ns;
}
while(!que.empty()){
int x = que.front(); que.pop();
deg[x] = 0;
if(x==s) return 1;
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);
int ns = *link[s].begin();
link[s].erase(link[s].find(ns));
revLink[ns].erase(revLink[ns].find(s));
s = ns;
if(removed[ns]) return 1;
}
}
}
if(removed[s]) return true;
return false;
}
int A = -1, B = -1;
bool visited[100002];
bool visitedinA[100002];
bool search_mode = 0;
bool search_overlap = 0;
void justSearch(int x){
visited[x] = 1;
if(search_mode == 0 && x != s) visitedinA[x] = 1;
for(auto y: link[x]){
if(x==s && y!=A && y!=B) continue;
if(x==s && y==B) search_mode = 1;
if(visited[y]){
if(search_mode && visitedinA[y]) search_overlap = 1;
continue;
}
justSearch(y);
}
}
vector<int> rec;
bool findCycle(int x, int lead, vector<int> &path, vector<int> &cycle, bool ina=0){
if(x==s) rec.clear();
visited[x] = 1;
rec.push_back(x);
for(auto y: link[x]){
if(x==s && y!=lead) continue;
if(visited[y]){
if(!ina || (y==0 && visitedinA[x]) || visitedinA[y]){
int c = find(rec.begin(), rec.end(), y) - rec.begin();
for(int i=0; i<=c; i++) path.push_back(rec[i]);
for(int i=c+1; i<(int)rec.size(); i++) cycle.push_back(rec[i]);
return true;
}
continue;
}
if(findCycle(y, lead, path, cycle, ina)) return true;
}
rec.pop_back();
return false;
}
bool inCycle[100002];
vector<int> record;
bool findInCycle(int x, int lead, vector<int> &path){
visited[x] = 1;
record.push_back(x);
for(auto y: link[x]){
if(x==s && y!=lead) continue;
if(inCycle[y] && y!=s){
for(auto z: record){
path.push_back(z);
}
path.push_back(y);
return true;
}
if(visited[y]) continue;
if(findInCycle(y, lead, path)) return true;
}
record.pop_back();
return false;
}
vector<int> solve(){
vector<int> ret;
if((int)link[s].size() <= 1) exit(1);
assert((int)link[s].size() > 1);
A = *link[s].begin();
B = *next(link[s].begin());
justSearch(s);
/// Case 2. A=B
if(A==B){
vector<int> pathA, cycleA;
memset(visited, 0, sizeof(visited));
findCycle(s, A, pathA, cycleA);
cycleA.insert(cycleA.begin(), pathA.back());
pathA.pop_back();
if(find(cycleA.begin(), cycleA.end(), s) == cycleA.end()){ /// 시작점이 포함되지 않음
int c = cycleA[0];
add(ret, startList);
add(ret, pathA); add(ret, cycleA); ret.push_back(c); add(ret, pathA, 1); ret.pop_back();
add(ret, pathA); ret.push_back(c); add(ret, cycleA, 1); add(ret, pathA, 1);
add(ret, startList, 1);
return ret;
}
else{
add(ret, startList);
add(ret, pathA); add(ret, cycleA);
ret.push_back(s);
int idx = find(cycleA.begin(), cycleA.end(), B) - cycleA.begin();
for(int i=idx; i>=0; i--) ret.push_back(cycleA[i]);
for(int i=(int)cycleA.size()-1; i>=idx; i--) ret.push_back(cycleA[i]);
ret.push_back(s);
add(ret, startList, 1);
return ret;
}
}
/// Case 1. A -> B의 경로가 없다
if(!visitedinA[B] && !search_overlap){
/// 각각 사이클 찾기
vector<int> pathA, cycleA, pathB, cycleB;
memset(visited, 0, sizeof(visited));
findCycle(s, A, pathA, cycleA);
memset(visited, 0, sizeof(visited));
findCycle(s, B, pathB, cycleB);
add(ret, startList);
add(ret, pathA);
add(ret, cycleA);
add(ret, pathA, 1);
ret.pop_back();
add(ret, pathB);
add(ret, cycleB);
add(ret, pathB, 1);
ret.pop_back();
add(ret, pathA);
add(ret, cycleA, 1);
add(ret, pathA, 1);
ret.pop_back();
add(ret, pathB);
add(ret, cycleB, 1);
add(ret, pathB, 1);
add(ret, startList, 1);
return ret;
}
/// Case 3. A->B의 경로가 있다
vector<int> pathB, cycleB;
memset(visited, 0, sizeof(visited));
findCycle(s, B, pathB, cycleB, 1);
cycleB.insert(cycleB.begin(), pathB.back());
pathB.pop_back();
if(find(cycleB.begin(), cycleB.end(), s) == cycleB.end()){ /// 시작점이 포함되지 않은 사이클
for(auto x: cycleB) inCycle[x] = 1;
add(ret, startList);
add(ret, pathB);
add(ret, cycleB);
ret.push_back(cycleB[0]);
add(ret, pathB, 1);
vector<int> pathA;
memset(visited, 0, sizeof(visited));
findInCycle(s, A, pathA);
int c = pathA.back();
pathA.pop_back();
ret.pop_back();
add(ret, pathA);
int idx = find(cycleB.begin(), cycleB.end(), c) - cycleB.begin();
for(int i=idx; i>=0; i--) ret.push_back(cycleB[i]);
for(int i=(int)cycleB.size()-1; i>=idx; i--) ret.push_back(cycleB[i]);
add(ret, pathA, 1);
add(ret, startList, 1);
return ret;
}
/// 시작점이 포함된 사이클
for(auto x: cycleB) inCycle[x] = 1;
add(ret, startList);
add(ret, cycleB);
vector<int> pathA;
memset(visited, 0, sizeof(visited));
findInCycle(s, A, pathA);
int c = pathA.back();
pathA.pop_back();
add(ret, pathA);
int idx = find(cycleB.begin(), cycleB.end(), c) - cycleB.begin();
for(int i=idx; i>=0; i--) ret.push_back(cycleB[i]);
for(int i=(int)cycleB.size()-1; i>=idx; i--) ret.push_back(cycleB[i]);
add(ret, pathA, 1);
add(ret, startList, 1);
return ret;
}
