#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.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));
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);
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;
}
int A = -1, B = -1;
bool visited[100002];
void justSearch(int x){
visited[x] = 1;
for(auto y: link[x]){
if(x==s && y!=A) continue;
if(visited[y]) continue;
justSearch(y);
}
}
void findCycle(int x, int lead, vector<int> &path, vector<int> &cycle){
vector<int> record;
while(!visited[x]){
visited[x] = 1;
record.push_back(x);
if(x == 0) x = lead;
else x = *link[x].begin();
}
int c = find(record.begin(), record.end(), x) - record.begin();
for(int i=0; i<=c; i++) path.push_back(record[i]);
for(int i=c+1; i<(int)record.size(); i++) cycle.push_back(record[i]);
}
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==0 && y!=lead) continue;
if(inCycle[y]){
for(auto x: record) path.push_back(x);
path.push_back(y);
return true;
}
if(visited[y]) continue;
if(findInCycle(y, lead, path)) return true;
}
path.pop_back();
return false;
}
vector<int> solve(){
vector<int> ret;
assert((int)link[s].size() > 1);
A = *link[s].begin();
B = *next(link[s].begin());
justSearch(0);
/// Case 1. A -> B의 경로가 없다
if(!visited[B]){
/// 각각 사이클 찾기
vector<int> pathA, cycleA, pathB, cycleB;
memset(visited, 0, sizeof(visited));
findCycle(0, A, pathA, cycleA);
memset(visited, 0, sizeof(visited));
findCycle(0, 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 2. A=B
if(A==B){
vector<int> pathA, cycleA;
memset(visited, 0, sizeof(visited));
findCycle(0, A, pathA, cycleA);
cycleA.insert(cycleA.begin(), pathA.back());
pathA.pop_back();
if(find(cycleA.begin(), cycleA.end(), s) == cycleA.end()){ /// 시작점이 포함되지 않음
add(ret, startList);
add(ret, pathA); add(ret, cycleA); add(ret, pathA, 1); ret.pop_back();
add(ret, pathA); add(ret, cycleA, 1); add(ret, pathA, 1);
add(ret, startList);
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 3. A->B의 경로가 있다
vector<int> pathB, cycleB;
memset(visited, 0, sizeof(visited));
findCycle(0, B, pathB, cycleB);
if(find(cycleB.begin(), cycleB.end(), s) == cycleB.end()){ /// 시작점이 포함되지 않은 사이클
cycleB.insert(cycleB.begin(), pathB.back());
pathB.pop_back();
for(auto x: cycleB) inCycle[x] = 1;
add(ret, pathB);
add(ret, cycleB);
ret.push_back(cycleB[0]);
add(ret, pathB, 1);
vector<int> pathA;
memset(visited, 0, sizeof(visited));
findInCycle(0, 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;
}
return vector<int> (1);
}
