Fişierul intrare/ieşire:dirty.in, dirty.outSursăCerc informatică Vianu
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.4 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Dirty

NSA a înfiinţat Departamentul pentru Interceptarea Reţelelor Teroriste pe Yahoo, Facebook, Apple, Google şi Skype (NSA PRISM). Departamentul veghează la liniştea noastră, a muritorilor simpli fără nimic de ascuns, şi analizează datele obţinute folosind o reţea de calcul formată din calculatoare conectate prin cabluri bidirecţionale. Fiecare cablu leagă exact două calculatoare, dar un calculator poate avea mai multe cabluri. Oricare două calculatoare sunt legate direct prin cel mult un cablu. În prezent, reţeaua este conexă, adică oricare două calculatoare pot comunica, direct sau indirect.

Anarhista Julianna Sage şi-a folosit puterea de seducţie pentru a îl convinge pe tehnicianul Steward Noden să-i ofere un tur al laboratorului. În realitate, ea ţine pe stick un virus cu care poate distruge orice calculator din reţea. Pentru a sabota cât mai mult reţeaua, Julianna doreşte să viruseze acel calculator prin dispariţia căruia reţeaua se fragmentează în cât mai multe sub-reţele deconectate una de alta. Cunoscând structura reţelei, ajutaţi-o pe Julianna să afle toate variantele de atac pe care le are.

Date de intrare

Fişierul de intrare dirty.in conţine, pe prima linie, numărul N de calculatoare şi numărul M de cabluri. Pe următoarele M linii sunt indicate conexiunile, sub forma câte unei perechi X Y cu semnificaţia că există un cablu între calculatoarele numerotate X şi Y.

Date de ieşire

În fişierul de ieşire dirty.out se vor scrie, pe prima linie, R = numărul de sub-reţele în care poate fragmenta Julianna reţeaua şi V = numărul de variante de a sabota un calculator pe care le are ea. Pe a doua linie se vor scrie cele V numere de ordine ale acestor calculatoare, în ordine crescătoare şi despărţite prin spaţii.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ M ≤ 300.000
  • 1 ≤ X, Y ≤ N
  • Julianna garantează că există un calculator prin dispariţia căruia reţeaua să se fragmenteze.

Exemplu

dirty.indirty.outpoză
9 10
1 2
3 1
2 3
6 7
8 6
6 3
3 4
5 3
8 9
4 5
3 2
3 6

Explicaţie

Prin sabotarea calculatorului 3, reţeaua se fragmentează în 3 sub-reţele: { 1, 2 }, { 4, 5 } şi { 6, 7, 8, 9 }.
Prin sabotarea calculatorului 6, reţeaua se fragmentează în 3 sub-reţele: { 1, 2, 3, 4, 5 }, { 7 } şi { 8, 9 }.
Sabotarea calculatorului 8 fragmentează reţeaua în numai două componente, iar sabotarea altor calculatoare nu fragmentează reţeaua.

Trebuie sa te autentifici pentru a trimite solutii. Click aici