== include(page="template/taskheader" task_id="stup") ==
Poveste şi cerinţă...
!> problema/stup?stup.png 60%!
Într-un stup oarecare locuiesc $N$ albine. Stupul este compartimentat în parcele în aşa fel încât fiecare parcelă se învecinează cu alte $6$ parcele identice. Cele $N$ albine au primit fiecare câte o parcelă pentru a-şi putea cultiva cele necesare. Se ştie că ele nu au primit aceste teritorii la întâmplare. Albina cu cele mai multe merite, albina $1$, a primit parcela din centrul stupului, iar toate celelalte au primit parcele în ordine descrescătoare a meritelor mergând în spirală de la căsuţa primei albine. Astfel, albina $1$ are cele mai multe merite, în timp ce albina $N$ are cele mai puţine. De-a lungul timpului, aceste albine au format triburi, iar în momentul de faţă niciun trib nu se înţelege prea bine cu vreun alt trib. Felul în care s-au format triburile nu este nici el întâmplător, toate albinele care aparţin unui trib au numere de ordine consecutive, aşa că dacă $a$ şi $b$ fac parte din acelaşi trib, atunci $a+1$, $a+2$, ..., $b-1$ fac şi ele parte din trib. O albină $x$ vrea să-şi vadă o veche prietenă, albina $y$, dar pentru a ajunge la ea, trebuie să treacă prin parcelele altora, deci e posibil să trebuiască să treacă şi prin triburi străine. Albina $x$ este foarte generoasă şi vă recompensează cu $100$ de puncte dacă îi determinaţi drumul până la prietena $y$, drum care trece printr-un număr minim de triburi străine.
h2. Cerinţă
Scrieţi un program care determină numărul minim de triburi prin care trebuie sa treacă albina $x$ pentru a-şi îndeplini scopul.
h2. Date de intrare
Fişierul de intrare $stup.in$ ...
Pe prima linie a fişierului de intrare $stup.in$ se află $N M x y$, patru numere naturale separate prin câte un spaţiu, unde $x$, $y$ şi $N$ au semnificaţia din enunţ, iar $M$ este numărul de triburi formate. În continuare găsiţi descrierea fiecărui trib în următorul format $b{~1~}$, $b{~2~}$, ... $b{~M~}$. Primul trib este format din albinele $1$, $2$, ..., $b{~1~}$, al doilea din $b{~1~}+1$, $b{~1~}+2$, ..., $b{~2~}$ şi aşa mai departe. $b{~M~}$ va fi întotdeauna egal cu $N$, iar fiecare trib are cel puţin o albină.
h2. Date de ieşire
În fişierul de ieşire $stup.out$ ...
În fişierul de ieşire $stup.out$ se află un singur număr natural, reprezentând numărul minim de triburi cerut.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100 000$
* Pentru $20%$ din teste $N ≤ 23$.
* Pentru următoarele $30%$ din teste $M = N$, adică fiecare albină va forma un singur trib.
h2. Exemplu
table(example). |_. stup.in |_. stup.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 10 5 4 9
3 5 6 9 10
| 3
|
h3. Explicaţie
...
Triburile ce se formează sunt $(1, 2, 3)$, $(4, 5)$, $(6)$, $(7, 8, 9)$, $(10)$. Un drum ce trece prin $3$ triburi este $[4, 1, 9]$.
== include(page="template/taskfooter" task_id="stup") ==
