În KGB exista din n
agenti, cu numere de cod distincte de la 1 la n si un agent
sef codificat 0.
Din motive de securitate, nu oricare doi agenti au contacte (informationale!)
directe, dar prin contactele directe existente, oricare doi agenti îsi
pot comunica informatii. Un serviciu de informatii este considerat forte daca
si numai daca nu contine nici un agent prin suprimarea caruia se compromite
comunicarea (si ca urmare, sa existe agenti care sa nu îsi mai poata transmite
informatii).
Cerinta
Scrieti un program, care verifica daca KGB este forte. În plus, daca KGB nu este forte, programul sa determine:
verigile slabe ale KGB (agentii prin a caror suprimare se compromite comunicarea);
toate grupurile de agenti care sunt forte în cadrul KGB, maximale cu aceasta proprietate.
Date de intrare
Fisierul de intrare kgb.in contine pe prima linie n, numarul de agenti din KGB, (exclusiv seful), iar pe fiecare din urmatoarele linii câte o pereche de numere x y
unde x, y apartin {0, 1, 2, ..., n}, sunt separate prin spatii si au semnificatia "x si y au contact direct".
Date de iesire
Fisierul de iesire kgb.out va contine pe prima linie mesajul KGB este forte sau:
pe prima linie, mesajul KGB nu este forte
pe a doua linie, numerele de cod ale agentilor care constituie verigile slabe ale serviciului, în ordine crescatoare, separate prin spatii;
pe a treia linie, m - numarul de grupuri de agenti forte în cadrul KGB;
pe fiecare din urmatoarele m linii, numerele de cod ale agentilor fiecarui grup forte, în ordine crescatoare, separate prin spatii.
Restrictii
1<=n<=1000
Exemple
kgb.in
kgb.out
kgb.in
kgb.out
2
0 2
0 1
2 1
KGB este forte
3
0 1
0 3
2 1
KGB nu este forte
0 1
3
0 3
1 2
0 1
prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil"
Iasi