// Sortare topologica BFS
// #include <iostream>
// #include <vector>
// #include <queue>
// #include <fstream>
//
// using namespace std;
// ifstream in("sortaret.in");
// ofstream out("sortaret.out");
// vector <int> vecini[50001];
// int f[50001], n,m,x,y;
// queue <int> q;
// vector <int> rezultat;
// void bfs() {
// while (!q.empty()) {
// int k = q.front();
// q.pop();
// for (auto v : vecini[k]) {
// f[v]--;
// if (f[v] == 0) {
// q.push(v);
// rezultat.push_back(v);
// }
// }
// }
// if (rezultat.size() == n) {
// for (int i = 0 ; i < rezultat.size() ; i++) {
// out << rezultat[i] << " ";
//
// }
// }
//
// }
// int main() {
// in>>n>>m;
// for (int i = 0 ; i<m ; i++) {
// in>>x>>y;
// vecini[x].push_back(y);
// f[y] ++;
//
// }
// for (int i = 1; i <= n ;i ++)
// if (f[i] == 0) {
// rezultat.push_back(i);
// q.push(i);
// }
// bfs();
// }
// Algoritm muchii critice
// #include <bits/stdc++.h>
//
// using namespace std;
// int a[101][101],viz[101],n,nivel[101], niv_min[101];
// set<int> vecini[100];
//
// void dfs(int nod) {
// viz[nod]=1;
// niv_min[nod]=nivel[nod];
// for (auto y : vecini[nod]) {
// if (viz[y]==0) {
// nivel[y]=nivel[nod]+1;
// dfs(y);
//
// niv_min[nod]=min(niv_min[nod],niv_min[y]);
//
// if (niv_min[y] > nivel[nod])
// cout<<nod<<" "<<y<<endl;
// }
// else {
// if (nivel[y] < nivel[nod] - 1) {
// niv_min[nod]=min(niv_min[nod],nivel[y]);
// }
// }
// }
// }
//
// int main() {
// int n,m,x,y;
// cin>>n>>m;
// for (int i=1;i<=m;i++) {
// cin>>x>>y;
// vecini[x].insert(y);
// vecini[y].insert(x);
// }
// dfs(1);
//
// }
// Alg Pct. critice
// #include <bits/stdc++.h>
//
// using namespace std;
// int a[101][101],viz[101],n,nivel[101], niv_min[101];
// set<int> vecini[100];
//
// void dfs(int nod) {
// viz[nod]=1;
// niv_min[nod]=nivel[nod];
// for (auto y : vecini[nod]) {
// if (viz[y]==0) {
// nivel[y]=nivel[nod]+1;
// dfs(y);
//
// niv_min[nod]=min(niv_min[nod],niv_min[y]);
//
// if (niv_min[y] >= nivel[nod])
// cout<<nod<<" ";
// }
// else {
// if (nivel[y] < nivel[nod] - 1) {
// niv_min[nod]=min(niv_min[nod],nivel[y]);
// }
// }
// }
// }
//
// int main() {
// int n,m,x,y;
// cin>>n>>m;
// for (int i=1;i<=m;i++) {
// cin>>x>>y;
// vecini[x].insert(y);
// vecini[y].insert(x);
// }
// dfs(1);
//
// }
// Alg. Kosaraju
// #include <bits/stdc++.h>
//
// using namespace std;
// vector <int> v;
// int n,a[101][101],viz[101],a1[101][101];
// int viz2[101];
// set<int> s;
//
// void dfs(int nod) {
// viz[nod]=1;
// v.push_back(nod);
// for (int i=1;i<=n;i++) {
// if (a[nod][i]==1 and viz[i]==0)
// dfs(i);
// }
// }
//
// void dfs2(int nod) {
// viz2[nod]=1;
// cout<<nod<<" ";
// for (int i=1;i<=n;i++) {
// if (a1[nod][i]==1 and viz2[i]==0) {
// dfs2(i);
// }
// }
// }
//
// int main() {
// int m,x,y;
// cin>>n>>m;
// for(int i=1;i<=m;i++) {
// cin>>x>>y;
// a[x][y]=1;
// a1[y][x]=1;
// }
// for (int i=1;i<=n;i++) {
// if (viz[i]==0) {
// dfs(i);
// }
// }
// for (int i=0; i<v.size(); i++) {
// if (viz2[v[i]]==0) {
// dfs2(v[i]);
// }
// cout<<endl;
// }
// return 0;
// }
// Alg. lui Prim
// #include <bits/stdc++.h>
// using namespace std;
//
// ifstream fin("apm.in");
// ofstream fout("apm.out");
//
// priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // (w, u)
// set<pair<int, int>> vecini[200001]; // (u, c)
// int n,m,x,y,c, d[200001], tata[200001], viz[200001];
// const int INF = 1e9;
//
// void prim(int nod) {
// for (int i=1;i<=n;i++) {
// d[i]=INF;
// tata[i]=0;
// }
// d[nod] = 0;
// pq.push(make_pair(0,nod));
//
// int luate = 0;
// long long cost_total = 0;
//
// while (!pq.empty() and luate < n) {
// int u = pq.top().second;
// int cost = pq.top().first;
// pq.pop();
//
// if (viz[u]) continue;
// if (cost != d[u]) continue;
//
// viz[u] = 1;
// luate++;
// cost_total += cost;
//
// for (auto it : vecini[u]) {
// int v = it.first;
// int w = it.second;
// if (!viz[v] && w < d[v]) {
// d[v] = w;
// tata[v] = u;
// pq.push(make_pair(w,v));
// }
// }
// }
// for (int i=1; i<=n ;i++) {
// if (d[i] == INF) {
// fout<<"Graful nu este conex";
// return;
// }
// }
// fout<<cost_total<<endl;
// int cnt=0;
// for (int i=1; i<=n; i++) {
// if (i!=nod)
// cnt++;
// }
// fout<<cnt<<endl;
// for (int i=1; i<=n; i++) {
// if (i!=nod)
// fout<<tata[i]<<" "<<i<<endl;
// }
// }
//
// int main() {
// fin>>n>>m;
// for (int i=1;i<=m;i++) {
// fin>>x>>y>>c;
// vecini[x].insert({y, c});
// vecini[y].insert({x, c});
// }
// prim(1);
// return 0;
// }
// Alg. lui Dijkstra
// #include <bits/stdc++.h>
// using namespace std;
//
// ifstream fin("dijkstra.in");
// ofstream fout("dijkstra.out");
//
// priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // (w, u)
// vector<pair<int, int>> vecini[50001]; // (u, c)
// int n,m,x,y,c, d[50001], tata[50001], viz[50001];
// const int INF = 1e9;
//
// void dijkstra(int nod) {
// for (int i=1;i<=n;i++) {
// d[i]=INF;
// tata[i]=0;
// viz[i]=0;
// }
// while(!pq.empty()) pq.pop();
// d[nod] = 0;
// pq.push(make_pair(0,nod));
//
// int luate = 0;
// long long cost_total = 0;
//
// while (!pq.empty() and luate < n) {
// int u = pq.top().second;
// int cost = pq.top().first;
// pq.pop();
//
// if (viz[u]) continue;
// if (cost != d[u]) continue;
//
// viz[u] = 1;
// luate++;
// cost_total += cost;
//
// for (auto it : vecini[u]) {
// int v = it.first;
// int w = it.second;
// if (!viz[v] and w + d[u] < d[v]) {
// d[v] = w + d[u];
// tata[v] = u;
// pq.push(make_pair(d[v],v));
// }
// }
// }
// for (int i=1;i<=n;i++) {
// if (d[i] == INF) {
// fout<<0<<" ";
// }
// else if (i!=1 and d[i] != INF){
// fout<<d[i]<<" ";
// }
// }
// }
//
// int main() {
// fin>>n>>m;
// for (int i=1;i<=m;i++) {
// fin>>x>>y>>c;
// vecini[x].push_back({y, c});
// }
// dijkstra(1);
// return 0;
// }
//Pb comp biconexe
// #include <bits/stdc++.h>
//
// using namespace std;
//
// ifstream fin("componentebiconexe.in");
// ofstream fout("componentebiconexe.out");
//
// int n, m, x, y, nivel[100001], niv_min[100001], viz[100001];
// set<int> vecini[100001];
// vector<pair<int,int>> rez1;
// set<int> rez2;
// stack<pair<int, int>> s;
// vector<vector<int>> rez;
//
// void muchii(int nod) {
// viz[nod]=1;
// niv_min[nod]=nivel[nod];
// for (auto i : vecini[nod]) {
// if (viz[i] == 0) {
// nivel[i]=nivel[nod]+1;
// muchii(i);
//
// niv_min[nod]=min(niv_min[i], niv_min[nod]);
//
// if (niv_min[i] > nivel[nod])
// rez1.push_back(make_pair(i, nod));
// }
// else {
// if (nivel[i] < nivel[nod] - 1)
// niv_min[nod] = min(nivel[i], niv_min[nod]);
// }
// }
// }
//
// void extragere_comp(int u, int v) {
// set<int> noduri_unice;
// while(true){
// pair<int,int> pereche = s.top();
// s.pop();
// noduri_unice.insert(pereche.first);
// noduri_unice.insert(pereche.second);
//
// if(pereche.first == u && pereche.second == v){
// break;
// }
// }
// vector<int> componenta;
// for(auto& elem: noduri_unice)
// componenta.push_back(elem);
//
// rez.push_back(componenta);
// }
//
//
// void noduri(int nod) {
// viz[nod]=1;
// int cnt = 0;
// niv_min[nod]=nivel[nod];
// for (auto i : vecini[nod]) {
// if (viz[i] == 0) {
// nivel[i]=nivel[nod]+1;
// cnt++;
// s.push(make_pair(nod, i));
// noduri(i);
// niv_min[nod]=min(niv_min[i], niv_min[nod]);
//
// if (niv_min[i] >= nivel[nod] and nod != 1) {
// rez2.insert(nod);
// extragere_comp(nod, i);
// }
// if (cnt >= 2 and nod == 1) {
// rez2.insert(nod);
// extragere_comp(nod, i);
// }
// }
// else {
// if (nivel[i] < nivel[nod] - 1)
// niv_min[nod] = min(nivel[i], niv_min[nod]);
// }
// }
// }
//
//
//
// int main() {
// int p;
// fin>>p;
// fin>>n>>m;
// for (int i=1;i<=m;i++) {
// fin>>x>>y;
// vecini[x].insert(y);
// vecini[y].insert(x);
// }
// if (p==3) {
// muchii(1);
// fout<<rez1.size()<<endl;
// for (auto it : rez1)
// fout<<it.first<<" "<<it.second<<endl;
// }
// if (p==2) {
// noduri(1);
// fout<<rez2.size()<<endl;
// for (auto it : rez2)
// fout<<it<<" ";
// }
// if(p == 1){
// noduri(1);
// fout << rez.size() << '\n';
// for(int i=0; i< rez.size(); i++){
// fout << rez[i].size() << " ";
// for(auto& elem: rez[i]){
// fout << elem << " ";
// }
// fout << '\n';
// }
//
// }
// return 0;
// }
//
//Alg. lui Bellman Ford
// #include <bits/stdc++.h>
// using namespace std;
// set<pair<int, int>> vecini[50001];
// int n, m, c, x, y, d[50001], tata[50001];
//
// ifstream fin("bellmanford.in");
// ofstream fout("bellmanford.out");
//
// const int INF = 1e9;
//
// void bellman_ford(int nod) {
// for (int i=1;i<=n;i++) {
// d[i] = INF;
// tata[i] = 0;
// }
// d[nod] = 0;
// for (int i=1; i<=n-1; i++) {
// for (int j=1; j<=n; j++) {
// for (auto v : vecini[j]) {
// if (d[j] + v.second < d[v.first]) {
// d[v.first] = d[j] + v.second;
// tata[v.first] = j;
// }
// }
// }
// }
// for (int j=1; j<=n; j++) {
// for (auto v : vecini[j]) {
// if (d[j] + v.second < d[v.first]) {
// fout<<"Ciclu negativ!";
// return;
// }
// }
// }
// for (int i=2;i<=n;i++)
// fout<<d[i]<<" ";
// }
//
// int main() {
// fin>>n>>m;
// for (int i=1;i<=m;i++) {
// fin>>x>>y>>c;
// vecini[x].insert(make_pair(y,c));
// }
// bellman_ford(1);
// return 0;
// }
// Alg. lui Roy - Floyd
// #include <bits/stdc++.h>
// using namespace std;
//
// int n, d[257][257], p[257][257];
// ifstream fin("royfloyd.in");
// ofstream fout("royfloyd.out");
//
// void floyd() {
// for (int i=1;i<=n;i++) {
// for (int j=1;j<=n;j++) {
// if (d[i][j]==100000)
// p[i][j]=0;
// else if ( d[i][j]!= 100000 and i!=j)
// p[i][j]=i;
// else if (d[i][j]!= 100000 and i==j)
// p[i][j]=0;
// }
// }
// for (int k=1;k<=n;k++) {
// for (int i=1;i<=n;i++) {
// for (int j=1;j<=n;j++) {
// if (d[i][j] > d[i][k] + d[k][j]) {
// d[i][j]=d[i][k]+d[k][j];
// p[i][j]=p[k][j];
// }
// }
// }
// }
// }
//
// int main() {
// fin>>n;
// for (int i=1;i<=n;i++) {
// for (int j=1;j<=n;j++) {
// fin>>d[i][j];
// }
// }
// floyd();
// for (int i=1;i<=n;i++) {
// for (int j=1;j<=n;j++) {
// fout<<d[i][j]<<" ";
// }
// fout<<endl;
// }
// return 0;
// }
//Alg. lui Edmond
// #include <bits/stdc++.h>
//
// using namespace std;
//
// ifstream f("maxflow.in");
// ofstream g("maxflow.out");
//
// int n, m, capacitate[1001][1001], tata[1001];
// vector <int> vecini[1001];
//
// bool bfs (int s, int t)
// {
// memset(tata, -1, 4 * (n + 1));
// queue <int> q;
//
// tata[s] = 0;
// q.push(s);
//
// while (!q.empty())
// {
// int i = q.front();
// q.pop();
//
// for (auto j : vecini[i])
// if (tata[j] == -1 and capacitate[i][j] > 0)
// {
// tata[j] = i;
//
// if (j == t)
// return true;
//
// q.push(j);
// }
// }
// return false;
// }
//
// int EdmondsKarp (int s, int t)
// {
// int flux_maxim = 0;
//
// while (bfs(s, t))
// {
// int flux_curr = INT_MAX;
//
// for (int j = t; j != s; j = tata[j])
// {
// int i = tata[j];
// flux_curr = min(flux_curr, capacitate[i][j]);
// }
//
// for (int j = t; j != s; j = tata[j])
// {
// int i = tata[j];
// capacitate[i][j] -= flux_curr;
// capacitate[j][i] += flux_curr;
// }
//
// flux_maxim += flux_curr;
// }
//
// return flux_maxim;
// }
//
// int main()
// {
// f>>n>>m;
// for (int i=1; i<=m; i++)
// {
// int x, y, w;
// f>>x>>y>>w;
// vecini[x].push_back(y);
// vecini[y].push_back(x);
// capacitate[x][y] += w;
// }
//
// g<<EdmondsKarp(1, n);
// }
//Alg. lui Euler recursiv
// #include <bits/stdc++.h>
//
// using namespace std;
// ifstream fin("ciclueuler.in");
// ofstream fout("ciclueuler.out");
//
// int n, m, x, y;
// multiset<int> vecini[100001];
// vector<int> ciclu;
//
// void euler(int nod) {
// while (!vecini[nod].empty()) {
// int v = *vecini[nod].begin();
// vecini[nod].erase(vecini[nod].begin());
// auto it = vecini[v].find(nod);
// if (it != vecini[v].end()) {
// vecini[v].erase(it);
// }
// euler(v);
// }
// ciclu.push_back(nod);
// }
//
// int main() {
// fin>>n>>m;
// for (int i=1;i<=m;i++) {
// fin>>x>>y;
// vecini[x].insert(y);
// vecini[y].insert(x);
// }
// euler(1);
// for (int i = 0;i<ciclu.size()-1;i++) {
// fout<<ciclu[i]<<" ";
// }
// return 0;
// }
// Alg. lui Euler stiva
#include <fstream>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <stack>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int n,m,x,y;
int main(){
fin >> n >> m;
vector<vector<pair<int,int>>> adj(n+1);
vector<int> degree(n+1);
vector<int> used(m+1);
for(int i=0; i<m; i++){
fin >> x >> y;
degree[x]++;
degree[y]++;
adj[x].push_back(make_pair(y,i));
adj[y].push_back(make_pair(x,i));
}
for(int i=1; i<=n; i++){
if(degree[i] % 2 == 1){
fout << -1;
return 0;
}
}
stack<int> st;
vector<int> path;
st.push(1);
while(!st.empty()){
int nod = st.top();
while(!adj[nod].empty() && used[adj[nod].back().second] == 1){
adj[nod].pop_back();
}
if(!adj[nod].empty()){
auto [v, idxEdge] = adj[nod].back();
used[idxEdge] = 1;
st.push(v);
}
else{
path.push_back(nod);
st.pop();
}
}
for(int i = path.size()-1; i >= 1; i--){
fout<<path[i]<<" ";
}
return 0;
}
Craciunescu Cristian Alexandru CRACIUNESCUalex