Петрик і розбиття масиву#7667

Петрик і розбиття масиву

1 секунда

64 мегабайти

Легка

Петрик — сумлінний учень, який мріє стати програмістом. На останньому уроці інформатики його улюблена вчителька запропонувала йому розв'язати таке завдання. Нехай $a_{1}, \dots, a_{N}$ a_1, \ldots, a_N — певна послідовність натуральних чисел. Петрику потрібно розділити послідовність чисел $1, 2, 3, \dots, N$ 1, 2, 3, \ldots, N на дві послідовності $b_{1}, \dots, b_{M}$ b_1, \ldots, b_M і $c_{1}, \dots, c_{K}$ c_1, \ldots, c_K таким чином, щоб:

• Кожне натуральне число $1 \leq r \leq N$ 1 \leq r \leq N було елементом рівно однієї з послідовностей $b$ або $c$ (тому $M + K = N$ M + K = N).

• Для кожної пари індексів $1 \leq i, j \leq M$ 1 \leq i, j \leq M, $i \neq = j$ i \neq j, числа $a_{b_{i}}$ a_{b_i} і $a_{b_{j}}$ a_{b_j} були взаємно простими.

• Для кожної пари індексів $1 \leq i, j \leq K$ 1 \leq i, j \leq K, $i \neq = j$ i \neq j, числа $a_{c_{i}}$ a_{c_i} і $a_{c_{j}}$ a_{c_j} були взаємно простими.

Взаємно простими називаються числа, найбільший спільний дільник яких дорівнює одиниці. Назвемо відповідний поділ послідовності $1, 2, 3, \dots, N$ 1, 2, 3, \ldots, N розбиттям послідовності $a_{i}$ a_i.

Розбиття послідовності може бути неоднозначне. Тому вчителька попросила Петрика знайти таке розбиття, що максимізує кількість елементів у послідовності $b_{i}$ b_i. Якщо існує кілька розбиттів, що максимізують кількість елементів у послідовності $b_{i}$ b_i, то потрібно знайти серед них таке, щоб послідовність $b_{i}$ b_i була лексикографічно найменшою.

Будемо казати, що послідовність $q_{1}, q_{2}, \dots, q_{W}$ q_1, q_2, \ldots, q_W є лексикографічно меншою за послідовність $p_{1}, p_{2}, \dots, p_{W}$ p_1, p_2, \ldots, p_W, якщо існує таке $i$ , що $q_{i} < p_{i}$ q_i < p_i, а для довільного $j < i$ j < i виконується $p_{j} = q_{j}$ p_j = q_j.

Напишіть програму, яка для заданої послідовності чисел $a$ знайде оптимальне розбиття послідовності чисел $1, 2, 3, \dots, N$ 1, 2, 3, \ldots, N на дві послідовності $b_{1}, \dots, b_{M}$ b_1, \ldots, b_M і $c_{1}, \dots, c_{K}$ c_1, \ldots, c_K.

Вхідні дані

У першому рядку вхідних даних записано число $Z$ ( $1 \leq Z \leq 3$ 1 \leq Z \leq 3) — кількість тестових вхідних даних (учителька кілька разів пропонувала Петрику розв'язати це завдання для різних вхідних даних).

Далі подаються $Z$ тестових даних у такому форматі.

У першому рядку даних міститься число $N$ ( $1 \leq N \leq 100000$ 1 \leq N \leq 100\,000) — кількість елементів у послідовності $a$ . У наступному рядку записано $N$ чисел, розділених одиничними пропусками, — елементи послідовності $a$ ( $1 \leq a_{i} \leq 2000000$ 1 \leq a_i \leq 2\,000\,000).

Вихідні дані

Для кожних тестових даних виведіть у вихідний файл в одному рядку число $M$ — кількість елементів у послідовності $b$ , а у другому — $M$ натуральних чисел — у порядку зростання номери елементів послідовності $a$ , що увійшли до послідовності $b$ .

Якщо так трапиться, що вчителька помилилась і не існує жодного розбиття послідовності $a$ , то виведіть в одному рядку $- 1$ .

Приклади

Приклад 1

Примітка

У першому наборі тестових даних не можна отримати розбиття, де в послідовності $b$ містилися б усі елементи $1, 2, \dots, N$ 1, 2, \ldots, N, тому що числа $2$ і $4$ не взаємно прості. А в наступному наборі тестових даних взагалі не існує жодного розбиття послідовності $a$ .

Оцінювання

Набір тестів складається з $4$ блоків, для кожного з яких виконуються такі умови:

$1.$ $24%$ балів: $N \leq 15$ N \leq 15, $1 \leq a_{i} \leq 2000000$ 1 \leq a_i \leq 2\,000\,000.

$2.$ $24%$ балів: $N \leq 1000$ N \leq 1000, $1 \leq a_{i} \leq 2000000$ 1 \leq a_i \leq 2\,000\,000.

$3.$ $30%$ балів: $N \leq 20000$ N \leq 20\,000, $1 \leq a_{i} \leq 2000000$ 1 \leq a_i \leq 2\,000\,000.

$4.$ $22%$ балів: $N \leq 100000$ N \leq 100\,000, $1 \leq a_{i} \leq 2000000$ 1 \leq a_i \leq 2\,000\,000.