Задача №114648. Разрежь ребро, спаси дерево
Прогуливаясь по центру города, Дима нашёл корневое дерево на \(n\) вершинах: неориентированный связный граф c \(n\) вершинами и \(n - 1\) ребром, в котором выбрана одна вершина, называемая корнем . Как известно, в подобном графе между любыми двумя вершинами существует единственный простой путь.
Назовём вершину \(u\) предком вершины \(v\) если вершина \(u \neq v\) и вершина \(u\) лежит на единственном простом пути от вершины \(v\) до корня дерева. В частности, корень дерева является предком всех остальных вершин. По найденному дереву Дима построил следующий граф: вершинами графа являются вершины дерева, а вершины \(u\) и \(v\) соединены неориентированным ребром тогда и только тогда, когда вершина \(u\) является предком вершины \(v\).
Петя увидел граф, который построил Дима, и теперь интересуется: какое же дерево нашёл Дима? Помогите ему найти ответ на этот каверзный вопрос.
В первой строке задано одно целое число \(T\) (\(1 \leq T \leq 100\,000\)) — количество случаев, для которых требуется решить задачу. Затем следуют описания тестовых случаев. Каждый тест задаётся в следующем формате.
В первой строке задано два целых числа \(n\) и \(m\) (\(1 \leq n \leq 100\,000, 0 \leq m \leq 100\,000\)) — количество вершин и рёбер в графе, который увидел Петя.
В следующих \(m\) строках заданы пары целых чисел \(u_i\) и \(v_i\) (\(1 \leq u_i, v_i \leq n, u_i \neq v_i\)), обозначающие ребро между вершинами \(u_i\) и \(v_i\) в графе. Гарантируется, что в графе нет кратных рёбер.
Обозначим за \(S_n\) сумму \(n\) по всем тестовым случаям в тесте, а за \(S_m\) — сумму \(m\) по всем тестовым случаям в тесте, тогда гарантируется, что \(S_n, S_m \leq 500\,000\).
Для каждого тестового случая выведите ответ в следующем формате.
В первой строке выведите «Yes», если требуемое дерево существует, и «No» иначе. В случае, если дерево существует, во второй строке выведите \(n\) целых чисел, описывающих дерево. Для вершины \(i\) выведите \(0\) в случае, если вершина \(i\) — корень дерева, в противном случае выведите одно целое число \(p_i\) — номер непосредственного предка вершины \(i\) в дереве. Непосредственным предком вершины \(v\) в дереве называется первая отличная от \(v\) вершина на единственном простом пути от вершины \(v\) до корня дерева. Если существует несколько подходящих деревьев, выведите любое.
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
| Дополнительные ограничения | ||||
| Группа | Баллы | \(S_n\), \(S_m\) | \(n\), \(m\) | Комментарий |
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 21 | \(S_n, S_m \leq 50\) | \(n, m \leq 10\) | |
| 2 | 12 | \(S_n, S_m \leq 1000\) | \(n, m \leq 100\) | |
| 3 | 15 | \(S_n, S_m \leq 10\,000\) | \(n, m \leq 5000\) | |
| 4 | 52 | – | – | |
5 1 0 3 2 1 2 2 3 3 3 1 2 1 3 2 3 4 2 1 4 2 3 7 10 1 2 1 3 2 4 2 5 3 6 3 7 1 4 1 5 1 6 1 7
Yes 0 Yes 2 0 2 Yes 0 1 2 No Yes 0 1 1 2 2 3 3