E. Несколько ламп
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Kid2Will - Fire Aura
⠀

У вас есть $$$n$$$ ламп, пронумерованных от $$$1$$$ до $$$n$$$. Изначально все лампы выключены.

У вас также есть $$$n$$$ кнопок. Кнопка $$$i$$$ переключает все лампы, чей индекс кратен $$$i$$$. Когда лампа переключается, если она была выключена, то она включается, а если была включена, то выключается.

Вы должны нажать несколько кнопок в соответствии со следующими правилами.

  • Вы должны нажать хотя бы одну кнопку.
  • Вы не можете нажимать одну и ту же кнопку несколько раз.
  • Вам даны $$$m$$$ пар $$$(u_i, v_i)$$$. Если вы нажмете кнопку $$$u_i$$$, вы также должны нажать кнопку $$$v_i$$$ (либо до, либо после нажатия кнопки $$$u_i$$$). Обратите внимание, что если вы нажимаете кнопку $$$v_i$$$, то вам не нужно нажимать кнопку $$$u_i$$$.

Вы не хотите тратить слишком много электричества. Найдите способ нажимать кнопки так, чтобы в конце горело не более $$$\lfloor n/5 \rfloor$$$ ламп, или выведите $$$-1$$$, если это невозможно.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq m \leq 2 \cdot 10^5$$$) — количество ламп и количество пар, соответственно.

Каждая из следующих $$$m$$$ строк содержит по два целых числа $$$u_i$$$, $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$). Если вы нажимаете кнопку $$$u_i$$$, вы также должны нажать кнопку $$$v_i$$$. Гарантируется, что пары $$$(u_i, v_i)$$$ различны.

Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных:

  • Если не существует набора кнопок, после нажатия на которые горят не более $$$\lfloor n/5 \rfloor$$$ ламп, выведите одну строку, содержащую $$$-1$$$.
  • В противном случае выведите две строки. Первая строка должна содержать целое число $$$k$$$ ($$$1 \le k \le n$$$) — количество нажатых кнопок. Вторая строка должна содержать $$$k$$$ целых чисел $$$b_1, b_2, \dots, b_k$$$ ($$$1 \le b_i \le n$$$) — индексы нажатых кнопок (в любом порядке). Индексы $$$b_i$$$ должны быть различными, и в конце должно быть включено не более $$$\lfloor n/5 \rfloor$$$ ламп.
Пример
Входные данные
4
4 0
5 2
4 1
5 1
15 9
7 8
8 9
9 10
10 9
11 1
12 2
13 3
14 4
15 5
5 4
1 2
2 3
3 4
4 5
Выходные данные
-1
4
3 5 1 2
3
8 9 10
1
5
Примечание

В первом наборе входных данных требуется оставить включенными не более $$$\lfloor 4/5 \rfloor$$$ ламп, а это значит, что ни одна лампа не может остаться включенной в конце. Можно показать, что при нажатии хотя бы одной кнопки в конце не может оказаться $$$0$$$ включенных ламп.

Во втором наборе входных данных можно нажать кнопки $$$3$$$, $$$5$$$, $$$1$$$, $$$2$$$.

  • Изначально все лампы выключены;
  • после нажатия кнопки $$$3$$$, лампы, чей индекс кратен $$$3$$$ (т.е. $$$3$$$), переключаются, так что лампа $$$3$$$ включается;
  • после нажатия кнопки $$$5$$$, лампы, чей индекс кратен $$$5$$$ (т.е. $$$5$$$) переключаются, поэтому лампы $$$3$$$, $$$5$$$ включены;
  • после нажатия кнопки $$$1$$$, лампы, чей индекс кратен $$$1$$$ (т.е. $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$) переключаются, поэтому становятся включенными лампы $$$1$$$, $$$2$$$, $$$4$$$;
  • после нажатия кнопки $$$2$$$, лампы, чей индекс кратен $$$2$$$ (т.е. $$$2$$$, $$$4$$$) переключаются, поэтому остается включенной только лампа $$$1$$$.

Это решение корректно, потому что

  • вы нажали хотя бы одну кнопку;
  • вы нажали каждую кнопку не более одного раза;
  • вы нажали кнопку $$$u_2 = 5$$$, что означает, что вы должны были также нажать кнопку $$$v_2 = 1$$$, и кнопка $$$1$$$ была нажата;
  • в конце горит только лампа $$$1$$$.

В третьем наборе входных данных нажатие кнопок $$$8$$$, $$$9$$$, $$$10$$$ включает только лампы $$$8$$$, $$$9$$$, $$$10$$$.