На производстве расположены \(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\) при этом обязано быть наименьшим, при котором можно подключить максимальное количество роботов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
0
0
2
1 2
1 1
5
0
0
2 4 5
2 3 5
2 3 4
7
1 2
2 1 7
0
2 5 6
2 4 6
2 4 5
1 2
7
1 7
0
3 4 5 6
3 3 5 6
3 3 4 6
3 3 4 5
1 1
|
1 0
2 0
4 1
1 + 4 - 3
6 2
4 + 2 - 1
3 + 6 - 5
7 3
3 + 7 - 1
2 + 6 - 5
1 + 6 - 4
|