#include <stdio.h>

typedef struct _nod {
    long val;
    struct _nod *urm;
} NOD;

long n,m,x,y;
int s[100010];

NOD *vf[100010],*sf[100010];

NOD *CICLU;

FILE *fin=fopen("ciclueuler.in","r");
FILE *fout=fopen("ciclueuler.out","w");

void adauga_lis_adiacenta(long i,long j){

    if(vf[i]==NULL){
        vf[i]=new NOD;
        vf[i]->val=j;
        vf[i]->urm=NULL;
        sf[i]=vf[i];
    }
    else{


        NOD *c=new NOD;
        c->val=j;
        c->urm=NULL;
        vf[i]->urm=c;
        sf[i]=c;
    }
}

void sterge_lis_adiacenta(NOD *&vf, NOD *sf, int val){

    NOD *c, *aux;

    if(vf->val==val)
    {
        aux=vf;
        vf=vf->urm;
    }
    else{
        c=vf;
        while(c->urm->val!=val)
            c=c->urm;
        aux=c->urm;
        c->urm=aux->urm;
        if(aux==sf)
            sf=c;
    }
    delete aux;
}



void afis(){

    for(long i=1;i<=n;i++){

        fprintf(stderr,"%ld: ",i);
        NOD *c = vf[i];
        while(c!=NULL){
            fprintf(stderr,"%d | ",c->val);
            c=c->urm;
        }
        fprintf(stderr,"\n");

    }
}

int grad_par(){

    for(long i=1;i<=n;i++){

        long s=0;
        NOD *c = vf[i];
        while(c!=NULL){
            s+=1;
            c=c->urm;
        }
        if(s%2==0)
            return 1;

    }

    return 0;
}

void parcurgere_adancime(long nod){

    s[nod]=1;

    NOD *c = vf[nod];
    while(c!=NULL){
        if(s[c->val]==0)
            parcurgere_adancime(c->val);
        c=c->urm;
    }
}

int conex(){
    long sum=0;

    parcurgere_adancime(n);

    for(long i=1;i<=n;i++)
        sum+=s[i];

    if(sum==n)
        return 1;
    else
        return 0;
}

void Ciclu(NOD *c){
    NOD *n_baza, *n_gasit, *n_urm;
    NOD *cc;

    int nrnod;

    n_baza=c;
    n_urm=c->urm;

    do{


        cc=vf[n_baza->val];
        while(cc!=NULL){
            nrnod=1;
            while(nrnod<=cc->val)
                ++nrnod;

            sterge_lis_adiacenta(vf[n_baza->val],sf[n_baza->val],nrnod);

            fprintf(stderr,"\n");
            afis();

            sterge_lis_adiacenta(vf[nrnod],sf[nrnod],n_baza->val);

            fprintf(stderr,"\n");
            afis();

            n_gasit=new NOD;
            n_gasit->val=nrnod;
            n_gasit->urm=NULL;
            n_baza->urm=n_gasit;
            n_baza=n_gasit;

            cc=cc->urm;
        }

    }while(n_baza == cc);
    n_baza->urm=n_urm;


}

int adauga_ciclu(){

    long k=0;
    NOD *ciclu=CICLU;

    while(ciclu!=NULL && k==0){
        NOD *c=vf[ciclu->val];
        while(c!=NULL){

            if(c->val)
                k=1;
            c=c->urm;
        }
        if(k==0)
            ciclu=ciclu->urm;
    }

    if(ciclu!=NULL)
    {
        Ciclu(ciclu);
        return 1;
    }
    return 0;
}


int main(){

    fscanf(fin,"%ld%ld",&n,&m);

    for(long i=1;i<=m;i++){
        fscanf(fin,"%ld%ld",&x,&y);
        adauga_lis_adiacenta(x,y);
        adauga_lis_adiacenta(y,x);
    }

    afis();

    fprintf(fout,"\n");

    if(grad_par())
        fprintf(stderr,"are grad par");

    fprintf(fout,"\n");

    if(conex())
        fprintf(stderr,"este conex");

    fprintf(fout,"\n");

    if(grad_par()){
        if(conex()){

            CICLU = new NOD;
            CICLU->val=1;
            CICLU->urm=NULL;
            long i=1;
            while(adauga_ciclu());

        }
    }
    else{
        fprintf(fout,"-1");
    }

}