== include(page="template/taskheader" task_id="dw") ==
Poveste şi cerinţă...
_"People assume that time is a strict progression of cause to effect, but actually, from a nonlinear, non-subjective viewpoint, it's more like a big ball of wibbly-wobbly, timey-wimey... stuff.."_
Doctorul trebuie să salveze universul… din nou. Cu ajutorul T.A.R.D.I.S.-ului acesta poate ajunge în mai multe momente ale istoriei, pe care le poate influenţa pentru a salva prezentul. Cum timpul are o structura complexă, unul din modurile în care poate fi reprezentat este printr-un graf orientat în care nodurile reprezintă evenimente, iar muchiile relaţii de tip cauză-efect. Pentru orice eveniment $i$, notăm cu v{~i~} importanţa acestuia.
Fie x{~1~}, x{~2~}, …, x{~k~} o secvenţă de evenimente. Doctorul poate influenţa această secvenţă dacă şi numai dacă sunt îndeplinite următoarele condiţii: pentru orice $i$ (1 ≤ $i$ ≤ $k-1$), v{~x{~i~}~} < v{~x{~i+1~}~}, iar în reprezentarea timpului ca graf orientat, avem drum de la nodul corespunzător lui x{~i~} la nodul corespunzător lui x{~i+1~} (prin existenţa unui drum de la $a$ la $b$ înţelegem că se poate ajunge de la $a$ la $b$, mergând doar pe muchii din graf şi numai în sensul corespunzător).
Doctorul trebuie să influenţeze cât mai multe evenimente pentru a salva universul, aşa că vă roagă pe voi să găsiţi lungimea maximă a unei secvenţe de evenimente ce respectă restricţiile de mai sus.
h2. Date de intrare
Fişierul de intrare $dw.in$ ...
Prima linie a fişierului $dw.in$ va conţine două numere naturale $N$ şi $M$, reprezentând numărul total de evenimente şi numărul de relaţii cauză-efect.
Pe cea de a doua linie, se vor găsi $N$ numere naturale, al $i$-lea dintre acestea reprezentând importanţa celui de-al $i$-lea eveniment.
Pe fiecare dintre următoarele $M$ linii, se vor găsi două numere naturale, $x$ şi $y$, cu semnificaţia că există o muchie orientată de la nodul corespunzător evenimentului $x$ la nodul corespunzător evenimentului $y$ (evenimentele sunt indexate cu numere naturale de la $1$ la $N$).
h2. Date de ieşire
În fişierul de ieşire $dw.out$ ...
Pe prima linie a fişierului $dw.out$ afişaţi $K$, lungimea maximă a unei secvenţe valide de evenimente.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 200.000$
* În toate testele graful orientat respectă următoarea condiţie: oricare ar fi 3 noduri $A$, $B$, $C$, dacă există drum de la $A$ la $C$ si de la $B$ la $C$, atunci există drum de la $A$ la $B$, sau de la $B$ la $A$, sau ambele.
* În toate testele există un nod de la care se poate ajunge la oricare alt nod.
* pentru 10% din teste 1 ≤ N ≤ 20
* pentru 40% din teste 1 ≤ N ≤ 1000, 1 ≤ M ≤ 2000
* pentru 60% din teste graful este aciclic
* subtask-urile de mai sus {*se pot suprapune*}
* importanta unui eveniment se afla in intervalul [1, 100.000]
h2. Exemplu
table(example). |_. dw.in |_. dw.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 8
1 3 1 4 2
1 2
2 3
3 4
4 2
4 3
4 5
3 5
1 5
| 3
|
h3. Explicaţie
...
Se aleg nodurile 1, 2 şi 4 cu valorile respective 1, 3 şi 4.
== include(page="template/taskfooter" task_id="dw") ==
== include(page="template/taskfooter" task_id="dw") ==
