Корова Бесси только что закончила курс графовых алгоритмов.
И выполнила кодирование своего собственного графического визуализатора! В настоящее время ее визуализатор графов только
способен визуализировать корневые деревья с узлами различных значений, и он может
выполнять только один вид операции: слияние.
В частности, операция слияния берет любые два различных узла в дереве с
один и тем же родителем и объединяет их в один узел со значением, равным максимальному
значений двух объединенных узлов, а потомки — объединение всех потомков
объединенных узлов (если есть).
К сожалению, после того, как Бесси выполнила несколько операций слияния с деревом, ее
программа дала сбой, потеряв историю выполненных ею операций слияния. Все, что
Бесси помнит, что это дерево, с которого она начала, и дерево, которым она закончила после того
как она выполнила все свои операции слияния.
Учитывая ее начальное и конечное деревья, определите последовательность операций слияния,
которые могла бы выполнить Бесси. Гарантируется, что последовательность существует.
Каждый вход состоит из \(T\) (\(1\le T\le 100\)) независимых подтестов.
Гарантируется, что сумма \(N\) по всем тестам не превышает \(1000\).
ФОРМАТ ВВОДА (ввод поступает с терминала/стандартного ввода):
Первая строка содержит
\(T\), количество независимых тестов. Каждый подтест
оформляется следующим образом.
Первая строка каждого подтеста содержит количество узлов \(N\).
(\(2 \leq N \leq 1000\)) в исходном дереве Бесси, которые имеют значения \(1\dots N\).
Каждая из следующих \(N-1\) строк содержит два значения узла \(v_i\), разделенных пробелом, и
\(p_i\) (\(1 \leq v_i, p_i \leq N\)), указывающий, что узел со значением \(v_i\) является
дочерним узла со значением \(p_i\) в исходном дереве Бесси.
Следующая строка содержит количество узлов \(M\) (\(2 \leq M \leq N\)) в таблице Бесси.
в финальном дереве.
Каждая из следующих \(M-1\) строк содержит два значения узла \(v_i\), разделенных пробелом, и
\(p_i\) (\(1 \leq v_i, p_i \leq N\)), указывающий, что узел со значением \(v_i\) является
дочерний узел узла со значением \(p_i\) в конечном дереве Бесси.
ФОРМАТ ВЫВОДА (вывод на терминал / стандартный вывод):
Для каждого теста выведите количество операций слияния, а затем
упорядоченная последовательность операций слияния такой длины, по одной на строку.
Каждая операция слияния должна быть отформатирована как два отдельных файла, разделенных пробелом.
целые числа: значения двух узлов для слияния в любом порядке.
Если решений несколько, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
8
7 5
2 1
4 2
5 1
3 2
8 5
6 2
4
8 5
5 1
6 5
|
4
2 5
4 8
3 8
7 8
|