KGB

kgb

Î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 Î {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

Timp maxim de executie/test: 0.1 secunde

prof. Emanuela Cerchez

Liceul de Informatica "Grigore Moisil" Iasi

Contact:ema at mail.dntis.ro