Question

problema bipartit de pe pbinfo 471
Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n, precum si o mulțime A de vârfuri ale grafului. Considerăm mulțimea B formată din vărfurile grafului care nu aparțin lui A. Să se verifice dacă graful este bipartit peste partiția formată din mulțimile A și B.

Date de intrare
Fişierul de intrare bipartit.in conţine pe prima linie numerele n și m, reprezentând numărul de vârfuri ale grafului și numărul de muchii. Fiecare dintre următoarele m linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j. Urmează un număr k, apoi k numere naturale distincte cuprinse între 1 și n, reprezentând vârfurile din A.

Date de ieşire
Fişierul de ieşire bipartit.out va conţine pe prima linie mesajul DA, dacă graful este bipartit peste partiția formată din mulțimile A și B, respectiv NU în caz contrar.

Restricţii şi precizări
1 < k < n ≤ 100
1 ≤ i , j ≤ n
muchiile se pot repeta în fișierul de intrare



Exemplu
bipartit.in

7 6
1 4
1 6
6 5
3 2
3 5
3 7
3
4 6 3
bipartit.out

DA
VA ROG EU MULT

Answer 1

Ai sursa in atasament.

bfab1f406d4d73641c959f38fabc2490.cpp