Cerința

Într-o țară locuiesc n persoane. Anumite perechi de persoane se cunosc între ele și se cunosc aceste perechi. Relația de cunoaștere între două persoane este reciprocă.

În țară izbucnește o epidemie (nu este mortală, doar foarte contagioasă). Dacă persoana A este bolnavă și cunoaște persoana B, se va îmbolnăvi și aceasta, după o perioadă de incubație a bolii de 1 zi. Inițial sunt bolnave k persoane cunoscute. Se cere să se determine după câte zile sunt bolnave toate cele n persoane.

Date de intrare

Fișierul de intrare epidemie.in conține pe prima linie numerele n m, reprezentând numărul persoanelor și numărul perechilor de persoane care se cunosc reciproc. Urmează m linii cu câte două numere i j, cu semnificația: persoanele i și j se cunosc. Pe următoarea linie se află numărul k de persoane infectate inițial, iar pe ultima linie se află k numere distincte cuprinse între 1 și n, reprezentând aceste persoane.

Date de ieșire

Fișierul de ieșire epidemie.out va conține pe prima linie numărul Z, reprezentând numărul de zile după care toate cele n persoane sunt infectate.

Restricții și precizări

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ n*(n-1)/2
• 1 ≤ i , j ≤ n
• 1 ≤ k ≤ n
• ziua inițială va fi luată în considerare
• graful asociat acestei populații este conex

Exemplu

epidemie.in

10 12
1 2
1 7
1 10
2 4
2 5
2 6
3 4
4 5
5 6
7 8
8 10
9 10
2
4 8

epidemie.out

3

Explicație

În prima zi se îmbolnăvesc persoanele: 4 8. În ziua a doua se infectează 2 3 5 7 10. În ziua a treia se infectează 1 6 9.

#include <bits/stdc++.h>


using namespace std;

ifstream cin("epidemie.in");
ofstream cout("epidemie.out");

int n , x , y , m , p , d[1001] , v[1001] , a , maxi;
vector <int> G[1001];
queue <int> Q;

void bfs()
{

    while(!Q.empty())
    {
        int x = Q.front();
        for(int i : G[x])
            if(!v[i])
            {
                Q.push(i);
                v[i] = 1;
                d[i] = d[x] + 1;
            }
        Q.pop();
    }
}


int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y ;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    cin >> p;

    for(int i = 1 ; i <= p ; i++)
    {
        cin >> a;
        v[a] = 1;
        d[a] = 1;
        Q.push(a);
    }
    bfs();

    for(int i = 1 ; i <= n ; i++)
        if(d[i] > maxi) maxi = d[i];

    cout << maxi;
}