E. Минимальное покрытие путями
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Несмотря на название задачи, мы надеемся, что она не является NP-трудной.

Это интерактивная задача.

Для корневого дерева$$$^{\text{∗}}$$$ $$$T$$$ размера $$$m$$$, где каждой вершине $$$i$$$ сопоставлено значение $$$a_i$$$, определим вертикальный путь как последовательность вершин $$$[s_1,s_2,\ldots,s_p]$$$, такую, что $$$s_{i+1}$$$ является ребёнком $$$s_i$$$ для всех $$$1 \leq i \lt p$$$. Вертикальный путь называется хорошим, если $$$\operatorname{gcd}(a_{s_1},a_{s_2},\ldots,a_{s_p}) \neq 1$$$$$$^{\text{†}}$$$. Определим $$$f(T)$$$ как минимальное количество хороших вертикальных путей, таких, что каждая вершина входит ровно в один хороший путь.

Дано странное корневое дерево из $$$n$$$ вершин, где вершина $$$1$$$ является корнем. Дерево обладает свойством, что у каждой вершины все дети имеют номер больше, чем она сама. Обозначим через $$$S(u)$$$ поддерево вершины $$$u$$$. То есть $$$S(u)$$$ содержит все вершины $$$v$$$, такие, что кратчайший путь от вершины $$$1$$$ до вершины $$$v$$$ проходит через вершину $$$u$$$, а также все рёбра, оба конца которых принадлежат множеству таких вершин.

Вам требуется найти $$$f(S(n)), f(S(n-1)), \ldots, f(S(1))$$$. Однако магический оракул скрывает от вас информацию о дереве! А именно, оракул сообщает вам информацию о вершине $$$x$$$ только после того, как прочитает ваш результат для $$$f(S(x+1))$$$. Другими словами, вы должны решать эту задачу в онлайн-режиме, начиная с вершины $$$n$$$ и заканчивая вершиной $$$1$$$.

$$$^{\text{∗}}$$$Деревом называется связный граф без циклов. Корневым деревом называется дерево, в котором одна из вершин специальная и называется корнем. Родителем вершины $$$v$$$ называется первая вершина на простом пути от $$$v$$$ до корня. У корня нет родителя. Ребенком вершины $$$v$$$ называется любая вершина $$$u$$$, для которой $$$v$$$ является родителем.

$$$^{\text{†}}$$$Здесь $$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.

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

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

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

Далее следуют $$$n$$$ строк. В $$$i$$$-й из них содержится информация о вершине $$$j=n-i+1$$$ в следующем формате.

  • $$$a_j \; k \; c_1 \; c_2 \; \ldots \; c_k$$$: вершине $$$j=n-i+1$$$ сопоставлено значение $$$a_j$$$, и у неё есть $$$k$$$ детей с номерами $$$c_1,c_2,\ldots,c_k$$$.

Для каждой вершины $$$j$$$ гарантируется, что $$$2 \le a_j \le 10^{18}$$$ и $$$j+1 \le c_i \le n$$$.

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

Гарантируется, что сумма $$$k$$$ по всем вершинам в одном наборе входных данных равняется ровно $$$n-1$$$, а рёбра образуют корректное корневое дерево.

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

Для каждого набора входных данных вы должны вывести $$$n$$$ строк, где в $$$i$$$-й из них должно содержаться значение $$$f(S(n-i+1))$$$.

Обратите внимание, что эта задача технически является интерактивной. А именно, интерактор выдаёт вам следующую порцию информации только после того, как прочитает вашу очередную строку вывода.

После вывода каждой строки необходимо вывести символ конца строки и сбросить буфер вывода$$$^{\text{∗}}$$$. Иначе вы получите вердикт Решение «зависло».

$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Входные данные
4
5
11 0
7 0
5 0
3 2 4 5
2 2 2 3
5
10 0
8 0
6 0
4 0
2 4 2 3 4 5
6
221 0
143 1 6
77 1 5
35 1 4
15 1 3
6 1 2
3
1000000000000000000 0
999999999999999998 0
999999999999999998 2 3 2
Выходные данные
1
1
1
3
5
1
1
1
1
4
1
1
2
2
3
3
1
1
2
Примечание

В первом наборе входных данных, поскольку все значения $$$a_i$$$ взаимно просты, невозможно покрыть более одной вершины каждым путём. Поэтому значение $$$f(S(1))$$$ равно $$$5$$$.

Во втором наборе входных данных можно проверить, что $$$f(S(1))=4$$$, используя следующие $$$4$$$ вертикальных пути:

  • $$$[1,2]$$$. НОД этого вертикального пути равен $$$\operatorname{gcd}(2,4)=2$$$.
  • $$$[3]$$$. НОД этого вертикального пути равен $$$\operatorname{gcd}(6)=6$$$.
  • $$$[4]$$$. НОД этого вертикального пути равен $$$\operatorname{gcd}(8)=8$$$.
  • $$$[5]$$$. НОД этого вертикального пути равен $$$\operatorname{gcd}(10)=10$$$.

Поскольку ни один из вертикальных путей не имеет НОД, равный $$$1$$$, это решение корректно. Кроме того, можно показать, что невозможно покрыть все вершины менее чем $$$4$$$ вертикальными путями.