Dany jest nieskierowany graf prosty o $kn$ wierzchołkach, w którym stopień każdego wierzchołka jest mniejszy niż $kd$.

Znajdź podzbiór $n$ wierzchołków taki, aby w podgrafie indukowanym przez ten zbiór stopień każdego wierzchołka był mniejszy niż $d$.

Wejście

W pierwszej linii podano cztery liczby całkowite dodatnie $k, n, d, m$.

W kolejnych $m$ liniach podano po dwie liczby całkowite dodatnie $u, v$, oznaczające krawędź między wierzchołkami $u$ i $v$.

Wyjście

Wypisz $n$ różnych liczb całkowitych z zakresu $1 \sim kn$, reprezentujących wybrany podzbiór wierzchołków.

Przykład

Wejście 1

2 3 2 9
1 2
2 3
3 1
4 5
5 6
6 4
1 4
2 5
3 6

Wyjście 1

3 4 5

Uwagi

Dla $100\%$ danych wejściowych zachodzą warunki: $2\leq k\leq 10$, $1\leq d\leq 10$, $1\leq n\leq 10^3$, $m\leq \frac{k(k-1)}2dn$.

Dla punktów danych $1\sim 2$: $kn\leq 20$.

Dla punktów danych $3\sim 5$: $d=1$.

Dla punktów danych $6\sim 8$: $k=2$.

Dla punktów danych $9\sim 10$: brak dodatkowych ograniczeń.