#include <bits/stdc++.h>
#include <variant>
#include <vector>
#define mp make_pair
#define pb push_back
#define pll pair<long long, long long>
#define MOD 1000002022ll
#define xx first
#define yy second
using namespace std;
typedef long long ll;
multiset<ll> to[100100], from[100100];
map<pll, vector<ll>> edgenames;
set<ll> obidjeni, ciklus, obidjeni2, ciklus2;
vector<int> braket;
ll root, sled[100100], pre[100100], sled2[100100], pre2[100100];
bool dead[100100];
string s;
void erase(ll cur) {
if(dead[cur]) return;
vector<ll> kill;
for(auto i:to[cur]) {
from[i].erase(from[i].find(cur));
if(i!=root&&from[i].empty()) kill.pb(i);
}
for(auto i:from[cur]) {
to[i].erase(to[i].find(cur));
if(to[i].empty()) kill.pb(i);
}
dead[cur]=true;
for(auto i:kill) erase(i);
}
void put(ll cur, ll pr) {
if(obidjeni.count(cur)) {
pre[cur]=pr;
while(pr!=cur) {
ciklus.insert(pr);
pr=pre[pr];
}
ciklus.insert(cur);
return;
}
pre[cur]=pr;
sled[cur]=*to[cur].begin();
obidjeni.insert(cur);
put(*to[cur].begin(), cur);
}
void drugiput(ll cur, ll pr) {
if(cur!=root&&ciklus.count(cur)) {
pre2[cur]=pr;
s="IstiCiklus";
return;
}
if(cur!=root&&obidjeni.count(cur)) {
pre2[cur]=pr;
s="IstiPut";
return;
}
if(obidjeni2.count(cur)) {
pre2[cur]=pr;
while(pr!=cur) {
ciklus2.insert(pr);
pr=pre2[pr];
}
ciklus2.insert(cur);
return;
}
pre2[cur]=pr;
obidjeni2.insert(cur);
if(cur==root) sled2[cur]=*next(to[cur].begin());
else sled2[cur]=*to[cur].begin();
if(cur==root) drugiput(*next(to[cur].begin()), cur);
else drugiput(*to[cur].begin(), cur);
}
vector<ll> veca, zapravo;
void ispisiput(ll cur) {
if(!ciklus.count(cur)) {
veca.pb(edgenames[mp(cur, sled[cur])][0]);
ispisiput(sled[cur]);
return;
}
zapravo=veca;
ll tr=cur;
zapravo.pb(edgenames[mp(tr, sled[tr])][0]);
tr=sled[tr];
while(tr!=cur) {
zapravo.pb(edgenames[mp(tr, sled[tr])][0]);
tr=sled[tr];
}
while(veca.size()) {
zapravo.pb(veca.back());
veca.pop_back();
}
}
void ispisiputnazad(ll cur) {
if(!ciklus.count(cur)) {
veca.pb(edgenames[mp(cur, sled[cur])][0]);
ispisiputnazad(sled[cur]);
return;
}
zapravo=veca;
ll tr=cur;
zapravo.pb(edgenames[mp(tr, pre[tr])][0]);
tr=pre[tr];
while(tr!=cur) {
zapravo.pb(edgenames[mp(tr, pre[tr])][0]);
tr=pre[tr];
}
while(veca.size()) {
zapravo.pb(veca.back());
veca.pop_back();
}
}
void ispisidrugiput(ll cur) {
if(!ciklus2.count(cur)) {
veca.pb(edgenames[mp(cur, sled2[cur])][0]);
ispisidrugiput(sled2[cur]);
return;
}
zapravo=veca;
ll tr=cur;
zapravo.pb(edgenames[mp(tr, sled2[tr])][0]);
tr=sled2[tr];
while(tr!=cur) {
zapravo.pb(edgenames[mp(tr, sled2[tr])][0]);
tr=sled2[tr];
}
while(veca.size()) {
zapravo.pb(veca.back());
veca.pop_back();
}
}
void ispisidrugiputnazad(ll cur) {
if(!ciklus2.count(cur)) {
veca.pb(edgenames[mp(cur, sled2[cur])][0]);
ispisidrugiputnazad(sled2[cur]);
return;
}
zapravo=veca;
ll tr=cur;
zapravo.pb(edgenames[mp(tr, pre2[tr])][0]);
tr=pre2[tr];
while(tr!=cur) {
zapravo.pb(edgenames[mp(tr, pre2[tr])][0]);
tr=pre2[tr];
}
while(veca.size()) {
zapravo.pb(veca.back());
veca.pop_back();
}
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
variant<bool, vector<int>> v;
for(int i=0; i<M; i++) {
to[U[i]].insert(V[i]);
from[V[i]].insert(U[i]);
edgenames[mp(U[i], V[i])].pb(i);
}
for(int i=0; i<N; i++) {
if(to[i].empty()||(i!=root&&from[i].empty())) erase(i);
}
if(dead[root]) {
v=false;
return v;
}
while(to[root].size()==1) {
ll t=root;
root=*to[root].begin();
braket.pb(edgenames[mp(t, root)][0]);
erase(t);
if(dead[root]) {
v=false;
return v;
}
}
v=true;
put(root, root);
drugiput(root, root);
if(s=="") {
vector<int> dobar;
dobar=braket;
ispisiput(root);
for(int i:zapravo) dobar.pb(i);
zapravo.clear();
ispisidrugiput(root);
for(int i:zapravo) dobar.pb(i);
zapravo.clear();
ispisiputnazad(root);
for(int i:zapravo) dobar.pb(i);
zapravo.clear();
ispisidrugiputnazad(root);
for(int i:zapravo) dobar.pb(i);
zapravo.clear();
while(braket.size()) {
dobar.pb(braket.back());
braket.pop_back();
}
v=braket;
}
return v;
}
