Cei doi prieteni se vor plimba împreună până când *ciclează*, adică până când vor ajunge în acelaşi nod a doua oară, notat cu $Z$. După ciclare, ei îşi pot continua drumurile separat. Totuşi, dacă vor, pot să meargă amândoi în
continuare pe acelaşi drum: doar dispare obligaţia de a merge împreună.
Fiecare dintre ei trebuie să-şi termine drumul doar după ciclare, adică după ce nu mai sunt obligaţi să meargă împreună.
Totuşi, este în regulă dacă drumul unuia se termină exact în nodul în care au ciclat (adică ciclează în $A$ sau $B$).
Fiecare dintre ei trebuie să-şi termine drumul doar după ciclare, adică după ce nu mai sunt obligaţi să meargă împreună. Totuşi, este în regulă dacă drumul unuia se termină exact în nodul în care au ciclat (adică ciclează în $A$ sau $B$).
Care este numărul minim de minute necesar, astfel încât să fie posibil ca amândoi să ajungă la destinaţiile lor, în timpul alocat, în $A$, respectiv $B$?
Există două tipuri de cerinţe, reprezentate printr-un număr $c$:
* Dacă $c = 1$, trebuie calculată valoarea minimă a lui _max_$(t + t{~A~}, t + t{~B~})$.
* Dacă $c = 2$, trebuie afişat un triplet de drumuri care poate fi urmat de cei doi veri (drumul comun din $S$ până în $Z$, drum urmat ulterior de primul văr din $Z$ până în $A$, drum urmat ulterior de al doilea văr din $Z$ până în $B$), astfel încât valoarea asociată drumurilor, adică _max_$(t + t{~A~}, t + t{~B~})$ să fie minimă. Orice triplet corect cu valoarea asociată minimă poate fi afişat.
h2. Date de intrare
Pe prima linie se găseşte $c$. Pe a doua linie se găsesc doi întregi $n$ şi $m$. Pe a treia linie se găsesc trei întregi $S$, $A$ şi $B$.
Pe următoarele $m$ linii se găsesc câte doi întregi $X$ şi $Y$ , reprezentând că există o muchie direcţionată de la nodul $X$ la nodul $Y$, care poate fi parcursă într-un minut (de cost 1).
Fişierul de intrare $veri.in$ ...
h2. Date de ieşire
Dacă $c = 1$, afişaţi un singur număr, valoarea minimă a lui _max_$(t + t{~A~}, t + t{~B~})$.
Dacă $c = 2$, afişaţi trei drumuri. Primul drum este format de la $S$ până la $Z$. Al doilea drum este format de la $Z$ până la $A$. Al treilea drum este format de la $Z$ până la $B$, unde $S$, $A$, $B$, $Z$ sunt definite anterior.
Fiecare drum se va tipări pe două linii separate.
* Pe prima linie va apărea lungimea drumului, adică numărul de muchii.
* Pe a doua linie vor apărea nodurile drumului, separate prin câte un spaţiu.
Valoarea asociată drumurilor, adică _max_$(t + t{~A~}, t + t{~B~})$, trebuie să fie minimă.
În fişierul de ieşire $veri.out$ ...
h2. Restricţii
* $1 ≤ S, A, B, Z ≤ n ≤ 5 000$
* Nodurile sunt numerotate de la 1 la $n$.
* $A ≠ B$
* $1 ≤ n ≤ m(m - 1)$
* Se garantează că pentru orice test dat spre rezolvare există cel puţin o soluţie.
* Nu există muchii de la un nod la el însuşi. Există maxim o muchie orientată între oricare două noduri distincte.
* Dacă verii se despart în $A$, primul văr poate să nu mai facă nimic (drumul lui ulterior ar avea 0 muchii şi l-ar conţine doar pe $A$: vezi exemplul 3). Analog pentru $B$.
* Pentru fiecare subtask, testele cu *$c = 1$* vor conta pentru *60%* din punctaj.
table(example). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $30$ | $n ≤ 500, m = n şi toate muchiile sunt de forma i → (i mod n) + 1, unde i ∈ {1, ..., n}.$|
| $2$ | $50$ | $n ≤ 500$|
| $3$ | $20$ | $n ≤ 5 000 şi m ≤ 4n$|
h2. Exemple şi Explicaţii
table(example). |_. veri.in |_. veri.out |
| 2
7 8
1 3 4
1 2
2 5
5 7
7 6
6 7
6 5
5 3
7 4
| 5
1 2 5 7 6 5
1
5 3
2
5 7 4
|
!problema/veri?veri1.png!
* $... ≤ ... ≤ ...$
Figura 1: Drumul urmat în comun de cei doi este $1 → 2 → 5 → 7 → 6 → 5$. Drumul urmat de primul văr în continuare este $5 → 3$. Drumul continuat de al doilea văr este $5 → 7 → 4$. Astfel, primul văr are nevoie de 6 minute pentru a ajunge în $A$, iar al doilea de 7 minute pentru a ajunge în $B$, deci răspunsul pentru $c = 1$ este 7. Cei doi ar fi putut să cicleze în 7, dacă ar fi urmat drumul $1 → 2 → 5 → 7 → 6 → 7$. Totuşi, deşi al doilea văr ar fi ajuns în $B$ în doar 6 minute ({$7 → 4$}), primul văr ar fi avut nevoie de cel puţin 8 minute ca să ajungă în $A$ ({$7 → 6 → 5 → 3$}).
h2. Exemplu
table(example). |_. veri.in |_. veri.out |
| 2
7 8
1 2 5
1 3
1 4
3 2
4 5
6 4
7 3
3 6
4 7
| 5
1 4 7 3 6 4
3
4 7 3 2
1
4 5
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
!problema/veri?veri2.png!
Figura 2: Răspunsul corect pentru $c = 1$ este 8. Pentru acest exemplu există două soluţii corecte. $A$ doua soluţie este tripletul de drumuri ({$1 → 3 → 6 → 4 → 7 → 3, 3 → 2, 3 → 6 → 4 → 5$}).
table(example). |_. veri.in |_. veri.out |
| 2
5 6
1 3 5
1 2
2 3
3 4
4 3
3 1
3 5
| 4
1 2 3 4 3
0
3
1
3 5
|
!problema/veri?veri3.png!
Figura 3: Răspunsul corect pentru $c = 1$ este 5. Este folosit un ciclu care se termină în $A = 3$.
table(example). |_. veri.in |_. veri.out |
| 1
4 4
1 2 4
1 3
3 2
2 3
2 4
| 5
|
!problema/veri?veri4.png!
Figura 4: Pentru $c = 2$, singurul triplet corect de drumuri este ({$1 → 3 → 2 → 3, 3 → 2, 3 → 2 → 4$}).
h3. Explicaţie
*Atenţie!* Tripletul ({$1 → 3 → 2 → 3 → 2, 2, 2 → 4$}) este greşit, deoarece primul nod vizitat a doua oară nu este 2.
...
== include(page="template/taskfooter" task_id="veri") ==
