Дан неориентированный простой граф с $kn$ вершинами, в котором степень каждой вершины меньше $kd$.

Найдите подмножество из $n$ вершин такое, что в порожденном подграфе степень каждой вершины меньше $d$.

Входные данные

В первой строке заданы четыре целых положительных числа $k, n, d, m$.

В следующих $m$ строках заданы по два целых положительных числа $u, v$, обозначающих ребро графа.

Выходные данные

Выведите $n$ различных целых чисел от $1$ до $kn$, представляющих выбранное подмножество вершин.

Примеры

Пример 1

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

Выходные данные 1

3 4 5

Ограничения

Для $100\%$ данных гарантируется, что $2\leq k\leq 10$, $1\leq d\leq 10$, $1\leq n\leq 10^3$, $m\leq \frac{k(k-1)}2dn$.

Для тестов $1\sim 2$: $kn\leq 20$.

Для тестов $3\sim 5$: $d=1$.

Для тестов $6\sim 8$: $k=2$.

Для тестов $9\sim 10$: без дополнительных ограничений.