//
//  main.cpp
//  Ciclu Eulerian
//
//  Created by Mara Dascalu on 11/12/2021.
//

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <bits/stdc++.h>
#include <map>
#include <list>
#include <set>
#include <tuple>

#define INF INT_MAX
#define N  100005
typedef std::tuple<int, int> tpl;

using namespace std;

ifstream input("ciclueuler.in");
ofstream output("ciclueuler.out");

class DisjointSets
{
int no_nodes;
vector<int> reprez;     //vectorul care retine reprezentantul fiecarui nod

public:

void set_no_nodes(int nr) { no_nodes = nr;}
int get_no_nodes() { return no_nodes;}

void initialization(int no_node);      //creeaza fiecare nod drept un subarbore
int reprezentative(int node, int father[]);       //returneaza reprezentantul componentei care il contine pe node
void reunite(int node1, int node2, int height[], int father[]); //uneste componenta care contine node1 cu cea care contine node2
};

void DisjointSets::initialization(int no_node)
{
set_no_nodes(no_nodes);

reprez.push_back(0);
for (int i = 1 ; i <= no_nodes; i++)
{
    reprez.push_back(0);
}
}

int DisjointSets::reprezentative(int node, int father[])
{
while (father[node])
    node = father[node];
return node;
}

void DisjointSets::reunite(int node1, int node2, int height[], int father[])
{
int r1, r2;

r1 = reprezentative(node1, father);
r2 = reprezentative(node2, father);

if (height[r1] > height[r2])
    father[r2] = r1;
else
{
    father[r1] = r2;
    if (height[r1] == height[r2])
        height[r2]++;
}
}

class Graph
{
int nodes, edges;
vector<int> adj[N] ;
vector<tuple<int,int>> adj_weight[N];
vector<tuple<int,int>> adj_capacity[N];
bool visited[N] = {0};

void set_no_nodes(int n) {nodes = n;}
int get_no_nodes() {return nodes;}
void set_no_edges(int n) {edges = n;}
int get_no_edges() {return edges;}

void addEdges_dg (int no_nodes, int no_edges);
void addEdges_ug ();
void addEdges_dg_weight();
void addEdges_dg_capacity();

void DFS(int node);     //parcurgerea DFS a grafului
void afis_adj(int node);       //afisarea vectorului de vectori de adiacenta a nodurilor
static bool sortByThird (const tuple<int,int,int> &a, const tuple<int,int,int>&b);    //sorteaza vectorul de tupluri coare contine si costul muchiilor dupa al treilea parametru (cost)

//PROBLEMA BFS INFORARENA: https://infoarena.ro/problema/bfs
void BFSUtil(int node);    //BFS adaptat pentru a calcula costul de parcurgere al fiecarui nod, plecand dintr-un nod de start

//PROBLEMA COMPONENTE BICONEXE INFOARENA: https://infoarena.ro/problema/biconex
void DFS_biconnectedComponents(int node, int parent, int level[], int low_level[], vector<vector<int>> &bcc, stack<pair<int,int>> &component_node, int &current);     // DFS auxiliar pentru determinarea componentelor biconexe

//PROBLEMA SORTARE TOPOLOGICA INFOARENA: https://infoarena.ro/problema/sortaret
void calculateIndegree (int indegree[]);       //functie auxiliara sortarii topologice pentru calcularea gradului interior al fiecarui nod
void topSort(int indegree[], queue<int> queue_ts);      //functia de sortare topologica

//PROBLEMA HAVEL-HAKIMI
bool graphExists (vector<int> degree_seq);      //functia care decide daca daca o secventa de numere poate sau nu poate reprezenta o secventa de noduri ale unui graf
void inputArray (vector<int> &degree_seq);

//PROBLEMA APM INFOARENA: https://infoarena.ro/problema/apm
void inputAPM(vector<tuple<int,int,int>> &weight_edges);
void APMUtil(vector<tuple<int,int,int>> &weight_edges);

//PROBLEMA FLUX MAXIM INFOARENA: https://infoarena.ro/problema/maxflow
bool bfs_maxFlow(int src, int dst, vector<vector<int>> residualGraph, int parent[]);
int Edmonds_Karp(int src, int dst);

//PROBLEMA ROY-FLOYD INFOARENA: https://infoarena.ro/problema/royfloyd
void inputRoy_Floyd(int dist[][N]);
void Roy_FloydUtil(int dist[][N]);
void outputRoy_Floyd(int dist[][N]);

//PROBLEMA DIAMETRUL UNUI ARBORE INFOARENA: https://infoarena.ro/problema/darb
void dfsUtil(int src, int &dst, int count, int &max_count);
void dfs_diameter(int src, int &dst,int &max_count);

//PROBLEMA CICLU EULERIAN INFOARENA: https://infoarena.ro/problema/ciclueuler
vector<int> EulerCircuit(vector<tuple<int,int>> edges[]);

public:

//PROBLEMA DFS INFOARENA: https://infoarena.ro/problema/dfs
int connectedComponents();     //determinarea numarului de componente conexe ale grafului

//PROBLEMA BFS INFORARENA: https://infoarena.ro/problema/bfs
void BFS();

//PROBLEMA COMPONENTE BICONEXE INFOARENA: https://infoarena.ro/problema/biconex
void biconnectedComponents();     //determina componentele biconexe ale unui graf

//PROBLEMA SORTARE TOPOLOGICA INFOARENA: https://infoarena.ro/problema/sortaret
void topologicalSort();

//PROBLEMA HAVEL-HAKIMI
void Havel_Hakimi();

//PROBLEMA APM INFOARENA: https://infoarena.ro/problema/apm
void APM();

//PROBLEMA PADURI DE MULTIMI DISJUNCTE INFOARENA: https://infoarena.ro/problema/disjoint
void disjoint();

//PROBLEMA ALGORITMUL LUI DIJKSTRA INFOARENA: https://infoarena.ro/problema/dijkstra
void Dijkstra();

//PROBLEMA ALGORITMUL BELLMAN-FORD: https://infoarena.ro/problema/bellmanford
void Bellman_Ford();

//PROBLEMA FLUX MAXIM INFOARENA: https://infoarena.ro/problema/maxflow
int maxFlow ();

//PROBLEMA ROY-FLOYD INFOARENA: https://infoarena.ro/problema/royfloyd
void Roy_Floyd();

//PROBLEMA DIAMETRUL UNUI ARBORE INFOARENA: https://infoarena.ro/problema/darb
int diameter();

//PROBLEMA CICLU EULERIAN INFOARENA: https://infoarena.ro/problema/ciclueuler
vector<int> Euler();
}g;

void Graph::DFS(int node)
{
visited[node] = 1;
output<<node<<" ";

for (int i = 0; i < adj[node].size(); i++)
    if( !visited[adj[node][i]])
        DFS(adj[node][i]);
}

void Graph::afis_adj(int node){
for (int i = 0; i < adj[node].size(); i++)
     cout<<adj[node][i]<<" ";
}

void Graph::addEdges_dg (int no_nodes, int no_edges)
{
//       int no_nodes, no_edges;
//       input>>no_nodes>>no_edges;
set_no_nodes(no_nodes);
set_no_edges(no_edges);

int node1, node2;

for(int i = 0 ; i < no_edges; i++)
{
    input>>node1>>node2;
    adj[node1].push_back(node2);
}
}

void Graph::addEdges_ug ()
{
int no_nodes;
input>>no_nodes;
set_no_nodes(no_nodes);

int node1, node2;

while (input>>node1>>node2) {
    adj[node1].push_back(node2);
    adj[node2].push_back(node1);
}
}

void Graph::addEdges_dg_weight()
{
int no_nodes, no_edges;
input>>no_nodes>>no_edges;
set_no_nodes(no_nodes);
set_no_edges(no_edges);

int node1, node2, weight;

for(int i = 0 ; i < no_edges; i++)
{
    input>>node1>>node2>>weight;
    adj_weight[node1].push_back(make_tuple(node2, weight));
}
}

void Graph::addEdges_dg_capacity()
{
int no_nodes, no_edges;
input>>no_nodes>>no_edges;
set_no_nodes(no_nodes);
set_no_edges(no_edges);

int node1, node2, capacity;
for(int i = 0 ; i < no_edges; i++)
{
    input>>node1>>node2>>capacity;
    adj_capacity[node1].push_back(make_tuple(node2, capacity));
}
}

int Graph::connectedComponents ()
{
int cc = 0;
for (int i = 1; i <= get_no_nodes(); i++)
    if (!visited[i])
    {
        cc++;
        DFS(i);
    }
return cc;
}

void Graph::BFSUtil (int node)
{
int cost[N];
queue<int> queue_bfs;

memset(cost,  -1, sizeof(cost));

visited[node] = 1; //marchez nodul curent ca vizitat
queue_bfs.push(node);
cost[node] = 0;

while (!queue_bfs.empty()) {
    node = queue_bfs.front(); //iau nodul din varful cozii
    queue_bfs.pop();

    for (int i = 0; i < adj[node].size(); i++) //parcurg toti vecinii sai
        if ( !visited[adj[node][i]]) //daca sunt nevizitati
        {
            visited[adj[node][i]] = 1;  //ii marchez ca vizitati
            queue_bfs.push(adj[node][i]);   //ii adaug in coada
            cost[adj[node][i]] = cost[node] + 1;   //calculez costul raportat la "parintele" sau
        }
}

for (int i = 1; i <= get_no_nodes(); i++)
    output<<cost[i]<<" ";
}

void Graph::BFS()
{
int no_nodes, no_edges, start;
    input>>no_nodes>>no_edges>>start;
    
    g.addEdges_dg(no_nodes, no_edges);
    g.BFSUtil(start);
}

void Graph::DFS_biconnectedComponents(int node, int parent, int level[], int low_level[], vector<vector<int>> &bcc, stack<pair<int,int>> &component_node, int &current)
{
visited[node] = 1;

level[node] = level[parent] + 1;
low_level[node] = level[node];
int child;

int dim = adj[node].size();
for ( int i = 0; i< dim ; i++)
{
    child = adj[node][i];
    if (child != parent)
    {
        if (visited[child] == true)  //daca fiul sau a fost deja parcurs si nu este tatal nodului curent, muchia (fiu,nod) este muchie de intoarcere
        {
            if(level[child] < low_level[node])low_level[node] = level[child];  //actualizam valoarea low_level[nod] daca fiul sau se afla mai sus decat el (pt ca avem muchie de intoarcere)
        }
        else //daca fiul sau nu a fost inca parcurs, continuam DFS din fiu
        {
            component_node.push({node, child});
            DFS_biconnectedComponents(child, node, level, low_level, bcc, component_node, current);

            if (low_level[child] < low_level[node])
                low_level[node] = low_level[child]; //daca la intoarcerea din apel fiul are un nivel de intoarcere mai mic decat al nodului, actualizam low_level[node]

            if (low_level[child] >= level[node])        //nodul k este pct de articulatie
            {
                bcc.push_back({});
                while( component_node.top().first != node)
                {
                    bcc.back().push_back(component_node.top().second);
                    component_node.pop();
                }
                bcc.back().push_back(component_node.top().second);
                bcc.back().push_back(component_node.top().first);
                component_node.pop();
                current++;
           }
        }
    }
}
}

void Graph::biconnectedComponents()
{
int level[N] = {0};    //nivelul la care se afla un nod
int low_level[N] = {0};    //nivelul minim de intoarcere a unui nod
stack<pair<int, int>> component_node;
vector<vector<int>> bcc; //vectorul care stocheaza componentele biconexe
int current = 0;

DFS_biconnectedComponents(1,0, level, low_level, bcc, component_node, current);

output<<current << "\n";
for (int i =0 ; i <= current; i++)
    {
        for (int j = bcc[i].size() - 1; j >= 0; j--)
            if(bcc[i][j])
                output<<bcc[i][j]<<" ";
        output<<"\n";
    }
}

void Graph::calculateIndegree (int indegree[])
{
int no_nodes, no_edges;
input>>no_nodes>>no_edges;
set_no_nodes(no_nodes);

int node1, node2;
memset(indegree, 0, no_nodes);

for(int i = 0 ; i < no_edges; i++)
{
    input>>node1>>node2;
    adj[node1].push_back(node2);
    indegree[node2]++;
}
}

void Graph::topSort(int indegree[], queue<int> queue_ts)
{
int dim = get_no_nodes();
for (int i = 1; i <= dim ; i++)  //adaugam in coada doar nodurile care au gradul 0
{
    if (indegree[i] == 0)
        queue_ts.push(i);
}

while (!queue_ts.empty()) //cat timp coada nu este goala, extragem varful, scadem gradele nodurilor adiacente cu varful si adaugam in coada acele noduri care au gradul interior 0
{
    int node = queue_ts.front();
    queue_ts.pop();

    for (int i = 0; i < adj[node].size(); i++)
    {
        int adj_node = adj[node][i];
        indegree[adj_node]--;
        if (!indegree[adj_node])
            queue_ts.push(adj_node);
    }
    cout<<node<<" ";
}
}

void Graph::topologicalSort()
{
queue<int> queue_ts; //coada in care vom adauga doar nodurile care au gradul interior 0
int indegree[N] ; //vectorul care retine gradul interior al fiecarui nod

calculateIndegree(indegree);
topSort(indegree, queue_ts);
}

bool Graph::graphExists (vector<int> degree_seq)
{
while (1) {
    sort(degree_seq.begin(), degree_seq.end(), greater<>());
    cout<<degree_seq[0]<<" ";
    if (degree_seq[0] == 0)  //daca toate elementele ramase sunt 0, atunci se poate construi un graf
        return true;

    int top = degree_seq[0];
    degree_seq.erase(degree_seq.begin());

    if (top > degree_seq.size()) // daca valoarea primului element este mare decat numarul de elemente ramase, nu putem construi un astfel de graf
        return false;

    for (int i = 0 ; i < degree_seq.size(); i++) //dupa eliminarea primului element, scadem gradul "nodurilor" ramase
    {
        degree_seq[i]--;
        if(degree_seq[i] < 0)  //daca apar numere negative, nu putem sa construim un graf
            return false;
    }
}
}

void Graph::inputArray (vector<int> &degree_seq)
{
int n;
input>>n;

for (int i = 0; i < n; i++)
{
    int val;
    input>>val;
    degree_seq.push_back(val);
}
}

void Graph::Havel_Hakimi()
{
vector<int> degree_seq; //vectorul care contine gradele unui posibil graf

inputArray(degree_seq);
output<<graphExists(degree_seq);
}

bool Graph::sortByThird (const tuple<int,int,int> &a, const tuple<int,int,int>&b)
{
return (get<2>(a) < get<2>(b));
}

void Graph::inputAPM(vector<tuple<int,int,int>> &weight_edges)
{
int no_nodes, no_edges;
input>>no_nodes>>no_edges;
set_no_nodes(no_nodes);
set_no_edges(no_edges);

for (int i = 0 ; i < no_edges; i++)
{
    int n1, n2, weight;
    input>>n1>>n2>>weight;
    weight_edges.push_back(make_tuple(n1,n2,weight));
}
}

void Graph::APMUtil(vector<tuple<int,int,int>> &weight_edges)
{
//    sort(weight_edges.begin(), weight_edges.end(), sortByTh);   //sortam vectorul crescator in functie de cost
//
//    DisjointSets djs;
//    djs.initialization(get_no_nodes());     //consideram ca fiecare nod reprezinta un subarbore
//
//    int weight = 0;     //costul arborelui
//    int ctr = 0;        //numarul de muchii ale APM intr-un anumit moment
//    vector<tuple<int,int>> apm;
//    for (int i = 0; i < get_no_edges(); i++)
//    {
//        int n1 = get<0>(weight_edges[i]);       //la fiecare iteratie alegem muchia cu cost minim
//        int n2 = get<1>(weight_edges[i]);
//
//        int r1 = djs.reprezentative(n1);        //verificam reprezentantii nodurilor incidente acestei muchii
//        int r2 = djs.reprezentative(n2);
//
//        if (r1 != r2)       //daca avem reprezentanti diferiti, subarborii din care fac parte nodurile se reunesc; altfe,l, ignoram muchia, deoarece ar genera un ciclu in APM
//        {
//            apm.push_back(make_tuple(n1, n2));
//            ctr++;
//            weight += get<2>(weight_edges[i]);
//            djs.reunite(n1, n2);
//
//            if  (ctr == get_no_nodes() - 1)      //un arbore poate avea maximum n-1 muchii intre noduri; astfel, daca am gasit n-1 muchii putem opri cautarea
//                break;
//        }
//    }
//
//    output<<weight<<"\n";
//    output<<get_no_nodes() - 1<<"\n";
//    for (int i = 0; i < apm.size(); i++)
//        output<<get<0>(apm[i])<<" "<<get<1>(apm[i])<<"\n";
}

void Graph::APM()
{
vector<tuple<int,int,int>> weight_edges;

inputAPM(weight_edges);
APMUtil(weight_edges);

}

void Graph::disjoint()
{
int height[N] = {0};
int father[N] = {0};

int no_sets, no_tasks;
input>>no_sets>>no_tasks;

DisjointSets djs;

for (int i = 0; i < no_tasks; i++)
{
    int no_task,x,y;
    input>>no_task>>x>>y;

    if (no_task == 1)
        djs.reunite(x, y, height, father);
    else
    {
        int r1 = djs.reprezentative(x, father);
        int r2 = djs.reprezentative(y, father);

        if(r1 != r2)
            output<<"NU\n";
        else output<<"DA\n";
    }
}
}

void Graph::Dijkstra()
{
int dist[N];       //vectorul care retine distanta minima de la nodul de start la celelalte noduri
int start = 1;
priority_queue<tpl, vector<tpl>, greater<tpl>> queue_adj;   //coada in care retinem nodurile adiacente si costurile muchiilor de adiacenta ale nodului vizitat curent pentru a avea ordinea parcurgerii
                                                            //vom retine mai intai costul si apoi nodul adiacent pentru a putea obtine cu usurinta la fiecare iteratie nodul care are muchia asociata de cost minim

for (int i = 1; i <= get_no_nodes(); i++)
    dist[i] = INF;

queue_adj.push(make_tuple(0, start));   //pentru nodul de start avem costul 0 pentru a ajunge la el
dist[start] = 0;

while (!queue_adj.empty()) {
    int node = get<1>(queue_adj.top());
    queue_adj.pop();

    for (int i = 0; i < adj_weight[node].size(); i++)       //pentru toate nodurile adiacente ale lui node
    {
        int child = get<0>(adj_weight[node][i]);
        int weight = get<1>(adj_weight[node][i]);

        if (dist[node] + weight < dist[child])      //verificam daca pentru nodurile adiacente gasim un drum mai scurt prin node decat cele parcurse deja
        {
            dist[child] = dist[node] + weight;
            queue_adj.push(make_tuple(dist[child], child));
        }
    }
}

for (int i = 2; i <= get_no_nodes(); i++)
    if (dist[i] == INF)
        output<<"0 ";
    else output<<dist[i]<<" ";
}

void Graph::Bellman_Ford()
{
int dist[N];  //vectorul care retine distanta minima de la nodul de start(1) la toate celelalte noduri
int len[N] = {0};  //vectorul care memoreaza lungimea unui drum de la sursa la un alt nod
queue<int> queue_bf;        //coada care memoreaza nodurile ale caror distanta minima s-a modificat
int start = 1;
bool cycle = false;        //presupunem ca in graf nu exista cicluri negative

for (int i = 1; i <= get_no_nodes(); i++)
    dist[i] = INF;

dist[start] = 0;        //pentru nodul 1 avem costul 0 pentru a ajunge la el
queue_bf.push(start);

while (!queue_bf.empty() && !cycle)
{
    int node = queue_bf.front();
    queue_bf.pop();

    for (int i = 0; i < adj_weight[node].size(); i++)  //pentru toate nodurile adiacente cu node
    {
        int child = get<0>(adj_weight[node][i]);
        int weight = get<1>(adj_weight[node][i]);

        if (dist[node] + weight < dist[child])      //verificam daca gasim un drum mai scurt decat cel parcurs deja
        {
            len[child] = len[node] + 1;
            if (len[child] == get_no_nodes())   //daca obtinem o lungime mai mare sau egala cu n, inseamna ca in graf exista un ciclu negativ
            {
                cycle = true;
                break;
            }
            dist[child] = dist[node] + weight;
            queue_bf.push(child);
        }
    }
}

if (cycle)
    output<<"Ciclu negativ!";
else
    for (int i = 2; i <= get_no_nodes(); i++)
        output<<dist[i]<<" ";
}

bool Graph::bfs_maxFlow(int src, int dst, vector<vector<int>> residualGraph, int parent[])
{
memset(visited, false, sizeof(visited));

queue<int> q;
q.push(src);
visited[src] = true;        //marcam nodul curent ca vizitat
parent[src] = 0;

while (!q.empty())
{
    int node = q.front();       //luam primul element din coada
    q.pop();
    
    for (int i = 0 ; i < adj_capacity[node].size(); i++)        //parcurg toate nodurile adiacente cu nodul curent
    {
        int j = get<0>(adj_capacity[node][i]);
        if (!visited[j] && residualGraph[node][j] > 0)
        {
            if (j == dst)       //daca am gasit un drum de la sursa la destinatie, ne oprim cu bfs_maxFlow
            {
                parent[j] = node;
                return true;
            }
            q.push(j);
            parent[j] = node;
            visited[j] = true;
        }
    }
}
return false;
}

int Graph::Edmonds_Karp(int src, int dst)
{
vector<vector<int>> residualGraph;        //cream un graf rezidual pe care il initializam cu valorile capacitatilor din graful original
                                //residualGraph[i][j] -> capacitatea arcului de la i la j, daca acesta exista
int parent[get_no_nodes() + 1];         //vectoul folosit pentru a memora drumul de la sursa la destinatie
int max_flow = 0;       //initial nu avem niciun flux
residualGraph.resize(get_no_nodes() + 1, vector<int> (get_no_nodes() + 1, 0));
for (int i = 1; i <= get_no_nodes(); i++)
    for (int j = 0; j < adj_capacity[i].size(); j++)
    {
        int col = get<0>(adj_capacity[i][j]);
        residualGraph[i][col] = get<1>(adj_capacity[i][j]);
    }

while (bfs_maxFlow(src, dst, residualGraph, parent)) {      //cat timp avem drum de la sursa la destinatie
    //cautam capacitatea reziduala minima a fiecarui arc de-a lungul drumului gasit de bfs
    int path_flow = INT_MAX;
    for (int i = dst ; i != src; i = parent[i])
    {
        int node = parent[i];
        path_flow = min(path_flow, residualGraph[node][i]);
    }
    
    //modificam valorile reziduale ale arcelor directe si inverse care se afla pe drumul gasit de bfs
    for (int i = dst ; i != src; i = parent[i])
    {
        int node = parent[i];
        residualGraph[node][i] -= path_flow;
        residualGraph[i][node] += path_flow;
    }
    max_flow += path_flow;
}
return max_flow;
}

int Graph::maxFlow()
{
addEdges_dg_capacity();
return Edmonds_Karp(1, get_no_nodes());
}

void Graph::Roy_FloydUtil(int dist[][N])
{
int n = get_no_nodes();
for (int k = 1; k <= n; k++)       //consideram pe rand fiecare nod ca fiind intermediar
    for (int i = 1; i <= n; i++)       //consideram pe rand ca fiecare nod este sursa
        for (int j = 1; j <= n; j++)       //consideram pe rand fiecare nod ca fiind destinatie
            if (dist[i][j] > (dist[i][k] + dist[k][j]) && (dist[k][j] != INF && dist[i][k] != INF)) {     //modificam distanta
                dist[i][j] = dist[i][k] + dist[k][j];
            }
}

void Graph::outputRoy_Floyd(int dist[][N])
{
for (int i = 1; i <= get_no_nodes(); i++)
{
    for (int j = 1; j <= get_no_nodes(); j++)
        if (dist[i][j] == INF || i == j)
            output<<"0 ";
        else
            output<<dist[i][j]<<" ";
    output<<"\n";
}
}

void Graph::inputRoy_Floyd(int dist[][N])
{
int no_nodes;
input>>no_nodes;
set_no_nodes(no_nodes);

for (int  i = 1; i <= no_nodes; i++)
    for (int j = 1; j <= no_nodes; j++)
{
    input>>dist[i][j];
    if (!dist[i][j]) dist[i][j] = INF;
}
}

void Graph::Roy_Floyd()
{
int dist[N][N];      // dist este matricea rezultat care contine drumul minim intre toate perechile de noduri
inputRoy_Floyd(dist);
Roy_FloydUtil(dist);
outputRoy_Floyd(dist);
}

void Graph::dfsUtil(int src, int &dst, int count, int &max_count)
{
visited[src] = true;
count++;
for (int i = 0; i < adj[src].size(); i++)
{
    if (!visited[adj[src][i]]){
        if (count >= max_count)
        {
            max_count = count;
            dst = adj[src][i];
        }
        dfsUtil(adj[src][i], dst, count, max_count);
    }
}
}

void Graph::dfs_diameter(int src, int &dst, int &max_count)
{
int count = 0;
for (int i = 1 ; i <= get_no_nodes(); i++)
    visited[i] = false;

dfsUtil(src, dst, count + 1, max_count);
}

int Graph::diameter()
{
addEdges_ug();
int max_count = INT_MIN;
int src, dst;

dfs_diameter(1, dst, max_count);
dfs_diameter(dst, src, max_count);

return max_count;
}

vector<int> Graph::EulerCircuit(vector<tpl> edges[])
{
    return {0};
}


vector<int> Graph::Euler()
{
    vector<tpl> edges[N];
    int no_nodes, no_edges;
    input>>no_nodes>>no_edges;
    set_no_edges(no_edges);
    set_no_nodes(no_nodes);

    for (int i = 0; i < no_edges; i++)
    {
        int x,y;
        input>>x>>y;
        edges[x].push_back(make_tuple(y,i));
        edges[y].push_back(make_tuple(x,i));
    }

    vector<int> eulerCircuit;
        bool eliminated[N] = {false};
    stack<int> stack_euler;
    
    for (int i = 1 ; i <= get_no_nodes(); i++)
    {
        if (edges[i].size() % 2)
        {
            eulerCircuit.push_back(-1);
            return eulerCircuit;
        }
    }

    stack_euler.push(1);
    while (!stack_euler.empty())
    {
        int node = stack_euler.top();
        if (!edges[node].empty())
        {
            auto t = edges[node].back();
            edges[node].pop_back();
            
            int adj_node = get<0>(t);
            int edge_code = get<1>(t);
            
            if (!eliminated[edge_code])
            {
                eliminated[edge_code] = true;
                stack_euler.push(adj_node);
            }
        }
        else
        {
            stack_euler.pop();
            eulerCircuit.push_back(node);
        }
    }
    return eulerCircuit;
}

int main(int argc, const char * argv[])
{
    vector<int> result;
    result = g.Euler();
    cout<<" ";

    for (int i = 0 ; i < result.size() -1 ; i++)
        output << result[i] << " ";

    return 0;
}