#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <stack>
#include <bitset>
#include <cstring>

using namespace std;

typedef struct{
    int h,e;
}FL_NODE;

typedef struct{
    int from,to;
}NODE;

const int INF=(1<<30);
const int Maxx=1e3+1;
int rez[Maxx][Maxx];
int graf[Maxx][Maxx];
vector<int> Adj[Maxx];
deque<int> Q;
bitset<Maxx> vis;
int father[Maxx];

bool usedEdge[1000000];

vector<FL_NODE> A;

vector<NODE> mch;

void init_preflux(int n){
    for(int i=0; i<n; ++i){
        A[i].e=0;
        A[i].h=0;
    }
    A[0].h=n-1;
    for(int i=1; i<n; ++i){
        if(graf[0][i]>0){
            rez[0][i]=0;
            rez[i][0]+=graf[0][i];
            A[i].e+=graf[0][i];
            A[0].e-=graf[0][i];
        }
    }
}

bool find(int n,int &u,int &v){
    for(int i=1; i<n-1; ++i){
        u=i;
        if(A[u].e>0){
            for(int j=0; j<n; ++j){
                v=j;
                if(rez[u][v]>0 && A[u].h==A[v].h+1){
                    return 1;
                }
            }
        }
    }
    return 0;
}

bool find2(int n,int &u){
    for(int i=1; i<n-1; ++i){
        if(A[i].e>0){
            int ok=-1;
            for(int j=0; j<n; ++j){
                if(rez[i][j]>0){
                    if(ok==-1) ok=1;
                    if(A[j].h<A[i].h){
                        ok=0;
                    }
                }
            }
            if(ok==1){
                u=i;
                return 1;
            }
        }
    }
    return 0;
}

void pompare(int from,int to){
    int delta=min(A[from].e,abs(rez[from][to]));
    rez[from][to]-=delta;
    rez[to][from]+=delta;

    A[from].e-=delta;
    A[to].e+=delta;
}

void inaltare(int n,int node){
    int h_min=INF;
    for(int i=0; i<n; ++i){
        if(rez[node][i]>0){
            h_min=min(h_min,A[i].h);
        }
    }
    A[node].h=h_min+1;
}

bool road(int n){
    vis.reset();
    father[0]=0;
    Q.clear();
    vis[0]=1;
    Q.push_back(0);
    while(!Q.empty()){
        int act=Q.front();
        Q.pop_front();
        for(auto& node: Adj[act]){
            if(rez[act][node]==graf[act][node] || vis[node]) continue;
            vis[node]=1;
            Q.push_back(node);
            father[node]=act;
            if(node==n-1) return 1;
        }
    }
    return 0;
}

int main() {
    int option=2;
    //cin>>option;
    if(option==0){//FORD
        int n,m;
        ifstream fin("05_laborator/1/8/1-in.txt");
        fin>>n>>m;
        for(int i=0; i<m; ++i){
            int x,y,cap;
            fin>>x>>y>>cap;
            graf[x][y]+=cap;
            Adj[x].push_back(y);
            Adj[y].push_back(x);
        }

        int flow,fmin;
        memset(father,-1,sizeof(father));
        for(flow=0; road(n); flow+=fmin){
            fmin=INF;
            for(int node=n-1; father[node]!=node;node=father[node]){
                fmin=min(fmin,graf[father[node]][node]-rez[father[node]][node]);
            }
            for(int node=n-1; father[node]!=node;node=father[node]){
                rez[father[node]][node]+=fmin;
                rez[node][father[node]]-=fmin;
            }
            memset(father,-1,sizeof(father));
        }
        cout<<flow<<"\n";

        return 0;
    }

    if(option==1){//PUSH RELABEL
        int n,m;
        ifstream fin("05_laborator/2/1-in.txt");
        fin>>n>>m;
        for(int i=0; i<m; ++i){
            int x,y,cap;
            fin>>x>>y>>cap;
            graf[x][y]+=cap;
            rez[x][y]+=cap;
        }

        //pompare preflux
        A.resize(n);
        init_preflux(n);
        while(true){
            int u,v;
            if(find(n,u,v)){
                pompare(u,v);
                continue;
            }

            if(find2(n,u)){
                inaltare(n,u);
                continue;
            }

            break;
        }

        cout<<abs(A[0].e)<<"\n";

        return 0;
    }

    if(option==2){
        ifstream fin("05_laborator/3/4-in.txt");
        int n,m;
        fin>>n>>m;
        for(int i=0; i<m; ++i){
            int x,y;
            fin>>x>>y;
            Adj[x].push_back(i);
            Adj[y].push_back(i);
            mch.push_back({x,y});
        }

        for(int i=0; i<n; ++i){
            if(Adj[i].size()%2!=0){
                cout<<"-1\n";
                return 0;
            }
        }

        vector<int> ans;

        stack<int> st;
        st.push(1);
        while(!st.empty()){
            int node=st.top();
            if(!Adj[node].empty()){
                int e=Adj[node].back();
                Adj[node].pop_back();
                if(!usedEdge[e]){
                    usedEdge[e]=true;
                    int to=::mch[e].from ^ ::mch[e].to ^ node;
                    st.push(to);
                }
            } else {
                st.pop();
                ans.push_back(node);
            }
        }
        ans.erase(ans.begin());
        for(auto& it: ans){
            cout<<it<<" ";
        }
        cout<<"\n";

        return 0;
    }

    return 0;
}