Пусть V = {1, 2, …, n}, а E {{u, v} | 1 ≤ u, v ≤ n}. Дерево T = (V, E) является связным графом и содержит в точности n-1 ребро. Например, дерево T_1 показано на рисунке ниже.
Для дерева T_1 имеем: V = {1,2,3,4,5,6,7}, E = {{4, 6}, {2, 6}, {6, 5}, {3, 5}, {5, 1}, {1, 7}}. Профессор Минтон обнаружил, как можно закодировать дерево. Код дерева представляет собой последовательность n - 2 чисел из V. Например, T_1 может кодироваться последовательностью <6, 5, 6, 5, 1>. Последовательность считается разрушенной, если некоторые числа пропущены в ней. Будем использовать алфавит x для представления пропущенных чисел в последовательности. По заданному дереву и разрушенной последовательности следует найти пропущенные числа.
Первая строка содержит количество тестов t. Вторая строка содержит значение n. Третья строка описывает дерево и содержит 2n - 2 числа, разделенные пробелом. Первая пара чисел задает первое ребро; вторая пара - второе ребро; и так далее. Четвертая строка содержит разрушенныую последовательность в виде n - 2 чисел, разделенных пробелом, причем некоторые из них обозначены символом x, что указывает на их отсутствие.
Содержит t строк, по одной для каждого теста. Каждая строка должна содержать последовательность пропущенных чисел в том же порядке как и на входе.