== include(page="template/taskheader" task_id="markon") ==
Poveste şi cerinţă...
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:
# Valoarea asociată lui B este egală cu zero;
# 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.
h2. Date de intrare
Fişierul de intrare $markon.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $markon.out$ ...
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
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N, M ≤ 500 000$
* 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 |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 6 3
3 2 0 1 1
1 2
5 1
1 4
2 5
4 2
3 4
| 2
3
4
|
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") ==
