#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
 
using namespace std;

class Graf
{
private:
    static constexpr int NMAX = 100009;
    const unsigned N, M;
    vector<int> Adiacenta[NMAX];  // liste de adiacenta


public:
    Graf(int, int);
    void AdMuchie(int, int);

    static constexpr int getNMAX() { return Graf::NMAX; }

// BF-DF si aplicatii
    void Bfs(int, int*);
    int  Dfs();
    void Biconex(vector<vector<int>>&);
    void CompTareConexe(vector<int>*, vector<vector<int>>&, int&);
    void MuchieCritica(vector<vector<int>>&);
    void ProbGraf_NoduriComune(int, int, vector<int>&);
    void SortTopo(int*);

    static bool HavelHakimi(int*, int);

// Drumuri minime si APM
    void APM(vector<vector<int>>&, int&, vector<pair<int, int>>&); 
    void Dijkstra(vector<vector<pair<int, int>>>&, int, int, vector<int>&);
    bool BellmanFord(vector<vector<pair<int, int>>>& Adiacenta, int, int, vector<int>&);

    static void Disjoint(int, vector<vector<int>>&, vector<string>&);

// Laborator 5
    void RoyFloyd(int[][100], int);
    int  DiametruArbore();
    int  FluxMaxim(int, int, vector<vector<int>>&);

// Laborator 6
    bool CicluEulerian(int, vector<vector<pair<int, int>>>&, vector<int>&);

private:
    void Dfs_fHelper(int, bool*);
    void Biconex_fHelper(int, int, pair<int, int>*, int&, int*, int*, vector<vector<int>>&);
    void CompTareConexe_Dfs(int, bool*, int*, int&);
    void CompTareConexe_t_Dfs(int, bool*, vector<int>*, vector<vector<int>>&, int);
    void MuchieCritica_fHelper(int, int, int*, int*, vector<vector<int>>&);
    void NoduriComune_BfsInainte(int, int, int*);
    void NoduriComune_BfsInapoi(int, int, int*, int*, vector<int>&);
    bool FluxMaxim_Drum(int, int, vector<vector<int>>&, vector<vector<int>>&, bool*, int*);

    static int  Disjoint_CautaRadacina(int, int*);
    static void Disjoint_CompresieDrumuri(int, int, int*);
    static void Disjoint_Reuneste(int, int, int*, int*);
};
 
Graf::Graf(int n, int m)
    : N(n), M(m)
{
}
 
void Graf::AdMuchie(int ini, int fin)
{
    Adiacenta[ini].push_back(fin);
}

void Graf::Bfs(int S, int* nrArce)
{
    int coada[NMAX], st = 0, dr = 0;
 
    for (unsigned i = 1; i <= N; ++i)
        nrArce[i] = -1;
    nrArce[S] = 0;
    coada[st] = S;
    while (st <= dr)
    {
        int curent = coada[st++];
        for (auto it = Adiacenta[curent].begin(); it != Adiacenta[curent].end(); ++it)
            if(nrArce[*it] == -1)
            {
                coada[++dr] = *it;
                nrArce[*it] = nrArce[curent] + 1;
            }
    }
}

int Graf::Dfs()
{
    bool vizitat[NMAX];
    int nrComp = 0;

    memset(vizitat, 0, NMAX * sizeof(bool));
    for (unsigned i = 1; i <= N; ++i)
        if (!vizitat[i])
        {
            ++nrComp;
            Dfs_fHelper(i, vizitat);
        }

    return nrComp;
}

void Graf::Dfs_fHelper(int curent, bool* vizitat)
{
    vizitat[curent] = true;
    for (auto it = Adiacenta[curent].begin(); it != Adiacenta[curent].end(); ++it)
        if (!vizitat[*it])
            Dfs_fHelper(*it, vizitat);
}

void Graf::Biconex(vector<vector<int>>& compBic)
{
    pair<int, int> Stiva[NMAX * 2];
    int stVf = 0;
    int nivelInArbDFS[NMAX];  // folosit si ca vizitat[]
    int nivelMinVecini[NMAX];

    nivelInArbDFS[0] = 0;
    Biconex_fHelper(1, 0, Stiva, stVf, nivelInArbDFS, nivelMinVecini, compBic);
}

void Graf::Biconex_fHelper(int nod, int parinte, pair<int, int>* Stiva, int& stVf, int* nivelInArbDFS, int* nivelMinVecini, vector<vector<int>>& compBic)
{
    nivelInArbDFS[nod] = nivelInArbDFS[parinte] + 1;
    nivelMinVecini[nod] = NMAX;
    for (int& vecin : Adiacenta[nod])
    {
        if (nivelInArbDFS[vecin])  // daca e vizitat
        {
            if (nivelMinVecini[nod] > nivelInArbDFS[vecin] && vecin != parinte)
                nivelMinVecini[nod] = nivelInArbDFS[vecin];
        }
        else
        {
            Stiva[++stVf] = {nod, vecin};
            Biconex_fHelper(vecin, nod, Stiva, stVf, nivelInArbDFS, nivelMinVecini, compBic);

            if (nivelMinVecini[nod] > nivelMinVecini[vecin])
                nivelMinVecini[nod] = nivelMinVecini[vecin];
            
            if (nivelMinVecini[vecin] >= nivelInArbDFS[nod])
            {
                compBic.push_back({});
                while (Stiva[stVf].first != nod)
                    compBic.back().push_back(Stiva[stVf--].second);
                compBic.back().push_back(Stiva[stVf].second);  // muchia din 'nod', intreaga
                compBic.back().push_back(Stiva[stVf].first);   //
                --stVf;
            }
        }
    }
}

void Graf::CompTareConexe(vector<int>* t_Adiacenta, vector<vector<int>>& compTC, int& nrComp)
{
    int stivaTopo[NMAX], stVf = 0;    // stivaTopo - stiva de noduri in care nodurile sunt inserate in ordinea topologica inversata
    bool vizitat[NMAX];

    memset(vizitat, 0, (N + 1) * sizeof(bool));
    for (unsigned nod = 1; nod <= N; ++nod)
        if (!vizitat[nod])
            CompTareConexe_Dfs(nod, vizitat, stivaTopo, stVf);

    compTC.resize(N);
    nrComp = 0;
    memset(vizitat, 0, (N + 1) * sizeof(bool));
    while (stVf)
    {
        if (!vizitat[stivaTopo[stVf]])
            CompTareConexe_t_Dfs(stivaTopo[stVf], vizitat, t_Adiacenta, compTC, nrComp++);
        --stVf;
    }
}

void Graf::CompTareConexe_Dfs(int nod, bool* vizitat, int* stivaTopo, int& stVf)
{
    vizitat[nod] = true;
    for (auto& vecin : Adiacenta[nod])
        if (!vizitat[vecin])
            CompTareConexe_Dfs(vecin, vizitat, stivaTopo, stVf);
    stivaTopo[++stVf] = nod; 
}

void Graf::CompTareConexe_t_Dfs(int nod, bool* vizitat, vector<int>* t_Adiacenta, vector<vector<int>>& compTC, int nrComp)
{
    vizitat[nod] = true;
    for (auto& vecin : t_Adiacenta[nod])
        if (!vizitat[vecin])
            CompTareConexe_t_Dfs(vecin, vizitat, t_Adiacenta, compTC, nrComp);
    compTC[nrComp].push_back(nod);
}

void Graf::MuchieCritica(vector<vector<int>>& mCritice)
{
    int nivelInArbDFS[NMAX];  // folosit si ca vizitat[]
    int nivelMin[NMAX];

    memset(nivelInArbDFS, 0, (N + 1) * sizeof(int));
    MuchieCritica_fHelper(0, 0, nivelInArbDFS, nivelMin, mCritice);
}

void Graf::MuchieCritica_fHelper(int nod, int parinte, int* nivelInArbDFS, int* nivelMin, vector<vector<int>>& mCritice)
{
    nivelInArbDFS[nod] = nivelMin[nod] = nivelInArbDFS[parinte] + 1;
    for (int& vecin : Adiacenta[nod])
    {
        if (nivelInArbDFS[vecin])
        {
            if (nivelMin[nod] > nivelInArbDFS[vecin] && vecin != parinte)
                nivelMin[nod] = nivelInArbDFS[vecin];
        }
        else
        {
            MuchieCritica_fHelper(vecin, nod, nivelInArbDFS, nivelMin, mCritice);

            if (nivelMin[nod] > nivelMin[vecin])
                nivelMin[nod] = nivelMin[vecin];

            // muchie critica
            if (nivelMin[vecin] > nivelInArbDFS[nod])  // nivelMin[vecin] == nivelInArbDFS[vecin]
                mCritice.push_back({nod, vecin});
        }
    }
}

void Graf::ProbGraf_NoduriComune(int X, int Y, vector<int>& noduri)
{
    int lungime[NMAX];  // folosit si ca vizitat[] in BfsInainte => lungimea se calculeaza incepand de la 1
    int nrVizite[NMAX];  // folosit in BfsInapoi pt a identifica unificarea ramurilor (si pentru vizitat[])

    noduri.push_back(X);
    // noduri.push_back(Y);  -- nu e nevoie, e mereu primul adaugat in BfsInapoi
    NoduriComune_BfsInainte(X, Y, lungime);
    NoduriComune_BfsInapoi(X, Y, lungime, nrVizite, noduri);

    sort(noduri.begin(), noduri.end());
}

void Graf::NoduriComune_BfsInainte(int X, int Y, int* lungime)
{
    int coada[NMAX], st = 0, dr = -1;
    bool COADA_STOP_INTRARI = false;

    coada[++dr] = X;
    lungime[X] = 1;
    while (st <= dr)
    {
        int nodCurent = coada[st++];
        for (int& vecin : Adiacenta[nodCurent])
            if (!lungime[vecin])
            {
                lungime[vecin] = lungime[nodCurent] + 1;
                if (vecin == Y)
                    COADA_STOP_INTRARI = true;
                if (!COADA_STOP_INTRARI)
                    coada[++dr] = vecin;
            }
    }
}

void Graf::NoduriComune_BfsInapoi(int X, int Y, int* lungime, int* nrVizite, vector<int>& noduri)
{
    int nrRamuri = 1;   // total ramuri existente la pasul curent

    int coada[NMAX], st = 0, dr = -1;
    coada[++dr] = Y;
    while (st <= dr)
    {
        int nodCurent = coada[st++];
        int ramuriDinCurent = 0;      // cate ramuri pornesc din nodul curent, cel putin una din moment ce avem drum mai departe

        if (nrRamuri == 1)
            noduri.push_back(nodCurent);

        for (int& vecin : Adiacenta[nodCurent])
        {
            if (lungime[vecin] == lungime[nodCurent] - 1)
            {
                ++ramuriDinCurent;
                ++nrVizite[vecin];
                if (nrVizite[vecin] > 1)
                    --nrRamuri;
                if (vecin == X)
                    break;
                if (nrVizite[vecin] == 1)
                    coada[++dr] = vecin;
            }
        }

        nrRamuri += (ramuriDinCurent - 1); 
    }                                 
}

void Graf::SortTopo(int* noduri)
{
    bool vizitat[NMAX];
    int dr = 0;
    
    memset(vizitat, 0, (N + 1) * sizeof(bool));
    for (unsigned nod = 1; nod <= N; ++nod)
        if (!vizitat[nod])
            CompTareConexe_Dfs(nod, vizitat, noduri, dr);
    reverse(noduri + 1, noduri + 1 + N);
}

int Graf::DiametruArbore()
{
    int dist[NMAX], nodCapatLant, diametru;
    
    Bfs(1, dist);
    nodCapatLant = max_element(dist + 1, dist + N + 1) - dist;
    Bfs(nodCapatLant, dist);
    diametru = *max_element(dist + 1, dist + N + 1) + 1;

    return diametru;
}

bool Graf::HavelHakimi(int* S, int N)
{
    auto descrescator = [](int a, int b) { return a > b; };
    sort(S, S + N, descrescator);

    if (S[0] >= N)
        return false;
    
    int grMax, pozPrimElem = 0;
    while (S[pozPrimElem] > 0)
    {   
        grMax = S[pozPrimElem++];
        for (int i = pozPrimElem; i < pozPrimElem + grMax; ++i)
            --S[i];

        sort(S + pozPrimElem, S + N, descrescator);
        if (S[N - 1] < 0)
            return false;
    }
    return true;
}

void Graf::Dijkstra(vector<vector<pair<int, int>>>& Adiacenta, int src, int INF, vector<int>& dist)
{
    auto comp = [](pair<int,int>& st, pair<int,int>& dr) { return st.second > dr.second; };
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> heap(comp);
    bool extras[NMAX];
    
    memset(extras, 0, (N + 1) * sizeof(bool));
    dist.resize(N + 1, INF);
    dist[src] = 0;

    heap.push({src, 0});
    while (!heap.empty())
    {
        int nodCurent = heap.top().first;
        heap.pop();
        
        if (extras[nodCurent])
            continue;
        extras[nodCurent] = true;

        for (auto& vecin : Adiacenta[nodCurent])
        {
            int nodVecin = vecin.first;
            int costMuchieVecin = vecin.second;
            if (dist[nodVecin] > dist[nodCurent] + costMuchieVecin)
            {
                dist[nodVecin] = dist[nodCurent] + costMuchieVecin;
                heap.push({nodVecin, dist[nodVecin]});
            }
        }
    }
}

bool Graf::BellmanFord(vector<vector<pair<int, int>>>& Adiacenta, int src, int INF, vector<int>& dist)
{
    queue<int> coadaNoduri;
    unsigned nrMuchiiLant[NMAX];
    bool inCoada[NMAX];

    memset(inCoada, 0, (N + 1) * sizeof(bool));
    nrMuchiiLant[src] = 0;
    dist.resize(N + 1, INF);
    dist[src] = 0;

    coadaNoduri.push(src);
    while (!coadaNoduri.empty())
    {
        int nodCurent = coadaNoduri.front();
        coadaNoduri.pop();
        inCoada[nodCurent] = false;
        
        for (auto& vecin : Adiacenta[nodCurent])
        {
            int nodVecin = vecin.first;
            int costMuchieVecin = vecin.second;
            if (dist[nodVecin] > dist[nodCurent] + costMuchieVecin)
            {
                dist[nodVecin] = dist[nodCurent] + costMuchieVecin;
                nrMuchiiLant[nodVecin] = nrMuchiiLant[nodCurent] + 1;

                if (nrMuchiiLant[nodVecin] == N)
                    return true;

                if (!inCoada[nodVecin])
                {
                    coadaNoduri.push(nodVecin);
                    inCoada[nodVecin] = true;               
                }
            }
        }
    }

    return false;
}

void Graf::RoyFloyd(int ponderi[][100], int INF)
{
    for (unsigned i = 0; i < N; ++i)
        for (unsigned j = 0; j < N; ++j)
            if (ponderi[i][j] == 0 && i != j)
                ponderi[i][j] = INF;
    
    for (unsigned K = 0; K < N; ++K)
        for (unsigned A = 0; A < N; ++A)
            for (unsigned B = 0; B < N; ++B)
                if (ponderi[A][B] > ponderi[A][K] + ponderi[K][B])
                    ponderi[A][B] = ponderi[A][K] + ponderi[K][B];
}

void Graf::APM(vector<vector<int>>& muchiiGraf, int& costAPM, vector<pair<int, int>>& muchiiAPM)
{
    // Kruskal

    auto comp = [](vector<int>& m1, vector<int>& m2) { return m1[2] < m2[2]; };
    sort(muchiiGraf.begin(), muchiiGraf.end(), comp);
    costAPM = 0;
    muchiiAPM.reserve(N - 1);

    int tata[NMAX * 2], rang[NMAX * 2];  // rangurile arborilor se retin in radacini
    memset(tata, 0, N * sizeof(int));
    memset(rang, 0, N * sizeof(int));  // va fi inaltime - 1

    auto mc = muchiiGraf.begin();
    while (muchiiAPM.size() < N - 1)
    {
        int x = mc->at(0);
        int y = mc->at(1);
        int cost = mc->at(2);
        int radX = Disjoint_CautaRadacina(x, tata);
        int radY = Disjoint_CautaRadacina(y, tata);
        Disjoint_CompresieDrumuri(x, radX, tata);
        Disjoint_CompresieDrumuri(y, radY, tata);

        if (radX != radY)
        {
            Disjoint_Reuneste(radX, radY, tata, rang);

            costAPM += cost;
            muchiiAPM.push_back({x, y});
        }

        ++mc;
    }
}

int Graf::Disjoint_CautaRadacina(int nod, int* tata)
{
    while (tata[nod])
        nod = tata[nod];
    return nod;
}

void Graf::Disjoint_CompresieDrumuri(int nod, int radacina, int* tata)
{
    while (tata[nod])
    {
        int old = tata[nod];
        tata[nod] = radacina;
        nod = tata[old];
    }
}

void Graf::Disjoint_Reuneste(int radX, int radY, int* tata, int* rang)
{
    if (rang[radX] > rang[radY])  // fiindca rang[radX] e strict mai mare decat rang[radY], 
        tata[radY] = radX;        // adaugarea arb. radY ca subarb. al lui radX nu va putea creste rang[radX]
    else // rang[radX] <= rang[radY]
    {
        tata[radX] = radY;
        if (rang[radY] == rang[radX])   // daca rangurile sunt egale, prin legarea rad., rangul celui de care s-a legat va creste cu 1
            ++rang[radY];
    }
}
void Graf::Disjoint(int N, vector<vector<int>>& Operatii, vector<string>& Raspuns)
{
    int tata[NMAX], rang[NMAX];  // rangurile arborilor se retin in radacini
    memset(tata, 0, N * sizeof(int));
    memset(rang, 0, N * sizeof(int));  // va fi inaltime - 1

    for (auto& op : Operatii)
    {
        int x = op[1];
        int y = op[2];
        int radX = Disjoint_CautaRadacina(x, tata);
        int radY = Disjoint_CautaRadacina(y, tata); 

        if (op[0] == 1)
            Disjoint_Reuneste(radX, radY, tata, rang);
        else
        {
            if (radX != radY)
                Raspuns.emplace_back("NU");
            else
                Raspuns.emplace_back("DA");

            // Compresia drumurilor
            Disjoint_CompresieDrumuri(x, radX, tata);
            Disjoint_CompresieDrumuri(y, radY, tata);
        }
    }
}

int Graf::FluxMaxim(int src, int dst, vector<vector<int>>& capacitati)
{
    // Edmonds-Karp

    const int NMAX = 1001;
    vector<vector<int>> flux(NMAX, vector<int>(NMAX, 0));
    int tata[NMAX], fluxMaxRetea = 0;
    bool vizitat[NMAX];

    memset(tata, 0, (N + 1) * sizeof(int));
    while (FluxMaxim_Drum(src, dst, capacitati, flux, vizitat, tata))
    {
        for (int vecinDst : Adiacenta[dst])
        {
            if (flux[vecinDst][dst] < capacitati[vecinDst][dst] && vizitat[vecinDst])
            {
                int fluxMaxDrum = capacitati[vecinDst][dst] - flux[vecinDst][dst];
                for (int nod = vecinDst; tata[nod]; nod = tata[nod])
                {
                    int tataNod = tata[nod];
                    fluxMaxDrum = min(fluxMaxDrum, capacitati[tataNod][nod] - flux[tataNod][nod]);
                }

                flux[vecinDst][dst] += fluxMaxDrum; 
                flux[dst][vecinDst] -= fluxMaxDrum; 
                for (int nod = vecinDst; tata[nod]; nod = tata[nod])
                {
                    int tataNod = tata[nod];
                    flux[tataNod][nod] += fluxMaxDrum; 
                    flux[nod][tataNod] -= fluxMaxDrum; 
                }
                
                fluxMaxRetea += fluxMaxDrum;
            }
        }
    }

    return fluxMaxRetea;
}

bool Graf::FluxMaxim_Drum(int src, int dst, vector<vector<int>>& capacitati, vector<vector<int>>& flux, bool* vizitat, int* tata)
{
    const int NMAX = 1001;
    int coada[NMAX], st = 0, dr = -1;

    memset(vizitat, 0, (N + 1) * sizeof(bool));
    coada[++dr] = src;
    vizitat[src] = true;

    while (st <= dr)
    {
        int nodCurent = coada[st++];
        for (int vecin : Adiacenta[nodCurent])
        {
            if (!vizitat[vecin] && flux[nodCurent][vecin] < capacitati[nodCurent][vecin])
            {
                vizitat[vecin] = true;
                if (vecin != dst)
                {
                    tata[vecin] = nodCurent;
                    coada[++dr] = vecin;
                }
            }
        }
    }

    return vizitat[dst];
}

vector<vector<pair<int, int>>> lAdiacenta;

bool Graf::CicluEulerian(int nodStart, vector<vector<pair<int, int>>>& lAdiacenta, vector<int>& solutie)
{
    for (unsigned i = 1; i <= N; ++i)
        if (lAdiacenta[i].size() % 2)
            return false;

    int stiva[NMAX];
    stiva[0] = 1;
    stiva[1] = nodStart;

    while (stiva[0] > 0)
    {
        int nodCurent = stiva[stiva[0]];
        if (lAdiacenta[nodCurent].size() > 0)
        {
            int nodUrmator = lAdiacenta[nodCurent].back().first;
            int idxListaVecin =  lAdiacenta[nodCurent].back().second;

            lAdiacenta[nodCurent].pop_back();
            lAdiacenta[nodUrmator][idxListaVecin] = lAdiacenta[nodUrmator].back();
            lAdiacenta[nodUrmator].pop_back();

            stiva[++stiva[0]] = nodUrmator;
        }
        else
        {
            solutie.push_back(nodCurent);
            --stiva[0];
        }
    }
    solutie.pop_back();

    if (solutie.size() != M)  // muchiile nu fac parte dintr-o singura componenta conexa
        return false;
    
    return true;
}


int main()
{   
    ifstream f("ciclueuler.in");
    ofstream g("ciclueuler.out");
    unsigned N, M, nodStart = 1;

    f >> N >> M;
    Graf graf(N, M);
    lAdiacenta.resize(N + 1);
    for (unsigned x, y, i = 0; i < M; ++i)
    {
        f >> x >> y;
        nodStart = x;
        if (x != y)
        {
            lAdiacenta[x].push_back({y, (int)lAdiacenta[y].size()});
            lAdiacenta[y].push_back({x, (int)lAdiacenta[x].size() - 1});
        }
        else
        {
            lAdiacenta[x].push_back({y, (int)lAdiacenta[y].size() + 1});
            lAdiacenta[y].push_back({x, (int)lAdiacenta[x].size() - 1});
        }
    }

    vector<int> solutie;
    if (!graf.CicluEulerian(nodStart, lAdiacenta, solutie))
        g << -1;
    else
        for (auto nod : solutie)
            g << nod << ' ';

    return 0;
}