Обход в глубину

Примеры

Примеры

#####################
###O11###...###M13###
###......O22......###
###...######M22######
###BBB###M31###M11###
###...O32...M33O31###
#####################

На производстве расположены \(n\) роботов, пронумерованных от \(1\) до \(n\). Любая пара роботов может быть либо соединена проводом, либо нет. Известно, что \(i\)-й робот соединен с \(k_i\) другими роботами с номерами \(v_{i,1}, \ldots, v_{i,k_i}\). Провода двухсторонние, то есть если \(i\) связан с \(j\), то \(j\) связан с \(i\) (иными словами, \((i, j)\) и \((j, i)\) — это один и тот же провод).

Вы находитесь рядом с роботом номер \(n\). Роботом номер \(t\) можно управлять, если он связан с \(n\)-м некоторой цепочкой проводов, то есть

• либо если \(t = n\);

• либо если существуют такие \(i_1, \ldots, i_k\), что \(i_1 = n\), \(i_k = t\), и любые два соседних в этой последовательности робота \(i_j\) и \(i_{j + 1}\) связаны проводом.

Любому из роботов, которыми можно управлять, можно послать команду <<извлеки второй конец подключенного к себе провода и подключи его к другому роботу>>. Иными словами, если роботом номер \(t\) можно управлять, и есть провод, соединяющий его с роботом номер \(x\), то можно заменить провод \((t, x)\) на провод \((t, y)\) для любого \(y \neq t\), еще не связанного проводом с \(t\). Обратите внимание, что после этого вы можете потерять управление над \(t\)-м роботом, если единственная связь \(t\)-го с \(n\)-м проходила через \(x\)-й.

Ваша задача — получить управление над максимально возможным количеством роботов на производстве. Найдите это количество и самую короткую последовательность действий, приводящую к такому исходу.

Формат входных данных
В первой строке записано целое число \(T\) (\(1 \le T \le 1000\)) — количество наборов входных данных в тесте.

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

Затем следуют \(n\) строк, в \(i\)-й из которых записаны числа \(k_i\) (\(0 \le k_i \le n - 1\)) и \(v_{i,1}, \ldots, v_{i,k_i}\) (\(1 \le v_{i,j} \le n\); \(v_{i,j} \neq i\)) — количество проводов, подключенных к \(i\)-му роботу, и номера роботов на противоположных концах этих проводов. Гарантируется, что данные корректны: никакие два провода не соединяют одну и ту же пару роботов, и если \(j \in v_i\), то \(i \in v_j\).

Также гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\) и сумма количества проводов по всем наборам входных данных не превосходит \(1.5 \cdot 10^5\).

Формат выходных данных
Для каждого набора входных данных выведите в первой строке через пробел максимальное количество роботов, управление над которыми можно получить, и количество действий \(k\), которое для этого понадобится.

В следующих \(k\) строках выведите сами описания действий в формате <<\(y\) + \(t\) - \(x\)>> (\(1 \leq t, x, y \leq n\); \(x \neq y\)). Каждая такая строка соответствует замене провода \((t, x)\) на провод \((t, y)\).

Если возможных ответов несколько, выведите любой. Обратите внимание, что \(k\) при этом обязано быть наименьшим, при котором можно подключить максимальное количество роботов.

На производстве расположены \(n\) роботов, пронумерованных от \(1\) до \(n\). Любая пара роботов может быть либо соединена проводом, либо нет. Всего на производстве \(m\) проводов и \(i\)-й из них сейчас соединяет роботов с номерами \(a_i\) и \(b_i\).

Вы находитесь рядом с роботом номер \(1\). Роботом номер \(t\) можно управлять, если он связан с первым некоторой цепочкой проводов, то есть

• либо если \(t = 1\);

• либо если существуют такие \(i_1, \ldots, i_k\), что \(i_1 = 1\), \(i_k = t\), и любые два соседних в этой последовательности робота \(i_j\) и \(i_{j + 1}\) связаны проводом.

Любому из роботов, которыми можно управлять, можно послать команду <<извлеки второй конец подключенного к себе провода и подключи его к другому роботу>>. Иными словами, если роботом номер \(t\) можно управлять, и есть провод, соединяющий его с роботом номер \(x\), то можно заменить провод \((t, x)\) на провод \((t, y)\) для любого \(y \neq t\), еще не связанного проводом с \(t\). Обратите внимание, что после этого вы можете потерять управление над \(t\)-м роботом, если единственная связь \(t\)-го с первым проходила через \(x\)-й.

Ваша задача — получить управление над максимально возможным количеством роботов на производстве. Найдите это количество и самую короткую последовательность действий, приводящую к такому исходу.

Формат входных данных
В первой строке записано целое число \(T\) (\(1 \le T \le 1000\)) — количество наборов входных данных в тесте.

Первая строка каждого набора входных данных содержит целые числа \(n\) и \(m\) (\(1 \leq n \leq 10^5\); \(0 \leq m \leq 1.5 \cdot 10^5\)) — количество роботов и количество проводов, соответственно.

В следующих \(m\) строках дано описание проводов: в \(i\)-й строке даны целые числа \(a_i\) и \(b_i\) (\(1 \leq a_i, b_i \leq n\); \(a_i \neq b_i\)) — номера роботов, соединенных \(i\)-м проводом. Гарантируется, что никакие два провода не соединяют одну и ту же пару роботов.

Также гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\) и сумма \(m\) по всем наборам входных данных не превосходит \(1.5 \cdot 10^5\).

Формат выходных данных
Для каждого набора входных данных выведите в первой строке через пробел максимальное количество роботов, управление над которыми можно получить, и количество действий \(k\), которое для этого понадобится.

В следующих \(k\) строках выведите сами описания действий по одному на каждой строке. Описание действия должно состоять из трех целых чисел \(t\), \(x\) и \(y\) (\(1 \leq t, x, y \leq n\); \(x \neq y\)), означающих, что робот номер \(t\) меняет провод \((t, x)\) на провод \((t, y)\).

Если возможных ответов несколько, выведите любой. Обратите внимание, что \(k\) при этом обязано быть наименьшим, при котором можно подключить максимальное количество роботов.

Каждый раз, когда в мире происходит значимое событие, наша реальность разветвляется на несколько — в зависимости от исхода этого события. После этого существует уже не только наша основная реальность, но и ответвившиеся от неё в моменты появления разных исходов.

Однажды один архимаг решил сделать мир лучше. Такая грандиозная задача не под силу одному архимагу, поэтому он решил найти самого себя ещё в \(K\) реальностях и выполнить эту задачу вместе. Проведённое теоретическое исследование показало, что, кроме реальности, в которой находится именно он, существует ещё \(N - 1\) реальностей. Для удобства они были занумерованы числами от \(1\) до \(N\), при этом его собственная реальность имеет номер \(1\), а посетить ему необходимо реальности с номерами \(2, 3, \ldots, K + 1\).

Как уже говорилось, каждая реальность когда-то ответвилась от некоторой другой, за исключением одной Начальной реальности, которая существовала всегда (её номер может оказаться каким угодно; считается, что она появилась в момент времени \(0\)). Исследование показало, что реальность с номером \(i\) ответвилась от реальности с номером \(P_i\) в момент времени \(T_i\). Из каждой реальности с номером \(i\) архимаг может переместиться

• в любую ответвившуюся от неё, то есть в любую \(j\), такую что \(P_j = i\);

• в \(P_i\), если \(i\) — не Начальная реальность.

Другими словами, возможны лишь переходы вида \(i \leftrightarrows P_i\). На каждый такой переход в любую сторону архимаг затрачивает \(T_i-T_{P_i} > 0\) условных единиц энергии.

Требуется найти минимальное количество энергии, которое потребуется архимагу, чтобы, начав в реальности с номером \(1\), посетить все реальности с номерами от \(2\) до \(K + 1\) (в любом порядке) и затем вновь вернуться в \(1\). Любую реальность при этом разрешается посещать сколько угодно раз.
Формат входных данных

Сначала вводятся два целых числа \(N\) и \(K\) (\(0 \leqslant K < N \leqslant 100\,000\)): количество доступных реальностей и количество реальностей, которые необходимо посетить. Далее идёт \(N\) пар целых чисел, \(i\)-я пара — это \(P_i\) и \(T_i\) (\(1 \leqslant P_i \leqslant N\), \(0 \leqslant T_i \leqslant 10^6\); для Начальной реальности \(P_i=T_i=0\)).

Гарантируется, что ответвившаяся реальность появилась строго позже породившей (\(T_i > T_{P_i})\), и что маг может при желании добраться до любой из \(N\) реальностей.

Формат выходных данных
Выведите единственное число \(E\) — минимальную возможную энергию, которая потребуется архимагу для путешествия.

• 2 ≤ N ≤ 2000
• 0 ≤ M ≤ min(2000, N*(N-1)
• 1 ≤ Ai, Bi ≤ N
• Ai не равно Bi.
• Пары (Ai,Bi) уникальны.
• Все значения во входных данных целые числа.

Примеры

5 4
1 3
1 2
2 3
2 4

4
4
3
4
1

Примеры

4
11 10 11 11
1 2
2 3
2 4

Примеры

Примеры

Примеры

Примеры

Из прямоугольного листа клетчатой бумаги (M строк, N столбцов) удалили некоторые клетки. На сколько кусков распадётся оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.

В первой строке находятся числа M и N, в следующих M строках - по N символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана - точка. 1 <= M, N <= 100.

Вывести одно число.
 

Примеры

5 10
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####

5

Примеры

Примеры