#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
multiset<ll>g[100007],g2[100007];
map<pair<ll,ll>,vector<ll>>v;
bool odw[100007];
ll pop=-1;
queue<pair<ll,ll>>q;
void upd(){
while(q.size()){
auto pom=q.front();
//cout<<pom.ff<<" "<<pom.ss<<"\n";
v[pom].pop_back();
q.pop();
g[pom.ff].erase(g[pom.ff].lower_bound(pom.ss));
g2[pom.ss].erase(g2[pom.ss].lower_bound(pom.ff));
if(g[pom.ff].empty())for(ll j : g2[pom.ff])q.push({j,pom.ff});
}
}
vector<ll>cycle(ll x,bool bl){
for(ll i=0;i<100007;i++)odw[i]=0;
vector<ll>ans,ak;
vector<pair<ll,ll>>vp;
while(!odw[x]){
//cout<<x<<" ";
ak.pb(x);
ll nxt;
nxt=*g[x].begin();
if(pop==v[{x,nxt}].back()){//cout<<"xd";
nxt=*--g[x].end();}
ans.pb(v[{x,nxt}].back());
pop=ans.back();
vp.pb({x,nxt});
odw[x]=1;
x=nxt;
}
// cout<<"xd"<<flush;
ak.pb(-1);
ll pom=ak.size()-1;
while(x!=ak.back()){
ak.pop_back();
pom--;
auto a=vp[pom];
//cout<<a.ff<<" "<<a.ss<<"\n";
g[a.ff].erase(g[a.ff].find(a.ss));
g[a.ss].insert(a.ff);
v[{a.ss,a.ff}].pb(v[{a.ff,a.ss}].back());
v[{a.ff,a.ss}].pop_back();
}
while(pom){
pom--;
ans.pb(ans[pom]);
}
//for(ll i : ans)cout<<i<<" ";
//cout<<"\n"<<flush;
pop=ans.back();
return ans;
}
variant<bool,vector<int>>find_journey(int n,int m,vector<int>u,vector<int>w){
for(ll i=0;i<m;i++){
g[u[i]].insert(w[i]);
g2[w[i]].insert(u[i]);
v[{u[i],w[i]}].pb(i);
}
for(ll i=0;i<n;i++){
if(g[i].empty())for(ll j : g2[i])q.push({j,i});
}
upd();
vector<int>ans,ans2;
ll ak=0;
//cout<<"xd";
while(1){
if(g[ak].empty())return false;
else if(g[ak].size()==1){
q.push({ak,*g[ak].begin()});
ans.pb(v[{ak,*g[ak].begin()}].back());
ans2.pb(v[{ak,*g[ak].begin()}].back());
ak=*g[ak].begin();
upd();
}
else{
auto v1=cycle(ak,0);
auto v2=cycle(ak,1);
for(ll i : v1)ans.pb(i);
for(ll i : v2)ans.pb(i);
v1=cycle(ak,0);
v2=cycle(ak,1);
for(ll i : v1)ans.pb(i);
for(ll i : v2)ans.pb(i);
while(ans2.size()){
ans.pb(ans2.back());
ans2.pop_back();
}
return ans;
}
}
}
