/*
1. BFS: https://infoarena.ro/job_detail/2797641 (100p)
2. DFS: https://infoarena.ro/job_detail/2797186  (100p)
3. CTC: https://infoarena.ro/job_detail/2798894 (100p)
4. Havel Hakimi:
5. Sortare topologica: https://infoarena.ro/job_detail/2797863  (100p)
6. Critical connections: https://leetcode.com/submissions/detail/585217368/ (Accepted)
7. Binconexe: https://infoarena.ro/job_detail/2798875 (90p)
8. Bellmanford: https://infoarena.ro/job_detail/2809092 (100p)
9. Dijkstra:  https://infoarena.ro/job_detail/2809102 (80p)
10. Paduri de multimi disjuncte: https://www.infoarena.ro/job_detail/2809108 (100p)
11. APM: https://www.infoarena.ro/job_detail/2809110 (90p)
*/

#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <stack>
#include <algorithm>

using namespace std;
#define Nmax 100007
#define max 1024
#define Rezolvare 14
#define inf   200004
#define neg_inf -200004
const char iname[] = "maxflow.in";
const char oname[] ="maxflow.out";


vector<int> rev[Nmax];
vector<int> aux;
vector <int> deg;
queue <int> coada;
vector<int> visited;
vector<int> niv_min;
vector<int> nivel,parent;
stack<int> st;
vector<vector<int> > output;
vector< pair<int,int> > node_with_cost[Nmax];
int greutate[Nmax];
int parinte[Nmax];
vector< pair < int, pair <int,int> > > muchii;
int capacitate[max][max];
int flux[max][max];

ifstream f(iname);
ofstream g(oname);

class Graph{
public:
    Graph(int n, int m);
    ~Graph();
    virtual void add_muchie(int x, int y){}
    bool is_correct_graph(vector<int> grade);
private:

protected:
    vector<int> la[Nmax]; //lista de adiacenta;
    int n,m; //numarul de noduri si numarul de muchii
};

bool Graph::is_correct_graph(vector<int> grade)
{
    sort(grade.begin(),grade.end(),greater <int>());
    while(grade[0]!=0)
    {
        int v=grade[0];
        grade.erase(grade.begin()+0);
        if(v>grade.size())
            return false;
        for(int i=0;i<v;i++)
        {
            grade[i]--;
            if(grade[i]<0)
                return false;
        }
        sort(grade.begin(),grade.end(),greater <int>());
    }
    return true;
}

class Undirected: public Graph{
public:
     Undirected(int n, int m=0);
     ~Undirected();
     void add_muchie(int x,int y)
     {
         la[x].push_back(y);
         la[y].push_back(x);
     }
     void dfs(int start,int visited[]);
     void criticalConnections(vector<vector<int>>& connections);
     void biconex();
     int find(int x);
     void unite(int x, int y);
     void kruskall();
     void dfs_darb(int start,int& maxCount);
private:
     void dfs_critical(const int cur);
     void util(const int cur,const int parent);
     void dfs_util(int start, int count, int& maxCount,bool visited[]);
};

void Undirected::dfs_darb(int start,int& maxCount)
{
    bool visited[n+1];
    for(int i=0;i<n+1;i++)
        visited[i]=false;
    int count=0;
    dfs_util(start,count+1,maxCount,visited);
}
int nod_final;
void Undirected::dfs_util(int start, int count, int& maxCount,bool visited[])
{
    visited[start] = true;
    count++;
    for(auto vecin: la[start])
    {
        if(!visited[vecin]){
            if(count>=maxCount)
            {
                maxCount = count;
                nod_final = vecin;
            }
        dfs_util(vecin,count,maxCount,visited);
        }
    }
}

void Undirected::kruskall()
{
    vector <pair <int,int> > arbore;
    int cost = 0;
    int numar_muchii = 0;
    sort(muchii.begin(),muchii.end());
    for(auto muchie:muchii)
    {
        if(find(muchie.second.second)!=find(muchie.second.first))
        {
            unite(muchie.second.second,muchie.second.first);
            cost+=muchie.first;
            numar_muchii ++;
            arbore.push_back(make_pair(muchie.second.second,muchie.second.first));
        }

    }
     g<<cost<<"\n";
     g<<numar_muchii<<"\n";
     for(int i=0;i<numar_muchii;i++)
        g<<arbore[i].first<<" "<<arbore[i].second<<"\n";
}

int indx=0;
vector <int> out[Nmax];

int Undirected::find(int x)
{
    if(parinte[x]==x) return x;
    return parinte[x] = find(parinte[x]);
}

void Undirected::unite(int x, int y)
{
    int parinte_x = find(x);
    int parinte_y = find(y);
    if(parinte_x!=parinte_y)
    {
        if(greutate[parinte_x]<greutate[parinte_y])
            swap(parinte_x,parinte_y);
        parinte[parinte_y]=parinte_x;
        greutate[parinte_x]+=greutate[parinte_y];
    }

}

void Undirected::util(const int cur,const int parent)
{
        static int time = 0;
        niv_min[cur] = nivel[cur] = ++time;
        st.push(cur);
        for(int j:la[cur])
        {
            if(!niv_min[j])
            {
                util(j,cur);
                niv_min[cur] = min(niv_min[cur],niv_min[j]);
                if(niv_min[j] >= nivel[cur])
                {
                    indx++;
                    while(st.top()!=j){
                        out[indx].push_back(st.top());
                        st.pop();
                    }

                    out[indx].push_back(st.top());
                    st.pop();
                    out[indx].push_back(cur);
                }
             }
            else
                if(j != parent)
                {
                    niv_min[cur]=min(niv_min[cur],nivel[j]);
                }
        }
}

 void Undirected::biconex()
{
    nivel.assign(n+1,-1);
    niv_min.resize(n+1);

    for(int i=0;i<n;i++)
        {
             if(!niv_min[i]){
                util(i,0);
            }
        }
    g<<indx<<endl;
    for(int i=1;i<=indx;i++)
    {
        for(auto j:out[i])
            g<<j<<" ";
        g<<endl;
    }

}
 void Undirected::dfs_critical(int cur)
    {
        static int time=0;
        visited[cur] = 1;
        niv_min[cur] = nivel[cur] = ++time;
        for(int j:la[cur])
        {
            if(!visited[j])
            {
                parent[j] = cur;
                dfs_critical(j);
                niv_min[cur] = min(niv_min[cur],niv_min[j]);
                if(niv_min[j]>nivel[cur])
                {
                    output.push_back({cur,j});
                }
             }
            else
                if(j!=parent[cur])
                    {
                        niv_min[cur]=min(niv_min[cur],nivel[j]);
                    }

        }
    }

void Undirected::criticalConnections(vector<vector<int>>& connections) {
        n=this->n;
        parent.assign(n+1,-1);
        visited.assign(n+1,0);
        niv_min.resize(n+1);
        nivel.resize(n+1);
        for(int i = 0; i < connections.size(); i++)
        {
            la[connections[i][0]].push_back(connections[i][1]);
            la[connections[i][1]].push_back(connections[i][0]);
        }
        for(int i=0;i<n;i++)
        {
             if(visited[i]==0){
                dfs_critical(i);
            }
        }

        for(int i=0;i<output.size();i++)
            cout<<output[i][0]<<" "<<output[i][1]<<endl;
    }

int nr_conex=0;
void Undirected::dfs(int start,int visited[])
{
  visited[start] = nr_conex;
  for(auto i:la[start])
  {
      if(!visited[i])
        dfs(i,visited);
  }
}

 Undirected::Undirected(int n, int m): Graph(n,m)
{

}

Undirected::~Undirected()
{

}

int visited_flux[max];
int tata[max];

class Directed: public Graph{
public:
     Directed(int n,int m);
     ~Directed();
     void add_muchie(int x,int y);
     void bfs(int start, int visited[],int dist[]);
     void findCTC();
     void reverse();
     void topologic(vector <int>& deg);
     void bellmanford_optimizat(vector< pair<int,int> > node_with_cost[Nmax],int source);
     void dijkstra(int source);
     void roy_floyd(int dist[][102]);
     int flux_bfs(int source, int sink)
     {
         queue<int> coada;
         for(int i=0;i<=n+1;i++)
            {
                visited_flux[i] = 0;
                tata[i] = 0;
            }
         visited_flux[source]=1;
         coada.push(source);

         while(!coada.empty() && tata[sink]==0){
            int cur = coada.front();
            coada.pop();
            for(auto vecin: la[cur])
            {
                if(capacitate[cur][vecin] - flux[cur][vecin]>0 && !visited_flux[vecin])
                {
                    visited_flux[vecin]=1;
                    coada.push(vecin);
                    tata[vecin]=cur;
                }
            }
         }
         return (tata[sink]?true:false);
     }

    int fluxmax()
    {
        int rasp = 0;

        while(flux_bfs(1,n)){
            for(auto vecin:la[n])
            {
                if(flux[vecin][n]!=capacitate[vecin][n] && visited_flux[vecin])
                {
                    tata[n]=vecin;
                    int fmin = inf;
                    int nod=n;
                    while(nod!=1)
                    {
                       if(capacitate[tata[nod]][nod]-flux[tata[nod]][nod]<fmin)
                            fmin = capacitate[tata[nod]][nod]-flux[tata[nod]][nod];
                       nod = tata[nod];
                    }
                    nod=n;
                    if(fmin!=0)
                    {
                        while(nod!=1)
                        {
                            flux[tata[nod]][nod] +=fmin;
                            flux[nod][tata[nod]] -=fmin;
                            nod = tata[nod];
                        }
                        rasp+=fmin;
                    }
                }
            }
        }
        g<<rasp;
    }
private:
    void dfs_plus(int i,stack<int> &my_stack,int visited[]);
    void dfs_reverse(int i,vector <int>& aux,int visited[]);

};


void Directed::roy_floyd(int dist[][102])
{
   for(int k = 1; k<=n; k++)
        for(int i=1;i<=n;i++)
            for(int j=1; j<=n;j++)
                if(dist[i][k] && dist[k][j]&& (dist[i][j]> dist[i][k] + dist[k][j] || !dist[i][j]) && i!=j)
                    dist[i][j] = dist[i][k] + dist[k][j];

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            g<<dist[i][j]<<" ";
    g<<"\n";
    }

}

void Directed::topologic(vector <int>& deg)
{
    for(int i=1;i<=n;i++)
        if(!deg[i]) coada.push(i);
    while(!coada.empty())
    {
        for(auto j:la[coada.front()])
        {
            deg[j]--;
            if(!deg[j]) coada.push(j);
        }
        g<<coada.front()<<" ";
        coada.pop();
    }
}

void Directed::dfs_reverse(int i,vector <int>& aux,int visited[])
    {
        visited[i]=1;
        for(auto j:rev[i])
        {
            if(!visited[j])
                dfs_reverse(j,aux,visited);
        }
        aux.push_back(i);
    }

void Directed::findCTC()
     {
         int visited[n];
         vector< vector<int> > sol;
         for(int i=1;i<=n;i++)
            visited[i]=0;
         stack<int> my_stack;
         for(int i=1;i<=n;i++)
            if(!visited[i])
                dfs_plus(i,my_stack,visited);



        for(int i=1;i<=n;i++)
            visited[i]=0;

         while(!my_stack.empty())
         {

             int cur = my_stack.top();
             my_stack.pop();
             if(!visited[cur])
                {
                    aux = vector<int>();
                    dfs_reverse(cur,aux,visited);
                    sol.push_back(aux);
                }
         }
         g<<sol.size()<<"\n";
         for(int i=0;i<sol.size();i++)
         {
             for(int j=0;j<sol[i].size();j++)
                g<<sol[i][j]<<" ";
          g<<"\n";
         }
     }

void Directed::reverse()
{
    for(int i=1;i<=n;i++)
    {
        for(int j:la[i])
            rev[j].push_back(i);
    }
}

void Directed::dfs_plus(int i,stack<int> &my_stack,int visited[])
{
    visited[i]=1;
    for(int j:la[i])
    {
        if(!visited[j])
            dfs_plus(j,my_stack,visited);
    }
    my_stack.push(i);
}

Directed::Directed(int n, int m): Graph(n,m)
{

}

Directed::~Directed()
{

}

void Directed::add_muchie(int x,int y)
{
    la[x].push_back(y);

}

void Directed::bfs(int start, int visited[],int dist[]){
    queue <int> coada;
    visited[start]=true;
    coada.push(start);
    dist[start] = 0;
    while(!coada.empty())
    {   start = coada.front();
        coada.pop();
        for(auto i:la[start])
        {
            if(!visited[i])
            {
                visited[i] = true;
                coada.push(i);
                dist[i]=dist[start]+1;
            }
        }
    }
}

void Directed::bellmanford_optimizat(vector< pair<int,int> > node_with_cost[Nmax],int source)
{
    vector<int> dist(n+1,inf);
    queue<int> q;
    vector<int> cnt(n+1,0);
    vector<bool> inqueue(n+1,false);

    dist[source]=0;
    q.push(source);
    inqueue[source]=true;

    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        inqueue[u] = false;

        for(auto neighbour:node_with_cost[u])
        {
            int v = neighbour.first;
            int weight = neighbour.second;

            if(dist[u]+weight<dist[v]){
                dist[v] = dist[u]+weight;
                if(!inqueue[v])
                {
                    q.push(v);
                    inqueue[v] = true;
                    cnt[v]++;
                    if(cnt[v]>n)
                        {
                            g<<"Ciclu negativ!";
                            return;
                        }
                }
            }

        }
    }
        for(int i=2;i<=n;i++)
        g<<dist[i]<<" ";
}

void Directed::dijkstra(int source)
{

    vector<int> dist(n+1,inf);
    vector<bool> visited(n+1,false);
    priority_queue<pair<int,int>,
        vector<pair<int,int>>,
        greater< pair<int,int> > > pq;

    dist[source]=0;

    pq.push(make_pair(0,source));
    while(!pq.empty())
    {
        int u=pq.top().second;
        pq.pop();
        if(visited[u]) continue;
        visited[u]=true;
        for(auto i=node_with_cost[u].begin();
            i!=node_with_cost[u].end();++i)
        {
            int v=(*i).first;
            int weight = (*i).second;
            if(dist[v]>dist[u]+weight)
            {
                dist[v]=dist[u]+weight;
                pq.push(make_pair(dist[v],v));
            }
        }
    }
    for(int i=2;i<=n;i++)
        if(dist[i]!=inf)
            g<<dist[i]<<" ";
         else g<<0<<" ";
}


Graph::Graph(int n=0, int m=0):n(n),m(m)
{

}

Graph::~Graph()
{

}



int main()
{
    int n,m,s;
    int x,y;
    switch(Rezolvare)
    {
    case 1:
    {
     f>>n>>m>>s;
     Directed grf(n,m);
     for(int i=0;i<m;i++)
     {
      f>>x>>y;
      grf.add_muchie(x,y);
     }
     f.close();
     int visited[n],dist[n];
     for(int i=0;i<=n;i++)
        visited[i]=dist[i]=0;
     grf.bfs(s,visited,dist);
     for(int i=1;i<=n;i++)
     {
         if(visited[i])
            g<<dist[i]<<" ";
        else g<<-1<<" ";
     }
        break;
    }
    case 2:
    {
     f>>n>>m;
     Undirected grf(n,m);
     int visited[n];
     for(int i=0;i<m;i++)
      {
      f>>x>>y;
      grf.add_muchie(x,y);
      }
     for(int i=0;i<=n;i++)
        visited[i]=0;
       for(int i=1;i<=n;i++)
        if(!visited[i])
         {
             nr_conex++;
             grf.dfs(i,visited);
         }
    g<<nr_conex;
    break;
    }
    case 3:
    {

     f>>n>>m;
     Directed grf(n,m);
     for(int i=0;i<m;i++)
     {
         f>>x>>y;
         grf.add_muchie(x,y);
     }
     grf.reverse();

     grf.findCTC();
     break;
    }
    case 4:
 {
    vector<int> check;
   int number;
   cin>>number;
   for(int i=0;i<number;i++)
   {
       int c;
       cin>>c;
       check.push_back(c);
   }
   Graph grf(n);
   if(grf.is_correct_graph(check))
     cout<<"DA";
   else cout<<"NU";
   break;
    }
    case 5:
        {
     f>>n>>m;
     Directed grf(n,m);
     deg = vector<int>(n+1,0);
     for(int i=0;i<m;i++)
     {

      f>>x>>y;
      grf.add_muchie(x,y);
      deg[y]++;
     }

     f.close();
     grf.topologic(deg);
     break;
        }

    case 6:
    {
       Undirected grf(4,0);
       vector<vector<int> > connections;
       connections.push_back({0,1});
       connections.push_back({1,2});
       connections.push_back({2,0});
       connections.push_back({1,3});
       grf.criticalConnections(connections);
       break;
    }
    case 7:
    {
        f>>n>>m;
        Undirected grf(n,m);

        for(int i=0;i<m;i++)
        {
            f>>x>>y;
            grf.add_muchie(x,y);
        }
        f.close();
        grf.biconex();
        break;
    }
     case 8:
    {
    f>>n>>m;
    Directed grf(n,m);
    for(int i=0;i<m;i++)
    {
        f>>x>>y>>s;
        node_with_cost[x].push_back(make_pair(y,s));

    }
    f.close();
    grf.bellmanford_optimizat(node_with_cost,1);
    break;
    }
    case 9:
    {
        f>>n>>m;
        Directed grf(n,m);
        for(int i=0;i<m;i++)
        {
            f>>x>>y>>s;
            node_with_cost[x].push_back(make_pair(y,s));
        }
        f.close();
        grf.dijkstra(1);
        break;
        }
    case 10:
        {

            f>>n>>m;
            for(int i=1;i<=n;i++){
                parinte[i]=i;
                greutate[i]=1;
            }
            Undirected grf(n,m);
            for(int i=0;i<m;i++)
            {
                f>>s>>x>>y;

                if(s==1)
                {
                    grf.unite(x,y);
                }
                else
                {
                if(grf.find(x)==grf.find(y))
                    g<<"DA\n";
                else g<<"NU\n";
                }

            }
            f.close();
            break;
        }
    case 11:
    {

        f>>n>>m;
        for(int i=1;i<=n;i++){
            parinte[i]=i;
            greutate[i]=1;
        }
        Undirected grf(n,m);
        for(int i=0;i<=m;i++)
        {
            f>>x>>y>>s;
            muchii.push_back(make_pair(s,make_pair(x,y)));
        }
        f.close();
        grf.kruskall();
        break;
        }

    case 12:
    {
        int pondere[102][102];
        f>>n;

        Directed grf(n,0);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
              {
                  f>>pondere[i][j];

              }



        grf.roy_floyd(pondere);
        break;
    }
    case 13:
        {
            f>>n;

            m = n-1;
            Undirected grf(n,m);

            for(int i=0;i<m;i++)
            {
                f>>x>>y;
                grf.add_muchie(x,y);
            }
            f.close();

            int maxCount = neg_inf;
            grf.dfs_darb(1,maxCount);

            grf.dfs_darb(nod_final,maxCount);
            g<<maxCount;
            break;
        }
    case 14:
        {
            f>>n>>m;
            Directed grf(n,m);
            for(int i=1;i<m;i++)
            {
                f>>x>>y>>s;
                capacitate[x][y] +=s;
                grf.add_muchie(x,y);
                grf.add_muchie(y,x);
            }

            grf.fluxmax();

            break;
        }
    }
    g.close();
    return 0;
}