MarsX
Pe planeta Marte se desfășoară un intens război între trupele coloniștilor pământeni și triburile autohtone de reptilieni.
Pentru a dobândi controlul decisiv asupra planetei, pământenii au trimis trupe de commando în sistemul de galerii subterane de pe Marte, reprezentat sub forma unei configurații de n
peșteri conectate prin m
canale unidirecționale. Misiunea acestora este să ajungă din baza subterană a coloniștilor aflată în galeria 1
în orașul subteran al reptilienilor plasat în galeria n
pentru a distruge rezistența extraterestră.
Știind că fiecare dintre cele m
canale dintre galerii este protejat de un anumit număr de soldați reptilieni, trupele de commando trebuie să aleagă rutele de deplasare cât mai vulnerabile în fața unui asalt, protejate de un număr minim de inamici.
Se cere să aflați setul de galerii care vor fi obligatoriu traversate de pământeni pe parcursul misiunii, folosind orice rută ce este protejată de un număr minim de inamici.
Se vor citi de la tastatură valorile n
(numărul de galerii) și m
(numărul de canale subterane), apoi m
triplete de forma u
, v
, w
, cu proprietatea că există canal unidirecțional între peștera u
și peștera v
, protejat de exact w
soldați.
Se va afișa pe prima linie valoarea k
(numărul de galerii care vor fi obligatoriu traversate de coloniști), iar pe următoarea linie cele k
galerii în ordine crescătoare.
1
și n
pentru fiecare test.1 <= n <= 100.000
1 <= m <= 200.000
1 <= u, v <= n
1 <= w <= 1.000.000.000
stdin
5 6
1 2 3
1 3 4
2 3 1
2 4 5
3 4 1
4 5 8
stdout
4
1 3 4 5
ID: 4
Upload: Sami
Input: Console Input
Memory limit: 64MB/8MB
Time limit: 0.3s
Author: Bărbuț-Dică Sami
Source: Ad-hoc