Asfalt
| vreme | memorija | ulaz | izlaz |
|---|---|---|---|
| 1 s | 1000 Mb | standardni izlaz | standardni ulaz |
U jednoj državi postoji n gradova i ukupno m dvosmernih auto-puteva od kojih svaki povezuje po dva grada. Svaki grad ima različitu popularnost od 1 do n. Najpopularniji grad ima popularnost n i to je ujedno i gravni grad. Odlučeno je da neki od puteva u ovoj državi budu asfaltirani, pri čemu će asfaltiranje finansirati gradovi. Svaki grad se obavezao da asfaltira (tačno jedan) put koji vodi od njega do njegovog suseda sa najvećom popularnošću (jer je to u interesu svakog grada). Međutim, ukoliko je popularnost nekog grada veća od popularnosti svih njegovih suseda, taj grad ne asfaltira nijedan put.
Mi smo stranci i ne znamo popularnosti gradova, ali imamo mapu i znamo koji su putevi asfaltirani. Ukoliko ima tačno n - 1 asfaltiranih puteva, odrediti sve gradove koji mogu biti glavni. Garantuje se da postoji bar jedan takav grad, tj. mapa je zadata korektno.
U prvom redu ulaza nalaze se 2 prirodna broja n i m, koji predstavljaju, redom, broj gradova i broj auto-puteva. U narednih m redova sledi opis mape: po tri broja ai, bi i ci u svakom redu, koji očnačavaju da postoji (neusmeren) put između gradova ai i bi, pri čemu je taj put asfaltiran ako je ci = 1. Gradovi su numerisani od 1 do n (nezavisno od popularnosti) i između svaka dva grada postoji najviše jedan auto-put.
U prvom redu izlaza ispisati broj gradova koji su kandidati za glavni grad. U sledećem redu ispisati redne brojeve tih gradova u proizvoljnom redosledu, razdvojene razmakom.
n ≤ 20.000,
m≤ 200.000
4 4
1 2 1
2 3 1
3 4 1
4 1 0
2
2 3
Asfaltirani putevi su: 1-2, 2-3 i 3-4. Ukoliko bi grad 1 bio glavni grad, onda bi sused grada 4 koji ima najveću vrednost bio baš grad 1 i grad 4 bi asfaltirao put 4-1. Međutim, ovaj put nije asfaltiran pa grad 1 ne može biti glavni. Slično i za grad 4. Gradovi 2 i 3 mogu biti glavni, na pr. ako su popularnosti gradova redom 1, 4, 3 i 2, grad 2 je najpopularniji i zato glavni, a asfaltiranje je u skladu sa ulaznim podacima i pravilima iz postavke. Slično i za grad 3.
Uploaded checker Asfalt.checker.exe, but could not assign it to this problem and try out the solution.
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.