#include <bits/stdc++.h>

using namespace std;

ifstream in("citire.in");
const int infinity = numeric_limits<int>::max();
const int infinitytMin = numeric_limits<int>::min();

// muchie de la x la y cu costul cost
struct Muchie
{
    int x, y;
    int cost = 0;
    int capacitate = -1;
    int flux = -1;

    Muchie() = default;

    Muchie(int x, int y, int cost)
    {
        this->x = x;
        this->y = y;
        this->cost = cost;
    }

    Muchie(int x, int y)
    {
        this->x = x;
        this->y = y;
    }

    Muchie(int x, int y, int flux, int capacitate)
    {
        this->x = x;
        this->y = y;
        this->flux = flux;
        this->capacitate = capacitate;
    }
};

bool comparison(Muchie m1, Muchie m2)
{
    return m1.cost < m2.cost;
}

struct Nod
{
    int nod;
    int cost = 0;
    int capacitate = -1;
    int flux = -1;

    Nod() = default;
    Nod(int nod) { this->nod = nod; }
    Nod(int nod, int cost)
    {
        this->nod = nod;
        this->cost = cost;
    }

    Nod(int nod, int flux, int capacitate)
    {
        this->nod = nod;
        this->flux = flux;
        this->capacitate = capacitate;
    }

    bool operator<(const Nod &obj) const
    {
        return this->cost > obj.cost; //> pt min-heap
    }
};

class Graf
{
public:
    int nrNoduri;
    int nrMuchii;
    vector<bool> vizitat;
    vector<int> grad_intern;
    vector<int> grad_extern;
    vector<vector<Nod>> lista_adiacenta;
    vector<Muchie> muchii;

    Graf() = default;

    Graf(int nrNoduri)
    {
        this->nrNoduri = nrNoduri;
        vizitat.resize(nrNoduri + 1);
        grad_intern.resize(nrNoduri + 1, 0);
        grad_extern.resize(nrNoduri + 1, 0);
        lista_adiacenta.resize(nrNoduri + 1);
    }
    Graf(int nrNoduri, int nrMuchii)
    {
        this->nrMuchii = nrMuchii;
        this->nrNoduri = nrNoduri;
        vizitat.resize(nrNoduri + 1);
        grad_intern.resize(nrNoduri + 1, 0);
        grad_extern.resize(nrNoduri + 1, 0);
        lista_adiacenta.resize(nrNoduri + 1);
    }
    void calculeazaGrad()
    {
        for (int nod = 1; nod <= nrNoduri; nod++)
            grad_extern[nod] = grad_intern[nod] = 0;
        for (int nod = 1; nod <= nrNoduri; nod++)
        {
            for (auto vecin : lista_adiacenta[nod])
            {
                grad_intern[vecin.nod] += 1;
                grad_extern[nod] += 1;
            }
        }
    }
    void dfs(int start, stack<int> &stiva)
    {
        vizitat[start] = true;
        for (auto vecin : lista_adiacenta[start])
        {
            if (vizitat[vecin.nod] == false)
            {
                dfs(vecin.nod, stiva);
            }
        }
        stiva.push(start);
    }

    void iterativeDFS(int start, vector<int> &tati)
    {
        int n = nrNoduri;
        vector<bool> vizitat(n + 1, false);
        stack<int> stack;
        stack.push(start);

        while (!stack.empty())
        {
            int nod = stack.top();
            stack.pop();

            if (vizitat[nod] == false)
            {
                cout << nod;
                vizitat[nod] = true;
            }

            for (auto vecin : lista_adiacenta[nod])
                if (vizitat[vecin.nod] == false)
                    stack.push(vecin.nod);
        }
    }

    void bfs(int start, vector<int> &tata)
    {
        queue<int> coada;
        coada.push(start);
        vizitat[start] = 1;
        while (!coada.empty())
        {
            int nod = coada.front();
            coada.pop();
            for (auto vecin : lista_adiacenta[nod])
            {
                if (vizitat[vecin.nod] == 0)
                {
                    coada.push(vecin.nod);
                    vizitat[vecin.nod] = 1;
                    tata[vecin.nod] = nod;
                }
            }
        }
    }

    vector<int> sortareTopologica()
    {
        vector<int> noduri_start;
        stack<int> stiva;
        for (int nod = 1; nod <= nrNoduri; nod++)
        {
            if (grad_intern[nod] == 0)
            {
                noduri_start.push_back(nod);
            }
        }

        for (auto nod : noduri_start)
        {
            dfs(nod, stiva);
        }

        vector<int> sortaretopologica;
        while (!stiva.empty())
        {
            sortaretopologica.push_back(stiva.top());
            stiva.pop();
        }
        return sortaretopologica;
    }

    void printGraf()
    {
        for (int i = 1; i <= nrNoduri; i++)
        {
            cout << i << ": ";
            for (auto nod : lista_adiacenta[i])
                cout << nod.nod << "(" << nod.cost << ") ";
            cout << endl;
        }
    }

    void printGrad()
    {
        for (int i = 1; i <= nrNoduri; i++)
        {
            cout << i << "-> grad intern = " << grad_intern[i] << ", grad extern = " << grad_extern[i] << endl;
        }
    }

    // DAG
    void DagDrumMaxim(int sursa, vector<int> &drum, vector<int> &tata)
    {
        drum.resize(nrNoduri + 1);
        tata.resize(nrNoduri + 1);
        for (int i = 1; i <= nrNoduri; i++)
        {
            drum[i] = -1;
            tata[i] = 0;
        }
        drum[sursa] = 0;
        vector<int> top = sortareTopologica();
        for (auto nod : top)
        {
            for (auto vecin : lista_adiacenta[nod])
            {
                if (drum[nod] + vecin.cost > drum[vecin.nod])
                {
                    drum[vecin.nod] = drum[nod] + vecin.cost;
                    tata[vecin.nod] = nod;
                }
            }
        }
    }

    void Djikstra(int sursa, vector<int> &drum, vector<int> &tata)
    {
        drum.clear();
        tata.clear();
        drum.resize(nrNoduri + 1);
        tata.resize(nrNoduri + 1);
        for (int i = 1; i <= nrNoduri; i++)
        {
            drum[i] = infinity;
            tata[i] = 0;
        }
        drum[sursa] = 0;

        auto cmp = [&](int nod1, int nod2)
        { return drum[nod1] > drum[nod2]; };
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);

        // daca am adaugat o sursa imaginara si doresc sa pornesc din locuri multiple :
        // for (int i = 1; i <= nrNoduri; i++)
        //     pq.push(i);

        pq.push(sursa);
        while (!pq.empty())
        {
            int nod = pq.top();
            pq.pop();

            for (auto vecin : lista_adiacenta[nod])
            {
                if (drum[nod] + vecin.cost < drum[vecin.nod])
                {
                    drum[vecin.nod] = drum[nod] + vecin.cost;
                    pq.push(vecin.nod);
                    tata[vecin.nod] = nod;
                }
            }
        }
    }

    // intoarce false daca contine circuit negativ, true daca nu
    bool BellmanFord(int sursa, vector<int> &drum, vector<int> &tata, int &negativStart)
    {
        drum.resize(nrNoduri + 1);
        tata.resize(nrNoduri + 1);
        for (int i = 1; i <= nrNoduri; i++)
        {
            drum[i] = infinity;
            tata[i] = 0;
        }
        drum[sursa] = 0;
        for (int k = 1; k <= nrNoduri - 1; k++)
        {
            for (auto muchie : muchii)
            {
                if (drum[muchie.x] < infinity && drum[muchie.x] + muchie.cost < drum[muchie.y])
                {
                    drum[muchie.y] = drum[muchie.x] + muchie.cost;
                    tata[muchie.y] = muchie.x;
                }
            }
        }
        // a n a rulare a algoritmului pentru a detecta ciclul negativ
        for (auto muchie : muchii)
        {
            if (drum[muchie.x] < infinity && drum[muchie.x] + muchie.cost < drum[muchie.y])
            {
                drum[muchie.y] = drum[muchie.x] + muchie.cost;
                tata[muchie.y] = muchie.x;
                negativStart = muchie.y;
                return false;
            }
        }
        return true;
    }

    // BellmanFord cu queue -> mai rapid decat primul
    bool BellmanFord2(int sursa, vector<int> &drum, vector<int> &tata, int &negativStart)
    {
        drum.resize(nrNoduri + 1);
        tata.resize(nrNoduri + 1);
        for (int i = 1; i <= nrNoduri; i++)
        {
            drum[i] = infinity;
            tata[i] = 0;
        }
        drum[sursa] = 0;
        vector<bool> inQueue(nrNoduri + 1, false);
        queue<int> q;
        q.push(sursa);
        inQueue[sursa] = true;
        vector<int> lungime(nrNoduri + 1, 0);
        while (!q.empty())
        {
            int nod = q.front();
            q.pop();
            inQueue[nod] = false;
            for (auto vecin : lista_adiacenta[nod])
            {
                if (drum[nod] < infinity && drum[nod] + vecin.cost < drum[vecin.nod])
                {
                    drum[vecin.nod] = drum[nod] + vecin.cost;
                    tata[vecin.nod] = nod;
                    if (inQueue[vecin.nod] == false)
                    {
                        q.push(vecin.nod);
                        inQueue[vecin.nod] = true;
                    }
                    lungime[vecin.nod] = lungime[nod] + 1;
                    if (lungime[vecin.nod] > nrNoduri - 1)
                    {
                        negativStart = vecin.nod;
                        return false;
                    }
                }
            }
        }
        return true;
    }

    void afisareDrum(int start, int end, vector<int> tata)
    {
        // cout << start << " " << end << endl;
        // for (int i = 1; i <= nrNoduri; i++)
        //     cout << tata[i] << " ";
        // cout << endl;
        vector<int> drum;
        if (start != end) // daca e circuit nu trebuie sa punem finalul de 2 ori
            drum.push_back(end);
        while (tata[end] != start)
        {
            end = tata[end];
            drum.push_back(end);
        }
        drum.push_back(start);
        for (int i = drum.size() - 1; i >= 0; i--)
            cout << drum[i] << " ";
    }

    // daca dupa algoritm avem drumuri[i][i] < 0 pentru un i => circuit negativ
    // am decis ca daca nu exista drum atunci in matrice e 0
    // de asemenea drumuri[i][i] = lantul minim folosin cel putin un arc sau infinit daca nu exista un
    // lant de lungime nevida de la i la i ( circuit practic )
    void FloydWarshall(vector<vector<int>> &drumuri, vector<vector<int>> &predecesor)
    {
        drumuri.resize(nrNoduri + 1);
        predecesor.resize(nrNoduri + 1);
        for (int nod = 1; nod <= nrNoduri; nod++)
        {
            drumuri[nod].resize(nrNoduri + 1, infinity);
            predecesor[nod].resize(nrNoduri + 1, 0);
            for (auto vecin : lista_adiacenta[nod])
            {
                drumuri[nod][vecin.nod] = vecin.cost;
                predecesor[nod][vecin.nod] = nod;
            }
        }
        // for (int i = 1; i <= nrNoduri; i++)
        //     drumuri[i][i] = 0;
        for (int k = 1; k <= nrNoduri; k++)
        {
            for (int i = 1; i <= nrNoduri; i++)
            {
                for (int j = 1; j <= nrNoduri; j++)
                {
                    if (drumuri[i][k] < infinity && drumuri[k][j] < infinity)
                    {
                        if (drumuri[i][j] > drumuri[i][k] + drumuri[k][j])
                        {
                            drumuri[i][j] = drumuri[i][k] + drumuri[k][j];
                            predecesor[i][j] = predecesor[k][j];
                        }
                    }
                }
            }
        }

        for (int i = 1; i <= nrNoduri; i++)
        {
            for (int j = 1; j <= nrNoduri; j++)
            {
                if (drumuri[i][j] == infinity)
                    drumuri[i][j] = 0; // nu exista drum
            }
        }
    }

    void drumMat(int x, int y, vector<vector<int>> predecesor)
    {
        if (x != y)
            drumMat(x, predecesor[x][y], predecesor);
        cout << y << " ";
    }

    void afisCircuitMat(int x, int y, vector<vector<int>> predecesor)
    {
        if (predecesor[x][y] != x)
            afisCircuitMat(x, predecesor[x][y], predecesor);
        cout << y << " ";
    }

    void afisareDrumuriMat(vector<vector<int>> drumuri, vector<vector<int>> predecesor)
    {
        for (int i = 1; i <= nrNoduri; i++)
        {
            cout << i << ": \n";
            for (int j = 1; j <= nrNoduri; j++)
            {
                cout << "       " << j << ": ";
                if (drumuri[i][j] == 0)
                    cout << "nu exista drum\n";
                else
                {
                    drumMat(i, j, predecesor);
                    cout << " cu costul: " << drumuri[i][j] << endl;
                }
            }
        }
    }

    long long Prim(int start, vector<Muchie> &muchiiApcm)
    {
        vector<int> d(nrNoduri + 1, infinity);
        vector<int> tata(nrNoduri + 1, -1);
        vector<bool> inHeap(nrNoduri + 1, true);

        auto cmp = [&](int nod1, int nod2)
        { return d[nod1] > d[nod2]; };
        priority_queue<Nod> minHeap;

        d[start] = 0;
        minHeap.push(Nod(start, d[start]));

        while (!minHeap.empty())
        {
            Nod u = minHeap.top();
            minHeap.pop();
            inHeap[u.nod] = false;

            for (auto vecin : lista_adiacenta[u.nod])
            {
                if (inHeap[vecin.nod] && vecin.cost < d[vecin.nod])
                {
                    d[vecin.nod] = vecin.cost;
                    tata[vecin.nod] = u.nod;
                    minHeap.push(Nod(vecin.nod, d[vecin.nod]));
                }
            }
        }
        long long cost = 0;
        for (int i = 1; i <= nrNoduri; i++)
            if (i != start)
            {
                muchiiApcm.push_back(Muchie(i, tata[i]));
                cost += d[i];
            }
        return cost;
    }

    int Repr(int x, vector<int> &tata)
    {
        if (tata[x] == 0)
            return x;
        tata[x] = Repr(tata[x], tata);
        return tata[x];
    }

    void Union(int x, int y, vector<int> &tata, vector<int> &h)
    {
        int rx, ry;
        rx = Repr(x, tata);
        ry = Repr(y, tata);
        if (h[rx] > h[ry])
        {
            tata[ry] = rx;
        }
        else
        {
            tata[rx] = ry;
            if (h[rx] == h[ry])
                h[rx] = h[ry] + 1;
        }
    }

    long long Kruskal(vector<Muchie> &apcm, vector<vector<Nod>> &apcmListaAdiacenta, vector<int> &tata)
    {
        sort(muchii.begin(), muchii.end(), comparison);
        tata.clear();
        tata.resize(nrNoduri + 1, 0);
        vector<int> inaltime(nrNoduri + 1, 0);
        apcmListaAdiacenta.clear();
        apcm.clear();
        apcmListaAdiacenta.resize(nrNoduri + 1);

        int nrSelectii = 0;
        long long costTotal = 0;

        for (auto muchie : muchii)
        {
            if (Repr(muchie.x, tata) != Repr(muchie.y, tata))
            {
                apcm.push_back(muchie);
                apcmListaAdiacenta[muchie.x].push_back(Nod(muchie.y, muchie.cost));
                apcmListaAdiacenta[muchie.y].push_back(Nod(muchie.x, muchie.cost));
                costTotal += muchie.cost;
                Union(muchie.x, muchie.y, tata, inaltime);
                nrSelectii += 1;
                if (nrSelectii == nrNoduri - 1)
                    return costTotal;
            }
        }
        return -1;
    }

    void dfsNivel(int i, vector<int> &nivel, vector<int> &nivel_min, vector<int> &tata)
    {
        vizitat[i] = true;
        nivel_min[i] = nivel[i];
        for (auto vecin : lista_adiacenta[i])
        {
            if (vizitat[vecin.nod] == false) // i -> vecin muchie de avansare
            {
                tata[vecin.nod] = i;
                nivel[vecin.nod] = nivel[i] + 1;
                dfsNivel(vecin.nod, nivel, nivel_min, tata);

                nivel_min[i] = min(nivel_min[vecin.nod], nivel_min[i]);

                // if (nivel_min[vecin.nod] > nivel[i])
                //     cout << i << " " << vecin.nod << endl;
            }
            else if (nivel[vecin.nod] < nivel[i] - 1) // i -> vecin muchie de intoarcere
                nivel_min[i] = min(nivel_min[i], nivel[vecin.nod]);
            // else if (nivel[vecin.nod] > nivel[i])
            // {
            //     nivel_min[i] = min(nivel_min[i], nivel_min[vecin.nod]);
            // }
        }
    }

    void muchiiCritice()
    {
        vector<int> nivel(nrNoduri + 1, 0), nivel_min(nrNoduri + 1, 0), tata(nrNoduri + 1, -1);
        dfsNivel(1, nivel, nivel_min, tata);
        for (int i = 1; i <= nrNoduri; i++)
        {
            if (tata[i] != -1 && nivel_min[i] > nivel[tata[i]])
                cout << tata[i] << " " << i << endl;
        }
    }

    void puncteCritice()
    {

        vector<int> nivel(nrNoduri + 1, 0), nivel_min(nrNoduri + 1, 0), tata(nrNoduri + 1, -1);
        for (int i = 1; i <= nrNoduri; i++)
            vizitat[i] = false;
        dfsNivel(1, nivel, nivel_min, tata);
        int nrfii = 0;
        for (int i = 1; i <= nrNoduri; i++)
            if (tata[i] == 1)
                nrfii++;

        if (nrfii >= 2)
            cout << 1 << endl;
        for (int i = 2; i <= nrNoduri; i++)
        {
            bool este = false;
            for (auto vecin : lista_adiacenta[i])
            {
                if (nivel_min[vecin.nod] >= nivel[i] && tata[vecin.nod] == i)
                {
                    este = true;
                    break;
                }
            }
            if (este)
                cout << i << " ";
        }
    }

    void dfsBiconex(int i, vector<int> &nivel, vector<int> &nivel_min, stack<Muchie> &stiva)
    {
        vizitat[i] = true;
        nivel_min[i] = nivel[i];
        for (auto vecin : lista_adiacenta[i])
        {
            if (vizitat[vecin.nod] == false) // ij -> vecin muchie de avansare
            {
                nivel[vecin.nod] = nivel[i] + 1;
                stiva.push(Muchie(i, vecin.nod));
                dfsBiconex(vecin.nod, nivel, nivel_min, stiva);

                nivel_min[i] = min(nivel_min[vecin.nod], nivel_min[i]);

                if (nivel_min[vecin.nod] >= nivel[i])
                {
                    // adica avem punct critic
                    // cout << i << endl; pct critice cu radacina ( nu e neaparat )
                    Muchie top = stiva.top();
                    while (!(top.x == i && top.y == vecin.nod))
                    {
                        cout << top.x << " " << top.y << endl;
                        stiva.pop();
                        top = stiva.top();
                    }
                    cout << top.x << " " << top.y << endl;
                    stiva.pop();
                    cout << endl;
                }
            }
            else if (nivel[vecin.nod] < nivel[i] - 1) // i -> vecin muchie de intoarcere
            {
                nivel_min[i] = min(nivel_min[i], nivel[vecin.nod]);
                stiva.push(Muchie(i, vecin.nod));
            }
            // else if (nivel[vecin.nod] > nivel[i])
            // {
            //     nivel_min[i] = min(nivel_min[i], nivel_min[vecin.nod]);
            // }
        }
    }

    void componenteBiconexe()
    {

        vector<int> nivel(nrNoduri + 1, 0), nivel_min(nrNoduri + 1, 0);
        stack<Muchie> stiva;
        for (int i = 1; i <= nrNoduri; i++)
            vizitat[i] = false;
        dfsBiconex(1, nivel, nivel_min, stiva);
        while (!stiva.empty())
        {
            cout << stiva.top().x << " " << stiva.top().y << endl;
            stiva.pop();
        }
    }

    void removeMuchie(int x, int y)
    {
        int found = -1;
        for (int i = 0; i < lista_adiacenta[x].size() && found == -1; i++)
            if (lista_adiacenta[x][i].nod == y)
                found = i;
        if (found != -1)
            lista_adiacenta[x].erase(lista_adiacenta[x].begin() + found);
        found = -1;
        for (int i = 0; i < lista_adiacenta[y].size() && found == -1; i++)
            if (lista_adiacenta[y][i].nod == x)
                found = i;
        if (found != -1)
            lista_adiacenta[y].erase(lista_adiacenta[y].begin() + found);
        calculeazaGrad();
        nrMuchii -= 1;
        found = -1;
        for (int i = 0; i < muchii.size() && found == -1; i++)
            if (muchii[i].x == x && muchii[i].y == y)
                found = i;
        if (found != -1)
            muchii.erase(muchii.begin() + found);
    }

    void colorare()
    {
        for (int i = 1; i <= nrNoduri; i++)
            vizitat[i] = false;
        calculeazaGrad();
        queue<int> coada;
        for (int i = 1; i <= nrNoduri; i++)
            if (grad_intern[i] <= 5)
            {
                coada.push(i);
                vizitat[i] = true;
            }
        stack<int> stiva;
        while (!coada.empty())
        {
            int nod = coada.front();
            coada.pop();
            stiva.push(nod);
            for (auto vecin : lista_adiacenta[nod])
            {
                grad_intern[vecin.nod] -= 1;
                grad_extern[vecin.nod] -= 1;
                if (grad_intern[vecin.nod] <= 5 && vizitat[vecin.nod] == false)
                {
                    vizitat[vecin.nod] = true;
                    coada.push(vecin.nod);
                }
            }
        }
        vector<int> sortare;
        while (!stiva.empty())
        {
            sortare.push_back(stiva.top());
            stiva.pop();
        }
        for (auto nod : sortare)
            cout << nod << " "; // ordinea in care le coloram cu una dintre cele 6 culori nefolosita de vecin
    }

    Graf transpunere()
    {
        Graf t(nrNoduri, nrMuchii);
        for (auto muchie : muchii)
        {
            int x = muchie.x, y = muchie.y, cost = muchie.cost;
            t.muchii.push_back(Muchie(y, x, cost));
            t.lista_adiacenta[y].push_back(Nod(x, cost));
        }
        return t;
    }

    int lantHamiltonianCostMinim()
    {

        vector<vector<int>> drumuri;
        vector<vector<int>> pred;
        FloydWarshall(drumuri, pred);
        int nrsubm = 1 << nrNoduri;
        vector<vector<int>> dp(nrNoduri, vector<int>(nrsubm, infinity));
        for (int i = 0; i < nrNoduri; i++)
            dp[i][1 << i] = 0;
        // dp[0][1] = 0;

        for (int s = 0; s < nrsubm; s++)
        {
            for (int i = 0; i < nrNoduri; i++)
            {
                int nod = i + 1;
                if (s & (1 << i))
                {
                    for (int j = 0; j < nrNoduri; j++)
                    // for (auto vecin : lista_adiacenta[nod])
                    {
                        // int j = vecin.nod - 1;
                        if (j != i && ((s & (1 << j)) != 0) && dp[j][s ^ (1 << i)] != infinity) //
                        {
                            // dp[i][s] = true;

                            int cost = drumuri[j + 1][i + 1];
                            // int cost = 0;
                            if (dp[i][s] > dp[j][s ^ (1 << i)] + cost)
                            {
                                // if (drumuri[j + 1][i + 1] != 0) // daca exista de la j+1 la i+1
                                dp[i][s] = dp[j][s ^ (1 << i)] + drumuri[i + 1][j + 1];
                            }
                        }
                    }
                }
            }
        }
        int minim = infinity;
        for (int i = 0; i < nrNoduri; i++)
        {
            // if (dp[i][nrsubm - 1] == true)
            // return 1;
            minim = min(minim, dp[i][nrsubm - 1]);
        }
        for (int i = 0; i < nrNoduri; i++)
        {
            for (int j = 0; j < nrsubm; j++)
                if (dp[i][j] != infinity)
                    cout << dp[i][j] << " ";
                else
                    cout << -1 << " ";
            cout << endl;
        }
        return (minim == infinity) ? -1 : minim;
    }

    // Kosaraju
    void componenteTareConexe()
    {
        stack<int> stiva;
        Graf transpus = transpunere();
        for (int i = 1; i <= nrNoduri; i++)
            vizitat[i] = false;
        for (int i = 1; i <= nrNoduri; i++)
            if (vizitat[i] == false)
                dfs(i, stiva);
        for (int i = 1; i <= nrNoduri; i++)
            vizitat[i] = false;

        while (!stiva.empty())
        {
            int nod = stiva.top();
            stiva.pop();
            stack<int> stivaTranspus;

            if (transpus.vizitat[nod] == false)
            {
                transpus.dfs(nod, stivaTranspus);
                while (!stivaTranspus.empty())
                {
                    cout << stivaTranspus.top() << " ";
                    stivaTranspus.pop();
                }
                cout << endl;
            }
        }
    }
};

// bipartit ++ daca e atribuie culori
void dfs2(int start, int culoare, vector<int> &culori, vector<bool> &vizitat, vector<vector<int>> ma, bool &bipartit)
{
    vizitat[start] = true;
    culori[start] = culoare;
    for (int vecin = 1; vecin < ma[start].size(); vecin++)
    {
        if (ma[start][vecin] == 1)
        {
            if (vizitat[vecin] == false)
            {
                dfs2(vecin, 1 - culoare, culori, vizitat, ma, bipartit);
            }
            else
            {
                if (culori[vecin] == culori[start])
                {
                    bipartit = false;
                }
            }
        }
    }
}

bool bipartit(vector<vector<int>> ma, int n, vector<int> &culori)
{
    vector<bool> vizitat(n + 1, false);
    bool bipartit = true;
    dfs2(1, 0, culori, vizitat, ma, bipartit);
    return bipartit;
}

// muchii da sau nu in apcm
void dfsApcm(int start, int level, vector<bool> &vizitat, vector<int> &nivel, vector<int> &cost, vector<int> &tata, vector<vector<Nod>> &apcm)
{
    vizitat[start] = true;
    nivel[start] = level;
    // cout << start << " ";
    for (auto muchie : apcm[start])
    {
        if (vizitat[muchie.nod] == false)
        {
            tata[muchie.nod] = start;
            cost[muchie.nod] = muchie.cost;
            dfsApcm(muchie.nod, level + 1, vizitat, nivel, cost, tata, apcm);
        }
    }
}

int get_radacina(int x, vector<int> &tata)
{
    while (tata[x] > 0)
        x = tata[x];
    return x;
}

int intersectie(int x, int y, vector<int> &tata, vector<int> &nivel, vector<int> &cost)
{
    int maxim = 0;
    if (nivel[x] > nivel[y])
        swap(x, y);
    while (nivel[x] < nivel[y])
    {
        maxim = max(maxim, cost[y]);
        y = tata[y];
    }
    while (x != y)
    {
        maxim = max(maxim, max(cost[x], cost[y]));
        x = tata[x];
        y = tata[y];
    }
    return maxim;
}

void interogariAPCM()
{
    int n, m;
    cin >> n >> m;
    Graf g(n, m);
    vector<Muchie> aux;
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        g.lista_adiacenta[x].push_back(Nod(y, c));
        g.lista_adiacenta[y].push_back(Nod(x, c));
        g.muchii.push_back(Muchie(x, y, c));
    }
    aux = g.muchii;
    vector<Muchie> apcm;
    vector<vector<Nod>> apcmLa;
    vector<int> tata;
    g.Kruskal(apcm, apcmLa, tata);

    vector<int> nivel(g.nrNoduri + 1, 0);
    vector<int> cost(g.nrNoduri + 1, 0);

    int radacina = get_radacina(1, tata);

    // for (int i = 1; i <= n; i++)
    // {
    //     cout << i << ": ";
    //     for (auto v : apcmLa[i])
    //         cout << v.nod << " ";
    //     cout << endl;
    // }

    vector<bool> vizitat(g.nrNoduri + 1, false);
    dfsApcm(radacina, 1, vizitat, nivel, cost, tata, apcmLa);

    int q;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int poz;
        cin >> poz;
        Muchie muchie = aux[poz - 1];
        if (muchie.cost == intersectie(muchie.x, muchie.y, tata, nivel, cost))
            cout << "Da\n";
        else
            cout << "Nu\n";
        // cout << muchie.x << " " << muchie.y << "(" << muchie.cost << ")";
        // cout << ": " << getMaximCostIntersection(muchie.x, muchie.y, tata, nivel, cost);
        // cout << endl;
    }
}

// ciclu eulerian
void euler(int v, Graf &g, vector<int> &ciclu)
{
    while (g.grad_intern[v] > 0)
    {
        int vecin = g.lista_adiacenta[v][0].nod;
        g.removeMuchie(v, vecin);
        euler(vecin, g, ciclu);
    }
    ciclu.push_back(v);
}
void cicluEulerian(int v, Graf g)
{
    g.calculeazaGrad();
    vector<int> ciclu;
    euler(1, g, ciclu);
    for (auto c : ciclu)
        cout << c << " ";
}

// flux edmond karp

bool bfsFlux(vector<vector<int>> &grafRezidual, vector<int> &tata, int start, int end)
{
    int n = grafRezidual.size() - 1;
    vector<bool> vizitat(n + 1, false);
    queue<int> coada;

    coada.push(start);
    vizitat[start] = true;
    tata[start] = -1;
    while (!coada.empty())
    {
        int nod = coada.front();
        coada.pop();

        for (int vecin = 1; vecin <= n; vecin++)
        {
            if (vizitat[vecin] == false && grafRezidual[nod][vecin] > 0)
            {

                coada.push(vecin);
                tata[vecin] = nod;
                vizitat[vecin] = true;

                if (vecin == end)
                    return true;
            }
        }
    }
    return false;
}

void dfs(int start, vector<vector<int>> graf, vector<bool> &vizitat)
{
    // cout << start << " ";
    vizitat[start] = true;
    int n = graf.size() - 1;
    // cout << n;
    for (int i = 1; i <= n; i++)
    {
        if (vizitat[i] == false && graf[start][i] > 0)
        {
            dfs(i, graf, vizitat);
        }
    }
}

// pt flux maxim cost minim putem pune muchia respectiva din graful rezidual va avea costul -cost ( unde cost = costul muchiei in graful normal)
// apoi la fiecare pas din edmondsKarp determinam lantul rezidual de cost minim folosind bellman ford => ok
int edmondsKarp(int start, int end, vector<vector<int>> capacitate, vector<vector<int>> &flux, vector<bool> &taietura)
{
    int n = capacitate.size() - 1;
    vector<vector<int>> grafRezidual = capacitate;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            grafRezidual[i][j] -= flux[i][j];
            grafRezidual[j][i] += flux[i][j];
        }
    }

    vector<int> tata(n + 1);

    while (bfsFlux(grafRezidual, tata, start, end))
    {
        int fluxRez = infinity;
        for (int nod = end; nod != start; nod = tata[nod])
        {
            // tata[nod] -> nod
            fluxRez = min(fluxRez, grafRezidual[tata[nod]][nod]);
        }
        for (int nod = end; nod != start; nod = tata[nod])
        {
            // tata[nod] -> nod
            grafRezidual[tata[nod]][nod] -= fluxRez;
            grafRezidual[nod][tata[nod]] += fluxRez;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (capacitate[i][j] >= 0)
                flux[i][j] = capacitate[i][j] - grafRezidual[i][j];
            else
                flux[i][j] = 0;
        }
    }
    taietura.resize(n + 1);
    for (int i = 0; i < taietura.size(); i++)
        taietura[i] = false;

    dfs(start, grafRezidual, taietura);
    int fmax = 0;
    // for (int i = 0; i < taietura.size(); i++)
    //     cout << taietura[i] << " ";
    // cout << endl;
    for (int i = 1; i <= n; i++)
        fmax += flux[start][i];
    return fmax;
}

// dist levensthein - pt clustering in k facem Kruskal pana la n-k cu costul
// distanta levenshtein

int levenshteinDist(string cuv1, string cuv2)
{
    int n = cuv1.length();
    int m = cuv2.length();
    int c[n + 1][m + 1];
    c[0][0] = 0;
    for (int i = 1; i <= n; i++)
        c[i][0] = i;
    for (int i = 1; i <= m; i++)
        c[0][i] = i;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (cuv1[i - 1] == cuv2[j - 1])
                c[i][j] = c[i - 1][j - 1];
            else
            {
                c[i][j] = 1 + min(c[i - 1][j], min(c[i - 1][j - 1], c[i][j - 1]));
            }
        }
    }

    // for (auto it : listaMuchii)
    // {

    //     if (Repr(it.x, tata) != Repr(it.y, tata))
    //     {

    //         solutie.push_back(it);
    //         Union(it.x, it.y, n, tata, h);
    //         nrmsel += 1;
    //         if (nrmsel == n - k)
    //             break;
    //     }
    // }
    // for (int i = 1; i <= n; i++)
    // {
    //     cout << noduri[i].s << " " << Repr(i, tata) << endl; -> s reprezinta string ( salvez nodurile cu string pentru a le putea afisa )
    // }
    // gradul de separare este costul urmatoarei muchii pe care am fi ales-o
    return c[n][m];
}

int main()
{
    int n, m, k;
    in >> n >> m >> k;
    int start = n + 1;
    n++;
    // nodul n+1 e sursa imaginara
    Graf g(n, m);
    for (int i = 1; i <= k; i++)
    {
        int nod;
        in >> nod;
        g.lista_adiacenta[start].push_back(Nod(nod, 1));
        g.muchii.push_back(Muchie(start, nod, 1));
    }
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        in >> x >> y;
        g.lista_adiacenta[x].push_back(Nod(y, 1));
        // g.lista_adiacenta[y].push_back(Nod(x, 1));
        g.muchii.push_back(Muchie(x, y, 1));
    }
    vector<int> tata;
    vector<int> drum;
    g.calculeazaGrad();
    g.DagDrumMaxim(start, drum, tata);
    int imx = 1;
    for (int i = 2; i <= n; i++)
        if (drum[imx] < drum[i])
            imx = i;
    cout << drum[imx] - 1 << endl;
    vector<int> d;
    while (tata[imx] != 0)
    {
        d.push_back(imx);
        imx = tata[imx];
    }
    for (int i = d.size() - 1; i >= 0; i--)
        cout << d[i] << " ";
    return 0;
}