Fişierul intrare/ieşire:	stup.in, stup.out	Sursă	Grigore Moisil 2011, Clasele 11-12
Autor	Perticas Catalin	Adăugată de	Marius Stroe •Marius
Timp execuţie pe test	0.075 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Stup

Î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.

Cerinţă

Scrieţi un program care determină numărul minim de triburi prin care trebuie sa treacă albina x pentru a-şi îndeplini scopul.

Date de intrare

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₁, b₂, ... b_M. Primul trib este format din albinele 1, 2, ..., b₁, al doilea din b₁+1, b₁+2, ..., b₂ şi aşa mai departe. b_M va fi întotdeauna egal cu N, iar fiecare trib are cel puţin o albină.

Date de ieşire

În fişierul de ieşire stup.out se află un singur număr natural, reprezentând numărul minim de triburi cerut.

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.

Exemplu

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].

Cum se trimit solutii?