CF36E Two Paths

// LUOGU_RID: 97073377
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 3e4 + 1 ;
int n , h [ N ] , nt [ N << 1 ] , to [ N << 1 ] , id [ N << 1 ] , tot ;
int ji [ N ] ;
struct ltx{
    int fa [ N ] ;
    int find ( int x ) { return fa [ x ] == x ? x : fa [ x ] = find ( fa [ x ] ) ; }
    bool add ( int x , int y ) {
        if ( find ( x ) == find ( y ) ) return false;
        fa [ fa [ x ] ] = fa [ y ] ;
        return true;
    }
    void clear ( int x ) {
        for ( int i = 1 ; i <= x ; i ++ )
            fa [ i ] = i ;
        return ;
    }
    void number ( int x , int & number ) { for ( int i = 1 ; i <= x ; i ++ ) if ( find ( i ) == i ) { number ++ ; ji [ number ] = i ; } return ; }
    ltx () { clear ( 20000 ) ; }
} ;
ltx check;
int rhs , X [ N ] , Y [ N ] , du [ N ] ;
int vis [ N ] ;
int ls [ N ] , m ;
void add ( int x , int y , int ids ) { nt [ ++ tot ] = h [ x ] ; h [ x ] = tot ; to [ tot ] = y ; id [ tot ] = ids ; }
void link ( int x , int y , int ids ) { add ( x , y , ids ) ; add ( y , x , ids ) ; return ; }
int st [ N ] , ceng;
void euler ( int x )
{
    for ( int i = h [ x ] ; i ; i = nt [ i ] ) {
        if ( vis [ id [ i ] ] ) continue;
        vis [ id [ i ] ] = 1 ;
        euler ( to [ i ] ) ;
        st [ ++ ceng ] = id [ i ] ;
    }
}
void works ( ) {
    int cnt = 0 , a [ 11 ] ;a [ 1 ] = ji [ 1 ] ;
    for ( int i = 1 ; i <= m ; i ++ ) {
        if ( du [ i ] % 2 == 1 ) a [ ++ cnt ] = i ;
        if ( cnt > 4 ) { return ( void ) printf ( "-1" )  ; }
    }
    link ( a [ 1 ] , a [ 2 ] , n + 1 ) ;
    euler ( a [ 3 ] ) ;
    if ( ceng <= 1 ) { return ( void ) printf ( "-1" )  ; }
    int i ;
    for (  i = 1 ; i <= ceng ; i ++ ) if ( st [ i ] == n + 1 ) break;
    cout << ceng - i << '\n';
    for ( int j = ceng ; j > i ; j -- ) cout << st [ j ] << '\n' ;
    cout << i - 1 << '\n' ;
    for ( int j = i - 1 ; j >= 1 ; j -- ) cout << st [ j ] << '\n' ;
    return ;
}
void work1 ( ) { // 连通图
    int cnt = 0 , a [ 5 ] ;a [ 1 ] = ji [ 1 ] ;
    for ( int i = 1 ; i <= m ; i ++ ) {
        if ( du [ i ] % 2 == 1 ) a [ ++ cnt ] = i ;
        if ( cnt > 2 ) { works ( ) ; return ; }
    }
    euler ( a [ 1 ] ) ;
    if ( ceng <= 1 ) { return ( void ) printf ( "-1" )  ; }
    cout << 1 << '\n' << st [ ceng ] << '\n' ;
    cout << ceng - 1 << '\n' ;
    for ( int i = ceng - 1 ; i >= 1 ; i -- ) cout << st [ i ] << '\n' ;
}
int pre [ N ] ;
void work2 ( ) {
    int cnt = 0 , a [ 5 ] ;a [ 1 ] = ji [ 1 ] ;
    for ( int i = 1 ; i <= m ; i ++ ) if ( check . fa [ i ] == ji [ 1 ] ) {
        if ( du [ i ] % 2 == 1 ) a [ ++ cnt ] = i ;
        if ( cnt > 2 ) { return ( void ) printf ( "-1" )  ; }
    }
    euler ( a [ 1 ] ) ;
    pre [ 0 ] = ceng ;
    for ( int i = ceng ; i >= 1 ; i -- ) pre [ ceng - i + 1 ] = st [ i ] ;
    cnt = 0 ;a [ 1 ] = ji [ 2 ] ;
    for ( int i = 1 ; i <= m ; i ++ ) if ( check . fa [ i ] == ji [ 2 ] ) {
        if ( du [ i ] % 2 == 1 ) a [ ++ cnt ] = i ;
        if ( cnt > 2 ) { return ( void ) printf ( "-1" )  ; }
    }
    ceng = 0 ;
    euler ( a [ 1 ] ) ;
    for ( int i = 0 ; ; i ++ ) { if ( pre [ i ] == 0 ) break ; cout << pre [ i ] << endl ; }
    cout << ceng << '\n' ;
    for ( int i = ceng  ; i >= 1 ; i -- ) cout << st [ i ] << '\n' ;
}
int main ( ) {
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    cin >> n ;
    for ( int i = 1 ; i <= n ; i ++ ) {
        cin >> X [ i ] >> Y [ i ] ;
        ls [ ++ m ] = X [ i ] ; ls [ ++ m ] = Y [ i ] ;
    }
    sort ( ls + 1 , ls + m + 1 ) ;
    m = unique ( ls + 1 , ls + m + 1 ) -ls - 1 ;
    for ( int i = 1 ; i <= n ; i ++ ) {
        X [ i ] = lower_bound ( ls + 1 , ls + m + 1 , X [ i ] ) - ls ;
        Y [ i ] = lower_bound ( ls + 1 , ls + m + 1 , Y [ i ] ) - ls ;
        link ( X [ i ] , Y [ i ] , i ) ;
        check . add ( X [ i ] , Y [ i ] ) ;
        du [ X [ i ] ] ++ ;du [ Y [ i ] ] ++ ;
    }
    check . number ( m , rhs ) ;
    if ( rhs > 2 ) { return printf ( "-1" ) * 0 ; }
    if ( rhs == 1 ) { work1 ( ) ; }
    else work2 ( ) ;
    return 0  ;
}