kcity

Kcity

In orasul $KCity$ exista $N$ intersectii, numerotate de la $1$ la $N$, interconectate prin $M$ strazi bidirectionale (fiecare strada leaga $2$ intersectii diferite). In ultimele luni, criminalitatea a crescut foarte mult in oras, astfel ca seful politiei doreste sa determine niste trasee pe care sa patruleze masinile politiei, pentru a mentine siguranta cetatenilor. Dupa parerea sefului politiei, fiecare traseu ar trebui sa fie de forma $x{~1~},x{~2~},..,x{~P~} (P ≥ 1)$, unde $x{~i~}$ sunt numerele unor intersectii si intre oricare doua intersectii consecutive de pe traseu, $x{~i~}$ si $x{~i+1~}$, exista o strada. Pentru a evita redundantele (care, in opinia sefului politiei, ar creste prea mult costurile), un traseu nu trebuie sa contina o intersectie de mai multe ori. In plus, fiecare intersectie trebuie sa apara in exact un singur traseu (daca ar exista o intersectie care sa nu apartina nici unui traseu, ar creste foarte mult rata criminalitatii in zona respectiva).

Ajutorul sefului politiei, insa, are o parere diferita. El crede ca fiecare traseu ar trebui sa fie de forma $x{~1~}, x{~2~},..,x{~P~} (P ≥ 4)$, unde $x~i~$ sunt numerele unor intersectii, $x{~1~}=x{~P~}$ si intre oricare doua intersectii consecutive de pe traseu, $x{~i~}$ si $x{~i+1~}$, exista o strada. Insa este si el de acord ca fiecare intersectie trebuie sa apartina exact unui singur traseu, iar un traseu nu trebuie sa contina o intersectie de mai multe ori (cu exceptia primei intersectii de pe traseu, care va fi si ultima).

Ajutorul sefului politiei, insa, are o parere diferita. El crede ca fiecare traseu ar trebui sa fie de forma $x{~1~}, x{~2~},..,x{~P~} (P ≥ 4)$, unde $x{~i~}$ sunt numerele unor intersectii, $x{~1~}=x{~P~}$ si intre oricare doua intersectii consecutive de pe traseu, $x{~i~}$ si $x{~i+1~}$, exista o strada. Insa este si el de acord ca fiecare intersectie trebuie sa apartina exact unui singur traseu, iar un traseu nu trebuie sa contina o intersectie de mai multe ori (cu exceptia primei intersectii de pe traseu, care va fi si ultima).

Deoarece departamentul de politie nu are la dispozitie prea multi oameni, se doreste determinarea numarului minim de trasee pe care trebuie trimise patrule de politie, in fiecare din cazuri (conform definitiei a ceea ce inseamna un traseu a sefului politiei si conform definitiei ajutorului sefului). Se mai stie si ca numele orasului ({$KCity$}) nu a fost ales intamplator, el provenind de la conditia cunoscuta doar de oficialitati, ca daca intre intersectiile $A$ si $B$ exista o strada, atunci $|A-B| ≤ K$.

h2. Date de iesire

In fisierul de iesire $kcity.out$ veti afisa numarul intreg $T$, reprezentand numarul minim de trasee care respecta parerea sefului politiei (daca $X &eq; 1$), respectiv numarul minim de trasee care respecta parerea ajutorului sefului (daca $X &eq; 2$). Daca nu se pot stabili trasee astfel incat sa fie respectate conditiile precizate in enunt, afisati $-1$.

In fisierul de iesire $kcity.out$ veti afisa numarul intreg $T$, reprezentand numarul minim de trasee care respecta parerea sefului politiei (daca $X=1$), respectiv numarul minim de trasee care respecta parerea ajutorului sefului (daca $X=2$). Daca nu se pot stabili trasee astfel incat sa fie respectate conditiile precizate in enunt, afisati $-1$.

h2. Restrictii

* Nu vor exista mai multe strazi intre aceeasi pereche de intersectii.
* In $50%$ din teste, $X=1$ (evident, in restul de $50%$ din teste, $X=2$).

h2. Exemplu

h2. Exemple

table(example). |_. kcity.in |_. kcity.out |
| 9 3 1 10

== include(page="template/taskfooter" task_id="kcity") ==

2160