#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <bits/stdc++.h>
#include<algorithm>
 
using namespace std;
typedef pair<int,int> p;

class grafMare
{
    int N,M;
    bool orientat;
    vector <int> graf[100001];
    public:
        grafMare(int n=0, int m=0, bool orientat=false);    
        void citire_graf(istream &fin);
        int get_N();
        
        void actualDFS(int, int[]);
        void BFS(int, int[]);
        void DFS_biconex(int,int,int,int&,vector<int>(&biconex)[100001],int[],int[],stack<int>&node_order);
        void CTCelp(istream &fin, vector<int>(&)[100001]);
        void DFS_CTC_1(int, int[], stack<int>&);
        void DFS_CTC_2(int, int[], vector<int>(&sol_ctc)[100001], int&,vector<int>ctc[100001]);
        void DFS_top(int, int[], vector<int>&);
        void critice(int, int, int, int[], int[], vector<vector<int>>&sol);
        bool helsinki(vector<int>&);
        void citire_helsinki();
        int radacina(int,int[]);
        void combine(int,int,int[],int[]);
        void pmd_out(int[],int[],istream &fin,ofstream &fout);
        void combine_apm_kruskal(int,int,int[]);
        void citire_apm_kruskal(istream &fin,ofstream &fout);
        void dijkstra(istream &fin,ofstream &fout);
        void bellman(istream &fin,ofstream &fout);
        void darbBFS(int,int&,int&);
        void Euler(vector<int>&sol, vector<vector<pair<int,int>>>graf);
};
grafMare::grafMare(int n, int m, bool ornt)
{
    N=n;
    M=m;
    orientat=ornt;
}
void grafMare::citire_graf(istream &fin)
{
    int a,b;
    for(int i=0;i<M;i++)
    {
        fin>>a>>b;
        graf[a].push_back(b);
        if(!orientat)
            graf[b].push_back(a);
    }
}	
int grafMare::get_N()
{
    return N;
}
void grafMare::CTCelp(istream &fin, vector<int>(&ctc)[100001])
{
    for(int i=0;i<M;i++)
    {
        int a,b;
        fin>>a>>b;
        graf[a].push_back(b);
        ctc[b].push_back(a);
    }
}
void grafMare::actualDFS(int index, int viz[])
{
    for(int vecin : graf[index])
        if(!viz[vecin])
        {
            viz[vecin]=1;
            actualDFS(vecin, viz);
        }
}
void grafMare::BFS(int start, int sol[])
{
    queue <int> q;
    q.push(start);
    sol[start]=0;
 
    while(!q.empty())
    {
        int first=q.front();
        q.pop();
        for(int vecin : graf[first])
        {
            if(sol[vecin]==-1)
            {
                sol[vecin]=sol[first]+1;
                q.push(vecin);
            }
        }
    }
}
void grafMare::DFS_biconex(int current_node, int current_pos, int tata_node, int &counter, vector<int>(&biconex)[100001],
                            int min_pos[], int first_value[], stack<int>&node_order)
{
    min_pos[current_node]=current_pos;
    first_value[current_node]=current_pos;
    node_order.push(current_node);
    for(auto i : graf[current_node])
    {
        if(!min_pos[i]) //dfs
        {   
            DFS_biconex(i, current_pos+1, current_node,counter,biconex,min_pos,first_value,node_order);
            min_pos[current_node]=min(min_pos[current_node],min_pos[i]);
            // actualizez levelul minim in caz ca baiatul urmator are traseu mai scurt de la un nod mai devreme, dupa ce intra in else if(desen 2, 7-8, 1-8)
            if(min_pos[i] >= current_pos) // asta e punct de articulatie, daca n ar respecta cond asta, ins ca exista alt traseu care mentine conditia cu conex
            {
                counter++;
                //current_node e first si i duce la ult elem din stack
                while(node_order.top()!=i)
                {
                    biconex[counter].push_back(node_order.top());
                    node_order.pop();
                }
                biconex[counter].push_back(node_order.top());
                node_order.pop();
                biconex[counter].push_back(current_node);
            }
        }
        else if(i!=tata_node)
            min_pos[current_node]=min(min_pos[current_node],first_value[i]);
    }
}
void grafMare::DFS_CTC_1(int current_node, int viz[], stack<int>&node_order)
{
    viz[current_node]=1;
    for(auto x : graf[current_node])
        if(!viz[x])
            DFS_CTC_1(x, viz, node_order);
    node_order.push(current_node);
}
void grafMare::DFS_CTC_2(int current_node, int viz[], vector<int>(&sol_ctc)[100001], int &counter, vector<int>ctc[100001])
{
    viz[current_node]=2;
    sol_ctc[counter].push_back(current_node);
    for(auto x : ctc[current_node])
        if(viz[x]==1)
            DFS_CTC_2(x, viz, sol_ctc, counter,ctc);
}
void citireDFS(string in, string out)
{   
    ifstream fin(in);
    ofstream fout(out);
    int N,M;
    fin>>N>>M;
    grafMare gm(N,M);
    gm.citire_graf(fin);
    int viz[100001];
    for(int i=0;i<N+1;i++)
        viz[i]=0;
    int counter=0;
    for(int i=1;i<N+1;i++)
        if(!viz[i])
        {
            counter++;
            gm.actualDFS(i,viz);
        }
    fout<<counter;
}
void citireBFS(string in, string out)
{
    ifstream fin(in);
    ofstream fout(out);
    int N,M;
    fin>>N>>M;
    int start;
    fin>>start;
    grafMare gm(N,M,true);
    gm.citire_graf(fin);
    int sol[100001];
    for(int i=0;i<N+1;i++)
        sol[i]=-1;
    gm.BFS(start, sol);
    for(int i=1;i<N+1;i++)
        fout<<sol[i]<<" ";
}
void citireBiconex(string in, string out)
{
    ifstream fin(in);
    ofstream fout(out);
    int N,M;
    fin>>N>>M;
    grafMare gm(N,M);
    gm.citire_graf(fin);
    vector<int>biconex[100001];   
    int first_value[100001];
    int min_pos[100001];
    stack <int> node_order;
    int counter=0;
    
    for(int i=1;i<=gm.get_N();i++)
        if(!min_pos[i])
            gm.DFS_biconex(i,1,0,counter,biconex,first_value,min_pos,node_order);
    fout<<counter<<"\n";
    for(int i=1;i<=counter;i++)
    {
        for(auto j : biconex[i])
            fout<<j<<" ";
        fout<<"\n";
    }
}
void citireCTC(string in, string out)
{
    ifstream fin(in);
    ofstream fout(out);
    int N,M;
    fin>>N>>M;
    grafMare gm(N,M,true);
    vector<int>ctc[100001];
    gm.CTCelp(fin,ctc);
    int viz[100001];
    stack<int>node_order;
    for(int i=1;i<=N;i++)
        if(!viz[i])
            gm.DFS_CTC_1(i,viz,node_order);
    
    vector<int>sol_ctc[100001];
    int counter=0;
    while(!node_order.empty())
    {
        if(viz[node_order.top()]==1)
        {
            counter++;
            gm.DFS_CTC_2(node_order.top(),viz,sol_ctc,counter,ctc);
        }
        node_order.pop();
    }
    fout<<counter<<"\n";
    for(int i=1;i<=counter;i++)
    {
        for(auto x : sol_ctc[i])
            fout<<x<<" ";
        fout<<"\n";  
    }
}
void grafMare::DFS_top(int current_node, int viz[], vector<int>&sol_sortaret)
{
    viz[current_node]=1;
    for(auto x : graf[current_node])
        if(!viz[x])
            DFS_top(x, viz, sol_sortaret);
    sol_sortaret.push_back(current_node);
}
void citireTop(string in, string out)
{
    ifstream fin(in);
    ofstream fout(out);
    int N,M;
    fin>>N>>M;
    grafMare gm(N,M,true);
    gm.citire_graf(fin);
    int viz[100001];
    vector<int>sol_sortaret;
    for(int i=1;i<=N;i++)
        if(!viz[i])
            gm.DFS_top(i, viz, sol_sortaret);
    reverse(sol_sortaret.begin(),sol_sortaret.end());
    for(auto x : sol_sortaret)
        fout<<x<<" ";
}
void grafMare::critice(int current_node, int current_pos, int tata_node, int first_value[], int min_pos[], vector<vector<int>>&sol)
{
    min_pos[current_node]=current_pos;
    first_value[current_node]=current_pos;
    for(auto i : graf[current_node])
    {
        if(!min_pos[i])
        {
            critice(i, current_pos+1, current_node, first_value, min_pos, sol);
            min_pos[current_node]=min(min_pos[current_node],min_pos[i]);
            if(min_pos[i]>current_pos)
                sol.push_back({current_node,i});
        }
        else if(i!=tata_node)
            min_pos[current_node]=min(min_pos[current_node],first_value[i]);
    }
}
void citireCritical()
{
    int N,M;
    cin>>N>>M;
    grafMare gm(N,M);
    gm.citire_graf(cin);
      
    int first_value[100001];
    int min_pos[100001];
    vector<vector<int>>sol;
    gm.critice(0,1,0,first_value,min_pos,sol);
    for(auto&c : sol)
    {
        for(auto j : c)
            cout<<j<<" ";
        cout<<"\n";
    }
}
bool grafMare::helsinki(vector<int>&hel)
{
    while(1)
    {
        sort(hel.begin(),hel.end(),greater<>());
        if(hel[0]==0)//toate 0
            return true;
        int x=hel[0];
        hel.erase(hel.begin());
        if(x>hel.size())//destule elem
            return false;
        for(int i=0;i<x;i++)
        {
            hel[i]--;
            if(hel[i]<0)//gasit elem negativ
                return false;
        }
    }
}
void citireHavel(string in, string out)
{
    ifstream fin(in);
    ofstream fout(out);
    int N;
    fin>>N;
    grafMare gm(N);
    vector<int>hel;
    for(int i=0;i<N;i++)
    {
        int x;
        fin>>x;
        hel.push_back(x);
    }
    fout<<gm.helsinki(hel);
}	
int grafMare::radacina(int x, int tree[])
{
    while(tree[x]!=x)
        x=tree[x];
    return x;
}
void grafMare::combine(int x,int y,int tree[], int rang[])
{
    if(rang[x]==rang[y])
    {
        tree[y]=x;
        rang[x]++;
    }
    else if(rang[x]>rang[y])
        tree[y]=x;
    else
        tree[x]=y;
}
void grafMare::pmd_out(int tree[], int rang[],istream &fin,ofstream &fout)
{
    int a,x,y;
    for(int i=0;i<M;i++)
    {
        fin>>a>>x>>y;
        if(a==1)
            combine(radacina(x,tree),radacina(y,tree),tree,rang);
        else
        {
            if(radacina(x,tree)==radacina(y,tree))
                fout<<"DA\n";
            else
                fout<<"NU\n";
        }
    }
}
void citirePMD(string in, string out)
{
    ifstream fin(in);
    ofstream fout(out);
    int N,M;
    fin>>N>>M;
    grafMare gm(N,M);
    int tree[100001];
    int rang[100001];
    for(int i=1;i<=N;i++)
		tree[i]=i;
	for(int i=1;i<=N;i++)
		rang[i]=1;
	gm.pmd_out(tree,rang,fin,fout);
}
void grafMare::combine_apm_kruskal(int x,int y,int tree[])
{
    tree[x]=y;
}
int C[100001];
bool sortare(int x,int y)
{
    return C[x]<C[y];
}
void grafMare::citire_apm_kruskal(istream &fin,ofstream &fout)
{
    int rez=0;
    int X[100001];
    int Y[100001];
    int idx[100001];
    int tree[100001];
    vector<int>sol_kruskal;
    for(int i=1;i<=M;i++)
    {
        fin>>X[i]>>Y[i]>>C[i];
        idx[i]=i;
    }
    for(int i=1;i<=N;i++)
    {
        tree[i]=i;
    }
    sort(idx+1,idx+M+1,sortare);
    for(int i=1;i<=M;i++)
    {
        if(radacina(X[idx[i]],tree) != radacina(Y[idx[i]],tree) )
        {
            rez+=C[idx[i]];
            combine_apm_kruskal(radacina(X[idx[i]],tree),radacina(Y[idx[i]],tree),tree);
            sol_kruskal.push_back(idx[i]);
        }
    }
    fout<<rez<<"\n"<<N-1<<"\n";
    for(int i=0;i<N-1;i++)
        fout<<X[sol_kruskal[i]]<<" "<<Y[sol_kruskal[i]]<<"\n";
}
void citireAPM(string in, string out)
{
    ifstream fin(in);
    ofstream fout(out);
    int N,M;
    fin>>N>>M;
    grafMare gm(N,M);
    gm.citire_apm_kruskal(fin,fout);
}
void grafMare::dijkstra(istream &fin,ofstream &fout)
{
    int viz[100001];
    vector<pair<int,int>>graf_d[50001];
    int distanta_dijkstra[50001];
    for(int i=0;i<M;i++)
    {
        int x,y,z;
        fin>>x>>y>>z;
        graf_d[x].push_back(make_pair(y,z));
    }
    for(int i=1;i<=N;i++)
        distanta_dijkstra[i]=INT_MAX;
    
    distanta_dijkstra[1]=0;
    priority_queue<p,vector<p>,greater<p>>heap;
    heap.push(make_pair(0,1));
    
    for(int i=1;i<=N;i++)
        viz[i]=0;
    while(!heap.empty())
    {
        int current=heap.top().second;
        heap.pop();
        if(viz[current]==1)
            continue;
        else
            viz[current]=1;
        for(auto x:graf_d[current])
            if(distanta_dijkstra[current]+x.second < distanta_dijkstra[x.first])
            {
                distanta_dijkstra[x.first]=distanta_dijkstra[current]+x.second;
                heap.push(make_pair(distanta_dijkstra[x.first],x.first));
            }
    }
    for(int i=2;i<=N;i++)
        if(distanta_dijkstra[i]!=INT_MAX)
            fout<<distanta_dijkstra[i]<<" ";
        else
            fout<<0<<" ";
}
void citireDijkstra(string in, string out)
{
    ifstream fin(in);
    ofstream fout(out);
    int N,M;
    fin>>N>>M;
    grafMare gm(N,M);
    gm.dijkstra(fin,fout);
}
void grafMare::bellman(istream &fin,ofstream &fout)
{
    int viz[100001];
    vector<pair<int,int>>graf_d[50001];
    int distanta_bellman[50001];
    for(int i=0;i<M;i++)
    {
        int x,y,z;
        fin>>x>>y>>z;
        graf_d[x].push_back(make_pair(y,z));
    }
    for(int i=1;i<=N;i++)
        distanta_bellman[i]=INT_MAX;
    
    distanta_bellman[1]=0;
    priority_queue<p,vector<p>,greater<p>>heap;
    heap.push(make_pair(0,1));
    int x=0;
    for(int i=1;i<=N;i++)
        viz[i]=0;
    while(!heap.empty())
    {
        int current=heap.top().second;
        heap.pop();
        viz[current]++;
        if(viz[current]>=N)
        {
            fout<<"Ciclu negativ!";
            x=1;
            break;
        }
        for(auto x:graf_d[current])
            if(distanta_bellman[current]+x.second < distanta_bellman[x.first])
            {
                distanta_bellman[x.first]=distanta_bellman[current]+x.second;
                heap.push(make_pair(distanta_bellman[x.first],x.first));
            }
    }
    if(x==0)
    for(int i=2;i<=N;i++)
        if(distanta_bellman[i]!=INT_MAX)
            fout<<distanta_bellman[i]<<" ";
        else
            fout<<0<<" ";
}
void citireBellman(string in, string out)
{
    ifstream fin(in);
    ofstream fout(out);
    int N,M;
    fin>>N>>M;
    grafMare gm(N,M);
    gm.bellman(fin,fout);
}
void citireFloyd(string in, string out)
{
    ifstream fin(in);
    ofstream fout(out);
    int N;fin>>N;
    int mat[N][N];
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            fin>>mat[i][j];
    for(int k=0;k<N;k++)
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                if(i!=j && mat[i][k] && mat[k][j] && (mat[i][j]>mat[i][k]+mat[k][j] || mat[i][j]==0))
                    mat[i][j]=mat[i][k]+mat[k][j];
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
            fout<<mat[i][j]<<" ";
        fout<<"\n";
    }
}
void grafMare::darbBFS(int start,int &end, int &d)
{
    int sol[100001];
    for(int i=0;i<N+1;i++)
        sol[i]=-1;
    queue <int> q;
    q.push(start);
    sol[start]=0;
    
    while(!q.empty())
    {
        int first=q.front();
        q.pop();
        for(int vecin : graf[first])
        {
            if(sol[vecin]==-1)
            {
                sol[vecin]=sol[first]+1;
                q.push(vecin);
            }
        }
    }
    d=0;
    for(int i=1;i<=N;i++)
        if(sol[i]>d)
        {
            d=sol[i];
            end=i;
        }
}
void citireDarb(string in, string out)
{
    ifstream fin(in);
    ofstream fout(out);
    int M;
    fin>>M;
    grafMare gm(M,M);
    gm.citire_graf(fin);
    int end,d,temp;
    gm.darbBFS(1,end,d);
    gm.darbBFS(end,temp,d);
    fout<<d+1;
}
void grafMare::Euler(vector<int>&sol, vector<vector<pair<int,int>>>graf)
{
    for(int i=1;i<=N;i++)
    {
        if(graf[i].size() % 2 != 0)
        {
            sol.push_back(-1);
            return;
        }
    }
    int viz[500001];
    for(int i=0;i<500001;i++)
        viz[i]=0;
    stack<int>nod_curent;
    nod_curent.push(1);
    while(!nod_curent.empty())
    {
        int nod=nod_curent.top();
        if(!graf[nod].empty())
        {
            pair<int,int>vecin = graf[nod].back();
            graf[nod].pop_back();
            if(!viz[vecin.second])
            {
                viz[vecin.second]=1;
                nod_curent.push(vecin.first);
            }
 
        }
        else
        {
            sol.push_back(nod);
            nod_curent.pop();
        }
    }
}
void citireEuler(string in, string out)
{
    ifstream fin(in);
    ofstream fout(out);
    int N,M;
    fin>>N>>M;
    grafMare gm(N,M);
    vector<vector<pair<int,int>>>graf(N+1);
    for(int i=0;i<M;i++)
    {
        int a, b;
        fin>>a>>b;
        graf[a].push_back(make_pair(b,i));
        graf[b].push_back(make_pair(a,i));
    }
    vector<int>sol;
    gm.Euler(sol,graf);
    for(auto x:sol)
        fout<<x<<" ";
}
int main()
{
citireDFS("dfs.in", "dfs.out");   
//citireBFS("bfs.in", "bfs.out");   
//citireBiconex("biconex.in", "biconex.out");   
//citireCTC("ctc.in", "ctc.out");   
//citireCritical();
//citireTop("sortaret.in", "sortaret.out"); 
//citireHavel("havel.in", "havel.out");
//citirePMD("disjoint.in","disjoint.out");
//citireAPM("apm.in", "apm.out");
//citireDijkstra("dijkstra.in", "dijkstra.out");
//citireBellman("bellmanford.in", "bellmanford.out");
//citireFloyd("royfloyd.in", "royfloyd.out");
//citireDarb("darb.in", "darb.out");
//citireEuler("ciclueuler.in","ciclueuler.out");
}