== include(page="template/taskheader" task_id="markon") ==
Albăstrel a găsit o hartă pe care sunt reprezentate $N$ oraşe legate între ele prin $M$ tuneluri bidirecţionale. Fiecare oraş are asociat un număr natural cu o semnificaţie necunoscută lui Albăstrel. Ingenios din fire, acesta a folosit harta pentru a realiza un nou joc pe calculator. Jocul constă în marcarea oraşelor după o anumită regulă: un oraş $A$ poate fi marcat numai dacă cel puţin unul dintre oraşele sale vecine $B$, marcat deja, are una dintre proprietăţile:
$1.$ Valoarea asociată lui $B$ este egală cu zero;
$2.$ Valoarea asociată lui $B$ este strict mai mare decât numărul oraşelor nemarcate vecine cu $B$.
Două oraşe sunt considerate vecine dacă există un tunel între ele. Calculatorul alege oraşul de start $X$ iar jucătorul trebuie să înceapă marcarea cu acest oraş. Pentru a câştiga, el trebuie să marcheze un număr maxim de oraşe de pe hartă, respectând regula jocului.
h2. Cerinţă
Ştiind că oraşul de start ales de calculator este $X$, scrieţi un program care să determine $NR$, reprezentând numărul maxim de oraşe ce pot fi marcate, precum şi cele $NR$ oraşe, în ordinea în care acestea sunt marcate.
Poveste şi cerinţă...
h2. Date de intrare
Fişierul de intrare $markon.in$ conţine pe prima linie trei numere naturale $N$, $M$ şi $X$ separate prin câte un spaţiu, reprezentând $N$ - numărul de oraşe, $M$ - numărul de tuneluri şi $X$ - oraşul ales de calculator drept oraş de start. Pe a doua linie se află $N$ numere separate prin câte un spaţiu, reprezentând valoarea asociată fiecărui oraş. Pe următoarele $M$ linii se află câte două numere $a$ şi $b$ reprezentând faptul că între oraşele $a$ şi $b$ este un tunel bidirecţional.
Fişierul de intrare $markon.in$ ...
h2. Date de ieşire
Fişierul de ieşire $markon.out$ are pe prima linie numărul $NR$, iar pe următoarele $NR$ linii se află câte un număr reprezentând raşele în ordinea în care au fost marcate, respectând regula jocului
În fişierul de ieşire $markon.out$ ...
h2. Restricţii
* $2 ≤ N, M ≤ 500 000$
* $1 ≤ v{~i~} ≤ 10^9^$
* oraşele sunt numerotate distinct de la $1$ la $N$
* între două oraşe diferite poate exista cel mult un tunel
* oraşul $X$ este singurul oraş care poate fi marcat prima dată
* dacă există mai multe soluţii cu număr maxim, se va afişa oricare dintre acestea
* pentru $30%$ din teste $N$, $M$ ≤ $10.000$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. markon.in |_. markon.out |
| 5 6 3
3 2 0 1 1
1 2
5 1
1 4
2 5
4 2
3 4
| 2
3
4
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
Oraşul $3$, ales de calculator, este marcat iniţial.
Oraşul $4$ este marcat pentru că este singurul oraş care are un vecin $(3)$, care respectă proprietatea $1$.
...
== include(page="template/taskfooter" task_id="markon") ==
== include(page="template/taskfooter" task_id="markon") ==
