Fişierul intrare/ieşire:matroid.in, matroid.outSursăBaraj Shumen seniori 2014
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.5 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Matroid

Grădina zoologică din satul Matroid a rămas fără bani. Directorul grădinii, pentru a face economie la hrană, s-a gândit să hrănească unele animale cu altele, până când în final rămâne cu un singur animal supravieţuitor. El primeşte o listă cu dieta animalelor şi ştie dacă un animal poate sau nu să mănânce alt animal. Ajutaţi-l pe director să afle care dintre animale ar putea fi supravieţuitorul final.

Grădina zoologică are N animale distincte. Directorul nu se pricepe la taxonomie, aşa încât nu operează cu numele animalelor, ci cu numerele lor de ordine, cuprinse între 1 şi N.

Date de intrare

Fişierul de intrare matroid.in conţine pe prima linie două numere N M, unde N este numărul de animale, iar M este lungimea listei de informaţii despre dietă. Pe următoarele M linii se află câte o pereche de numere x y, cu semnificaţia că animalul x se poate hrăni cu animalul y.

Date de ieşire

În fişierul de ieşire matroid.out se va scrie, pe prima linie, numărul de animale care ar putea fi supravieţuitorul final. Pe următoarele linii se vor scrie numerele acestor animale, în ordine crescătoare, câte unul pe linie.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ M ≤ 300.000

Exemplu

matroid.inmatroid.out
4 5
1 2
1 3
3 4
2 4
3 1
2
1
3
4 2
1 2
3 4
0

Explicaţie

Pentru primul exemplu, animalul 1 poate fi supravieţuitor: 2 îl mănâncă pe 4, 1 pe 2, 1 pe 3. De asemenea, animalul 3 poate fi supravieţuitor: 3 îl mănâncă pe 4, 1 pe 2, 3 pe 1.

În al doilea exemplu, grădina zoologică nu poate fi redusă la un singur animal.

Trebuie sa te autentifici pentru a trimite solutii. Click aici