Pinely Round 3 (Div. 1 + Div. 2) |
---|
Закончено |
У вас есть $$$n$$$ ламп, пронумерованных от $$$1$$$ до $$$n$$$. Изначально все лампы выключены.
У вас также есть $$$n$$$ кнопок. Кнопка $$$i$$$ переключает все лампы, чей индекс кратен $$$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$$$.
Для каждого набора входных данных:
44 05 24 15 115 97 88 99 1010 911 112 213 314 415 55 41 22 33 44 5
-1 4 3 5 1 2 3 8 9 10 1 5
В первом наборе входных данных требуется оставить включенными не более $$$\lfloor 4/5 \rfloor$$$ ламп, а это значит, что ни одна лампа не может остаться включенной в конце. Можно показать, что при нажатии хотя бы одной кнопки в конце не может оказаться $$$0$$$ включенных ламп.
Во втором наборе входных данных можно нажать кнопки $$$3$$$, $$$5$$$, $$$1$$$, $$$2$$$.
Это решение корректно, потому что
В третьем наборе входных данных нажатие кнопок $$$8$$$, $$$9$$$, $$$10$$$ включает только лампы $$$8$$$, $$$9$$$, $$$10$$$.
Название |
---|