//#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;
map<pair<ll,ll>,pair<ll,ll>>nx;
bool us[100007];
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;
bool bll=0;
nxt=*g[x].begin();
if(pop==v[{x,nxt}].back()){
//cout<<"xd";
nxt=*--g[x].end();
swap(v[{x,nxt}].back(),v[{x,nxt}][0]);
bll=1;
}
ans.pb(v[{x,nxt}].back());
pop=ans.back();
vp.pb({x,nxt});
odw[x]=1;
if(bl && us[v[{x,nxt}].back()]){
ll l=ans.size()-2;
pair<ll,ll> akk={x,nxt};
//akk={akk.ss,akk.ff};
pair<ll,ll> ak2=nx[akk];
//akk={akk.ss,akk.ff};
//ak2={ak2.ss,ak2.ff};
while(ak2!=akk){
vp.pb(ak2);//cout<<ak2.ff<<" "<<ak2.ss<<flush;
ans.pb(v[ak2].back());
//cout<<ak2.ff<<" "<<ak2.ss<<" "<<flush;
// ak2={ak2.ss,ak2.ff};
ak2=nx[ak2];
//ak2={ak2.ss,ak2.ff};
ak.pb(ak2.ff);
pop=ans.back();
}
while(l>=0){ans.pb(ans[l--]);pop=ans.back();}
ans.pb(-1);
return ans;
}
else{if(bll && bl)
swap(v[{x,nxt}].back(),v[{x,nxt}][0]);
x=nxt;
}
}
//cout<<"xd"<<flush;
ak.pb(-1);
ll pom=ak.size()-1;
vector<pair<pair<ll,ll>,ll>>vm;
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);
vm.pb({{a.ss,a.ff},v[{a.ff,a.ss}].back()});
v[{a.ff,a.ss}].pop_back();
}
for(auto i : vm)v[i.ff].pb(i.ss);//cout<<pom<<" ";
if(!bl)
for(ll i=0;i<vm.size();i++){us[v[vm[i].ff].back()]=1;nx[vm[i].ff]=vm[(i+vm.size()+1)%(vm.size())].ff;//cout<<vm[i].ff.ff<<" "<<vm[i].ff.ss<<"\n";
}
while(pom){
pom--;
ans.pb(ans[pom]);
}
//for(ll i : ans)cout<<i<<" ";
//cout<<"\n\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);
bool bl=0;
if(v2.back()==-1){
bl=1;
v2.pop_back();
}
for(ll i : v1)ans.pb(i);
for(ll i : v2)ans.pb(i);
if(bl){
while(ans2.size()){
ans.pb(ans2.back());
ans2.pop_back();
}
return ans;
}
return ans;
reverse(v1.begin(),v1.end());
reverse(v2.begin(),v2.end());
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;
}
}
}
