Дан неориентированный граф, состоящий из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$.
Ваша задача — выбрать подмножество из ровно $$$k$$$ различных вершин данного графа. Пусть выбранные вершины — это $$$v_1, v_2, \cdots, v_k$$$. Тогда все эти вершины удаляются из графа, а вместо них добавляется новая вершина $$$V$$$, соединённая со всеми вершинами, с которыми была соединена каждая из вершин $$$v_1, v_2, \cdots, v_k$$$ (то есть если хотя бы одна вершина $$$v_i$$$ не соединена с какой-то вершиной $$$x$$$, то и $$$V$$$ не будет соединена с $$$x$$$).
Можно ли сделать так, чтобы вершина $$$V$$$ была соединена со всеми оставшимися вершинами графа? Если можно, то выведите выбранные вершины $$$v_1, v_2, \cdots, v_k$$$ в произвольном порядке.
Если существует несколько ответов, то выведите любой из них.
В первой строке записаны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \lt n \le 2000$$$) — количество вершин графа и требуемый размер подмножества.
В $$$i$$$-й из следующих $$$n$$$ строк записаны $$$n$$$ целых чисел $$$g_{i,1}, g_{i,2}, \dots, g_{i,n}$$$, где $$$g_{i, j}$$$ равно $$$1$$$, если между вершинами $$$i$$$ и $$$j$$$ в графе есть ребро, и $$$0$$$, если ребра нет. $$$g_{i, i} = 0$$$ для всех $$$i$$$. $$$g_{i, j} = g_{j, i}$$$ для всех $$$i$$$ и $$$j$$$.
Если не существует требуемого подмножества размера ровно $$$k$$$, то выведите $$$-1$$$.
Иначе выведите $$$k$$$ различных целых чисел от $$$1$$$ до $$$n$$$ — номера вершин выбранного подмножества в произвольном порядке. Если существует несколько ответов, то выведите любой из них.
5 20 0 1 1 10 0 1 1 11 1 0 0 01 1 0 0 01 1 0 0 0
1 2
5 20 0 1 1 10 0 0 1 11 0 0 0 01 1 0 0 01 1 0 0 0
-1
10 70 1 0 1 1 1 1 1 1 11 0 1 0 1 1 1 1 1 00 1 0 1 1 1 1 1 1 11 0 1 0 1 1 1 1 1 01 1 1 1 0 1 1 1 0 11 1 1 1 1 0 0 0 1 11 1 1 1 1 0 0 0 1 11 1 1 1 1 0 0 0 1 11 1 1 1 0 1 1 1 0 11 0 1 0 1 1 1 1 1 0
5 9 2 4 10 1 3
