#include<bits/stdc++.h>
//#include <variant>
#define MAXN 200007
using namespace std;
int n,m,root,banned;
vector< pair<int,int> > v[MAXN];
vector<int> path,sol,z;
int ind[MAXN];
void euler(int x,int e){
for(int i=ind[x];i<v[x].size();i++){
ind[x]++;
if(v[x][i].first==banned)continue;
euler(v[x][i].first,v[x][i].second);
i=max(i,ind[x]-1);
}
path.push_back(e);
}
int dfs(int x,int p){
if(x==1 and p!=0)return 0;
if(v[x].size()>2 or (p==0 and v[x].size()>1)){
banned=p;
return x;
}
for(int i=0;i<v[x].size();i++){
if(v[x][i].first!=p){
z.push_back(v[x][i].second);
return dfs(v[x][i].first,x);
}
}
return -1;
}
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++){
U[i]++; V[i]++;
v[U[i]].push_back({V[i],i});
}
root=dfs(1,0);
if(root==-1)return {-1};
if(root==0){
for(int i:z)sol.push_back(i);
return sol;
}
for(int i:z)sol.push_back(i);
euler(root,-1);
path.pop_back();
reverse(path.begin(),path.end());
for(int i=0;i<path.size();i++){
sol.push_back(path[i]);
}
for(int i=1;i<=n;i++){
v[i].clear(); ind[i]=0;
}
path.clear();
for(int i=m-1;i>=0;i--){
v[V[i]].push_back({U[i],i});
}
euler(root,-1);
path.pop_back();
reverse(path.begin(),path.end());
for(int i=0;i<path.size();i++){
sol.push_back(path[i]);
}
for(int i=z.size()-1;i>=0;i--){
sol.push_back(z[i]);
}
if(sol.empty())return {-1};
return sol;
}
/*
int main(){
find_journey(6, 7, {0,1,2,2,3,4,5}, {1,2,3,5,4,2,0});
}
*/
