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&eq;1$, atunci se cere determinarea numarului minim de trasee care corespund cu parerea sefului politiei; daca $X&eq;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&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$.

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&eq;1$.

h2. Exemplu
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") ==