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

using namespace std;

ifstream fi("bfs.in");
ofstream fo("bfs.out");

vector<bool> vizitat; //vector pentru marcarea nodurilor vizitate in
                             //functiile componente_conexe si DFS; declarat
                             //global pentru a fi accesibil oricand din
                             //ambele functii

vector<int> nivel; //stocheaza adancimea la care a fost gasit un nod
                   //daca un element are valoarea -1, atunci nodul asociat
                   //este nevizitat
vector<int> low; //stocheaza nivelul minim la care poate ajunge un anumit
                 //nod mergand in fii pe drumuri de intoarcere
                 //(folosit si la componente tare conexe, prin analogie)
stack<pair<int, int>> muchii_comp_biconexe; //stocheaza muchii care vor intra
                                            //intr-o viitoare componenta
                                            //biconexa
//sunt declarati global pentru a fi accesibili oricand din functia
//componente_biconexe
vector<vector<int>> comp_biconexe; //declarat global pentru a fi accesibil
                                   //si din functia gasire_componenta_biconexa,
                                   //si din main
int index_ctc = 0;
vector<int> index;
vector<bool> inComponenta;
stack<int> noduri_comp_tare_conexa;
vector<vector<int>> comp_tare_conexe; //declarate global pentru a fi accesibile
                                      //oricand din functiile
                                      //componente_tare_conexe si
                                      //DFS_tare_conexe


class Graf
{
    int nr_noduri;
    int nr_muchii;
    int nod_start;
    vector<vector<int>> lista_adiacenta;
    void DFS(int nod);
    void gasire_componenta_biconexa(int nod1, int nod2);
    void DFS_tare_conexe(int nod);
public:
    Graf();
    void citire_neorientat();
    void citire_orientat();
    void citire_orientat_bfs();
    void BFS();
    void componente_conexe();
    void componente_biconexe(int nod_curent, int nod_initial, int nv);
    void componente_tare_conexe();
    void havel_hakimi();
};

Graf::Graf(){
    nr_noduri = 0;
    nr_muchii = 0;
    nod_start = 0;
}

void Graf::citire_neorientat(){
    int nod_1, nod_2;
    fi >> nr_noduri >> nr_muchii;
    for (int i = 1; i <= nr_noduri + 1; i++){
        lista_adiacenta.push_back(vector<int>());
    }
    for (int i = 0; i < nr_muchii; i++){
        fi >> nod_1 >> nod_2;
        lista_adiacenta[nod_1].push_back(nod_2);
        lista_adiacenta[nod_2].push_back(nod_1);
    }
}

void Graf::citire_orientat(){
    int nod_1, nod_2;
    fi >> nr_noduri >> nr_muchii;
    for (int i = 1; i <= nr_noduri + 1; i++){
        lista_adiacenta.push_back(vector<int>());
    }
    for (int i = 0; i < nr_muchii; i++){
        fi >> nod_1 >> nod_2;
        lista_adiacenta[nod_1].push_back(nod_2);
    }
}

void Graf::citire_orientat_bfs(){ //functie de citire specifica problemei BFS
                                  //pentru a permite citirea nodului de start
    int nod_1, nod_2;
    fi >> nr_noduri >> nr_muchii >> nod_start;
    for (int i = 1; i <= nr_noduri + 1; i++){
        lista_adiacenta.push_back(vector<int>());
    }
    for (int i = 0; i < nr_muchii; i++){
        fi >> nod_1 >> nod_2;
        lista_adiacenta[nod_1].push_back(nod_2);
    }
}

void Graf::BFS(){
    //declaram un vector "vizitat" pentru marcarea nodurilor vizitate, o
    //coada "coada_varfuri" pentru prelucrarea in ordine a nodurilor
    //parcurse, un vector "nivel" care stocheaza nivelurile pe care se afla
    //fiecare nod si o variabila "nod" pentru nodul care trebuie prelucrat
    bool vizitat[nr_noduri + 1];
    queue<int> coada_varfuri;
    int nod;
    int nivel[nr_noduri + 1];
    //initializam vectorul vizitat si vectorul nivel
    for (int i = 1; i <= nr_noduri; i++){
        vizitat[i] = false;
        nivel[i] = -1;
    }
    //incepem prin a pune nodul de start in coada, marcandu-l drept vizitat
    //si setandu-i nivelul ca fiind 0
    coada_varfuri.push(nod_start);
    vizitat[nod_start] = true;
    nivel[nod_start] = 0;
    //facem BFS pana cand nu mai sunt noduri de prelucrat
    while (!coada_varfuri.empty()){
        //luam un nod din coada
        nod = coada_varfuri.front();
        //pentru fiecare vecin al sau
        for (auto i = lista_adiacenta[nod].begin(); i != lista_adiacenta[nod].end(); i++){
            //daca vecinul respectiv nu a mai fost vizitat, il punem in
            //coada, il marcam drept vizitat si ii setam nivelul ca fiind
            //cel al nodului initial + 1
            if (!vizitat[*i]){
                coada_varfuri.push(*i);
                vizitat[*i] = true;
                nivel[*i] = nivel[nod] + 1;
            }
        }
        //eliminam nodul din coada
        coada_varfuri.pop();
    }
    //afisam nivelul tuturor nodurilor dupa BFS
    for (int i = 1; i <= nr_noduri; i++){
        fo << nivel[i] << " ";
    }
}

void Graf::DFS(int nod){
    //marcam nodul curent ca fiind vizitat
    vizitat[nod] = true;
    //pentru fiecare vecin al sau
    for (auto i = lista_adiacenta[nod].begin(); i != lista_adiacenta[nod].end(); i++){
        //daca vecinul respectiv nu a mai fost vizitat, apelam DFS pe acesta
        if (!vizitat[*i]){
            DFS(*i);
        }
    }
}

void Graf::componente_conexe(){
    //declaram un vector "vizitat" pentru marcarea nodurilor vizitate si o
    //variabila "nr_comp_conexe" in care stocam numarul de componente conexe
    //gasite (egal cu numarul de DFS-uri apelate din aceasta functie)
    int nr_comp_conexe = 0;
    //initializam vectorul vizitat
    for (int i = 1; i <= nr_noduri; i++){
        vizitat.push_back(false);
    }
    //luam fiecare nod, si daca nu a mai fost vizitat, apelam DFS pornind
    //de la el si incrementam numarul de componente conexe gasite
    for (int i = 1; i <= nr_noduri; i++){
        if (!vizitat[i]){
            nr_comp_conexe++;
            DFS(i);
        }
    }
    //la sfarsit, afisam numarul de componente conexe cerut
    fo << nr_comp_conexe;
}

void Graf::gasire_componenta_biconexa(int nod1, int nod2){
    //eliminam muchii din stiva pana ajungem la muchia (nod1, nod2)
    //cream un vector in care retinem componenta biconexa (muchiile sale,
    //mai tarziu vom pastra doar nodurile)
    vector<int> comp;
    int n1, n2;
    do {
        n1 = muchii_comp_biconexe.top().first;
        n2 = muchii_comp_biconexe.top().second;
        comp.push_back(n1);
        comp.push_back(n2);
        //stergem muchia din stiva
        muchii_comp_biconexe.pop();
    } while (n1 != nod1 && n2 != nod2);
    //punem componenta in lista de componente
    comp_biconexe.push_back(comp);
}

void Graf::componente_biconexe(int nod_curent, int nod_initial, int nv){
    //setam adancimea si low[nod_curent]; initial, nodul curent are low
    //egal cu adancimea
    if (nivel.empty() && low.empty()){
        for (int i = 1; i <= nr_noduri; i++){
            nivel.push_back(-1);
            low.push_back(-1);
        }
    }
    nivel[nod_curent] = nv;
    low[nod_curent] = nv;
    //pentru fiecare vecin al nodului
    for (auto i = lista_adiacenta[nod_curent].begin(); i != lista_adiacenta[nod_curent].end(); i++){
        //daca intalnim nodul initial printre vecini, il ignoram
        if (*i == nod_initial){
            continue;
        }
        //daca intalnim un nod pe care nu l-am vizitat
        if (nivel[*i] == -1){
            //punem muchia dintre cele doua noduri in stiva
            muchii_comp_biconexe.push(make_pair(nod_curent, *i));
            //apelam DFS (reapelam aceasta functie) pe nodul gasit
            //nv va avea valoarea nv + 1
            componente_biconexe(*i, nod_curent, nv + 1);
            //dupa ce iesim din recursie, va trebui sa actualizam
            //low[nod_curent] cu low-ul nodului gasit
            low[nod_curent] = min(low[nod_curent], low[*i]);
            //daca nodul gasit nu poate ajunge la un stramos al nodului curent
            if (low[*i] >= nivel[nod_curent]){
                //am gasit o componenta biconexa, deci incepem sa o retinem
                gasire_componenta_biconexa(nod_curent, *i);
            }
        } else {
            //altfel, actualizam low[nod_curent] cu adancimea nodului gasit
            low[nod_curent] = min(low[nod_curent], nivel[*i]);
        }
    }
}

void Graf::DFS_tare_conexe(int nod){
    //initializam nodul si low[nod] cu index-ul curent, punem nodul in stiva,
    //ii marcam prezenta in stiva si setam indexul pentru urmatorul nod
    index[nod] = index_ctc;
    low[nod] = index_ctc;
    index_ctc++;
    noduri_comp_tare_conexa.push(nod);
    inComponenta[nod] = true;
    //pentru fiecare vecin al nodului
    for (auto i = lista_adiacenta[nod].begin(); i != lista_adiacenta[nod].end(); i++){
        //daca nodul nu a fost vizitat, apelam DFS pe acest nod si actualizam
        //low-ul nodului curent cu low-ul nodului gasit
        if (index[*i] == -1){
            DFS_tare_conexe(*i);
            low[nod] = min(low[nod], low[*i]);
        } else if (inComponenta[*i]){
            //altfel, daca nodul este in stiva (si deci in componenta curenta),
            //actualizam low-ul nodului curent cu indexul nodului gasit
            low[nod] = min(low[nod], index[*i]);
        }
    }
    //daca low-ul unui nod este egal cu indexul sau, atunci inseamna ca el e
    //nodul "radacina" si ca trebuie sa formam componenta tare conexa din
    //acest nod
    if (low[nod] == index[nod]){
        //cream vectorul cu nodurile din componenta tare conexa extragandu-le
        //din stiva si stergandu-le prezenta in stiva; adaugam apoi acest
        //vector printre componente
        vector<int> comp;
        int n;
        do {
            n = noduri_comp_tare_conexa.top();
            comp.push_back(n);
            inComponenta[n] = false;
            noduri_comp_tare_conexa.pop();
        } while (n != nod);
        comp_tare_conexe.push_back(comp);
    }
}

void Graf::componente_tare_conexe(){
    if (index.empty() && low.empty() && inComponenta.empty()){
        for (int i = 1; i <= nr_noduri; i++){
            index.push_back(-1);
            low.push_back(-1);
            inComponenta.push_back(false);
        }
    }
    for (int i = 1; i <= nr_noduri; i++){
        if (index[i] == -1){
            DFS_tare_conexe(i);
        }
    }
}

void Graf::havel_hakimi(){
    //declaram un vector secv_grade, care va stoca gradele pe care trebuie
    //sa le aiba fiecare nod
    vector<int> secv_grade;
    //declaram o variabila suma_grade pentru a verifica daca suma gradelor
    //este para sau nu
    int n, suma_grade = 0;
    fi >> n;
    for (int i = 0; i < n; i++){
        int grad;
        fi >> grad;
        secv_grade.push_back(grad);
        //verificam daca un grad este mai mare decat n, daca da atunci
        //nu se poate construi graful cerut
        if (grad > n - 1){
            fo << "NU";
            return;
        }
        //altfel, adunam gradul la suma pentru a doua conditie necesara
        suma_grade += grad;
    }
    //daca suma gradelor este impara, nu se poate construi graful cerut
    if (suma_grade % 2 != 0){
        fo << "NU";
        return;
    }
    //sortam descrescator vectorul de grade pentru a alege cel mai mare grad
    //din secventa
    sort(secv_grade.begin(), secv_grade.end(), greater<int>());
    //algoritmul ruleaza cat timp secventa contine valori nenule
    //vectorul fiind sortat descrescator, daca primul element este nul,
    //inseamna ca si celelalte elemente sunt nule
    while (secv_grade[0] > 0){
        //scadem gradele pentru atatea noduri cat este gradul nodului curent
        for (int i = 1; i <= secv_grade[0]; i++){
            secv_grade[i]--;
            //daca un nod, prin aceasta scadere, ajunge sa aiba grad negativ,
            //atunci nu se poate construi graful cerut
            if (secv_grade[i] < 0){
                fo << "NU";
                return;
            }
        }
        //eliminam gradul prelucrat
        secv_grade.erase(secv_grade.begin());
        //sortam din nou vectorul descrescator pentru a alege, in continuare,
        //cel mai mare grad din secventa
        sort(secv_grade.begin(), secv_grade.end(), greater<int>());
    }
    //daca programul nu a fost intrerupt pana acum, inseamna ca putem construi
    //graful cerut
    fo << "DA";
}

int main()
{
    Graf g;
    //1. algoritmul BFS
    g.citire_orientat_bfs();
    g.BFS();
    //2. componente conexe (algoritmul DFS)
    //g.citire_neorientat();
    //g.componente_conexe();
    //3. componente biconexe
    /*
    g.citire_neorientat();
    g.componente_biconexe(1, 0, 0); //pornim din nodul 1, care va avea
                                    //adancimea 0
    //afisam numarul de componente biconexe
    int nr_comp = comp_biconexe.size();
    fo << nr_comp << "\n";
    //incepem sa procesam fiecare componenta pentru afisare
    for (int i = 0; i < nr_comp; i++){
        //ordonam crescator nodurile care alcatuiesc componenta
        sort(comp_biconexe[i].begin(), comp_biconexe[i].end());
        //dupa executarea functiei, in comp_biconexe avem muchiile
        //componentelor; trebuie sa lasam doar nodurile in componenta
        comp_biconexe[i].erase(unique(comp_biconexe[i].begin(), comp_biconexe[i].end()), comp_biconexe[i].end());
        //afisam nodurile care alcatuiesc componenta
        int n_noduri = comp_biconexe[i].size();
        for (int j = 0; j < n_noduri; j++){
            fo << comp_biconexe[i][j] << " ";
        }
        fo << "\n";
    }
    */
    //4. componente tare conexe (algoritmul lui Tarjan)
    /*
    g.citire_orientat();
    g.componente_tare_conexe();
    int nr_comp = comp_tare_conexe.size();
    fo << nr_comp << "\n";
    //incepem sa procesam fiecare componenta pentru afisare
    for (int i = 0; i < nr_comp; i++){
        //ordonam crescator nodurile care alcatuiesc componenta
        sort(comp_tare_conexe[i].begin(), comp_tare_conexe[i].end());
        //afisam nodurile care alcatuiesc componenta
        int n_noduri = comp_tare_conexe[i].size();
        for (int j = 0; j < n_noduri; j++){
            fo << comp_tare_conexe[i][j] << " ";
        }
        fo << "\n";
    }
    */
    //5. algoritmul Havel-Hakimi
    //g.havel_hakimi();
    return 0;
}