Злам коду дерева#2543
Нехай \textbf{V} = \{1, 2, \ldots, n\} і \textbf{E} = \{\{u, v\} \mid 1 \leq u, v \leq n\}. Дерево \textbf{T} = (V, E) — це зв'язний граф, що містить рівно n - 1 ребер. Наприклад, дерево \textbf{T}_1 показано на рисунку нижче.
У \textbf{T}_1 маємо \textbf{V} = \{1, 2, 3, 4, 5, 6, 7\}, \textbf{E} = \{\{4, 6\}, \{2, 6\}, \{6, 5\}, \{3, 5\}, \{5, 1\}, \{1, 7\}\}. Професор Мінтон відкрив спосіб кодування дерева. Код дерева — це послідовність з n - 2 чисел із множини . Наприклад, \textbf{T}_1 можна закодувати послідовністю <6, 5, 6, 5, 1>. Якщо деякі числа відсутні в послідовності, то вона вважається неповною. Для позначення відсутнього числа використовується символ . Дано дерево і неповну послідовність; потрібно визначити відсутні числа.
У першому рядку знаходиться кількість тестових випадків . У другому рядку дано ціле число . У третьому рядку описується дерево: 2n - 2 чисел через пробіл. Кожна пара чисел описує ребро. Перша пара — перше ребро, друга пара — друге, і так далі. У четвертому рядку міститься послідовність з n - 2 чисел, де деякі числа замінені літерою , щоб вказати на їх відсутність.
Для кожного тестового випадку виведіть одним рядком послідовність відсутніх чисел у тому порядку, у якому вони зустрічаються у вхідній послідовності.
Приклад 1