Veri

veri

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

h2. Exemplu

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

!problema/veri?veri1.png!

h3. Explicaţie

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$}).
 
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
|
 
!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$}).
 
*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") ==