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~} &eq; 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 intrare
...
Prima linie a fisierului de intrare $kcity.in$ contine $4$ numere intregi, separate printr-un spatiu: $N$, $K$, $X$ si $M$. Fiecare din urmatoarele $M$ linii contine cate $2$ numere intregi, separate printr-un spatiu, $A$ si $B$, avand semnificatia ca exista o strada intre intersectia $A$ si intersectia $B$. Daca $X=1$, atunci se cere determinarea numarului minim de trasee care corespund cu parerea sefului politiei; daca $X=2$, se cere determinarea numarului minim de trasee ce corespund cu parerea ajutorului sefului.
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=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
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1000$
* $1 ≤ K ≤ 6$
* $0 ≤ M ≤ 6000$
* 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 |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 9 3 1 10
1 4
2 4
1 2
3 6
6 9
9 7
7 8
8 5
5 3
4 7
| 1 |
| 9 3 2 10
1 4
2 4
1 2
3 6
6 9
9 7
7 8
8 5
5 3
4 7
| 2 |
h3. Explicatie
...
== include(page="template/taskfooter" task_id="kcity") ==
