Прямий, центрований та обернений порядок
Однією з класичних задач на структури даних є порядок обходу вершин бінарного дерева. Існує три стандартні варіанти обходу:
Прямий: відвідується корінь, ліве піддерево, праве піддерево;Центрований: відвідується ліве піддерево, корінь, праве піддерево;Обернений: відвідується ліве піддерево, праве піддерево, корінь;
Розглянемо рисунок:
При прямому, центрованому та оберненому обході ми отримаємо відповідно ABCDEF, CBAEDF та CBEFDA. В задачі необхідно знайти послідовність вершин при оберненому обході, якщо відомі прямий та центрований.
Вхідні дані
Перший рядок містить кількість тестів c (c ≤ 2000). Кожний наступний рядок є окремим тестом та містить кількість вершин у бінарному дереві n (1 ≤ n ≤ 52) та два рядки S[1] та S[2], що містять відповідно прямий та центрований обхід дерева. Вершини дерева пронумеровані різними символами з множин a..z та A..Z. Значення n, S[1] та S[2] розділені пропуском.
Вихідні дані
Для кожного тесту вивести послідовність вершин при оберненому обході дерева.