У вас есть \(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\), если это невозможно.
Выходные данные
Для каждого набора входных данных:
- Если не существует набора кнопок, после нажатия на которые горят не более \(\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\) ламп.
Примечание
В первом наборе входных данных требуется оставить включенными не более \(\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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|