#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 1000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod = 1000000007 ;
const int mod1 = 998244353 ;
const int N = 4e5 + 10 ;
//mt19937 R(time(0));
map < string , int > ma , ma1 ;
#include <variant>
#include "islands.h"
vector < int > cur[ N ] , uu , vv , pas ;
vector < pair < int , int > > v ;
int n , m , been[ N ] ;
int pp[ N ] , us[ N ] ;
void make_path( int node , int par ){
int A = node ;
int B = vv[ cur[ node ][ 0 ] ] ;
if( B == par ) B = vv[ cur[ node ][ 1 ] ] ;
int D = vv[ cur[ node ] [ 0 ] ] + vv[ cur[ node ][ 1 ] ] + vv[ cur[ node ][ 2 ] ] ;
D = D - B - par ;
int a = -1 , b = -1 , c = -1 , d = -1 ;
FOR( i , m ){
if( a == -1 && uu[ i ] == A && vv[ i ] == B && us[ i ] == 0 ) a = i , us[ i ] = 1 ;
if( b == -1 && uu[ i ] == B && vv[ i ] == A && us[ i ] == 0 ) b = i , us[ i ] = 1 ;
if( c == -1 && uu[ i ] == A && vv[ i ] == D && us[ i ] == 0 ) c = i , us[ i ] = 1 ;
if( d == -1 && uu[ i ] == D && vv[ i ] == A && us[ i ] == 0 ) d = i , us[ i ] = 1 ;
}
if( a != -1 && b != -1 && c != -1 && d != -1 ){
pas.pb( a ) ;
pas.pb( b ) ;
pas.pb( c ) ;
pas.pb( d ) ;
pas.pb( b ) ;
pas.pb( a ) ;
pas.pb( d ) ;
pas.pb( c ) ;
}
}
int check(){
int tt = -1 ;
int node = 0 , par = -1 ;
while( true ){
pp[ node ] = par ;
been[ node ] = 1 ;
if( cur[ node ].size() == 1 && node != 0 ){
return -1 ;
}
if( cur[ node ].size() > 2 ){
vector < int > pip = pas ;
make_path( node , par ) ;
for( int j = pip.size() - 1 ; j >= 0 ; j -- ) pas.pb( pip[ j ] ) ;
return 1 ;
}
// finding next one and the path
int nx = vv[ cur[ node ][ 0 ] ] ;
if( par == nx ){
pas.pb( cur[ node ][ 1 ] ) ;
us[ cur[ node ][ 1 ] ] = 1 ;
nx = vv[ cur[ node ][ 1 ] ] ;
}
else pas.pb( cur[ node ][ 0 ] ) , us[ cur[ node ][ 0 ] ] = 1 ;
// if( been[ nx ] == 1 ){
// // find the cycle
// return 1 ;
// }
par = node ;
node = nx ;
}
return tt ;
}
int col[ N ] ;
int tita = 0 ;
int papiki[ N ] ;
vector < int > pth , axl ;
//int pp[ N ] ;
void make_cycle( int bg , int nd , int nmb ){
pas.clear() ;
int BG = bg ;
while( BG != 0 ){
axl.pb( papiki[ BG ] ) ;
BG = pp[ BG ] ;
}
// before cycle
reverse( axl.begin() , axl.end() ) ;
for( auto x : axl ) pas.pb( x ) ;
// now for cycle
pth.pb( nmb ) ;
int cur = nd ;
while( true ){
if( cur == -1 ) break ;
if( cur == bg ) break ;
pth.pb( papiki[ cur ] ) ;
cur = pp[ cur ] ;
}
reverse( pth.begin() , pth.end() ) ;
for( auto x : pth ) pas.pb( x ) ;
for( auto x : pth ){
pas.pb( x + 1 ) ;
}
reverse( pth.begin() , pth.end() ) ;
for( auto x : pth ) pas.pb( x ) ;
for( auto x : pth ){
pas.pb( x + 1 ) ;
}
// after cycle
reverse( axl.begin() , axl.end() ) ;
for( auto x : axl ) pas.pb( x ) ;
return ;
}
vector < int > vi ;
void dfs( int node , int parent , int piu ){
papiki[ node ] = piu ;
pp[ node ] = -1 ;
col[ node ] = 2 ;
if( tita == 1 ) return ;
for( auto X : cur[ node ] ){
int x = vv[ X ] ;
if( col[ x ] == 2 ){
tita = 1 ;
pas.pb( 1 ) ;
int nd = node ;
int zz = 0 ;
while( nd != -1 ){
nd = pp[ nd ] ;
vi.pb( 1 ) ;
}
// make_cycle( x , node , X ) ;
return ;
}
if( col[ x ] == 1 ) continue ;
dfs( x , node , X ) ;
}
col[ node ] = 1 ;
}
int check1(){
int tt = -1 ;
dfs( 0 , -1 , -1 ) ;
if( tita == 1 ) tt = 1 ;
return tt ;
}
variant<bool, vector<int>> find_journey( int N, int M, vector<int> U, vector<int> V){
uu = U ; vv = V ; n = N ; m = M ;
FOR( i , M ){
cur[ U[ i ] ].pb( i ) ;
v.pb( { U[ i ] , V[ i ] } ) ;
}
if( N == 2 ){
if( cur[ 0 ].size() < 2 || cur[ 1 ].size() < 1 ){
return false ;
}
vector < int > ans ;
ans.pb( cur[ 0 ][ 0 ] ) ;
ans.pb( cur[ 1 ][ 0 ] ) ;
ans.pb( cur[ 0 ][ 1 ] ) ;
ans.pb( cur[ 0 ][ 0 ] ) ;
ans.pb( cur[ 1 ][ 0 ] ) ;
ans.pb( cur[ 0 ][ 1 ] ) ;
return ans ;
}
if( cur[ 0 ].size() == 0 ) return false ;
int a = -1 , b = -1 , c = -1 , d = -1 ;
int cc1 = -1 , cc2 = -1 ;
cc1 = V[ cur[ 0 ][ 0 ] ] ;
if( cur[ 0 ].size() > 1 ){
cc2 = V[ cur[ 0 ][ 1 ] ] ;
}
FOR( i , M ){
if( a == -1 && uu[ i ] == 0 && vv[ i ] == cc1 && us[ i ] == 0 ) a = i , us[ i ] = 1 ;
if( b == -1 && uu[ i ] == cc1 && vv[ i ] == 0 && us[ i ] == 0 ) b = i , us[ i ] = 1 ;
if( c == -1 && uu[ i ] == 0 && vv[ i ] == cc2 && us[ i ] == 0 ) c = i , us[ i ] = 1 ;
if( d == -1 && uu[ i ] == cc2 && vv[ i ] == 0 && us[ i ] == 0 ) d = i , us[ i ] = 1 ;
}
if( a != -1 && b != -1 && c != -1 && d != -1 ){
vector < int > ans ;
ans.pb( a ) ;
ans.pb( b ) ;
ans.pb( c ) ;
ans.pb( d ) ;
ans.pb( b ) ;
ans.pb( a ) ;
ans.pb( d ) ;
ans.pb( c ) ;
return ans ;
}
int titu = 0 ;
if( m % 2 != 0 ) titu = -1 ;
for( int i = 0 ; i < m ; i += 2 ){
int cc = -1 ;
if( U[ i ] == V[ i + 1 ] && V[ i ] == U[ i + 1 ] ) cc = 0 ;
titu = min( titu , cc ) ;
}
if( titu == 0 ){
// subtask 3
// sheamowme prosta xazia tuara
int tt = check() ;
if( tt == -1 ) return false ;
return pas ; }
pas.clear() ;
int tt = check1() ;
if( tt == -1 ) return false ;
return pas ;
}
// int main() {
// int N, M;
// assert(2 == scanf("%d %d", &N, &M));
// std::vector<int> U(M), V(M);
// for (int i = 0; i < M; ++i) {
// assert(2 == scanf("%d %d", &U[i], &V[i]));
// }
// std::variant<bool, std::vector<int>> result = find_journey(N, M, U, V);
// if (result.index() == 0) {
// printf("0\n");
// if (std::get<bool>(result)) {
// printf("1\n");
// } else {
// printf("0\n");
// }
// } else {
// printf("1\n");
// std::vector<int> &canoes = std::get<std::vector<int>>(result);
// printf("%d\n", static_cast<int>(canoes.size()));
// for (int i = 0; i < static_cast<int>(canoes.size()); ++i) {
// if (i > 0) {
// printf(" ");
// }
// printf("%d", canoes[i]);
// }
// printf("\n");
// }
// return 0;
// }
