< На список задач
      

Задача H. Схемы космических маршрутов

Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 Mb

Таинственный враг из далекого будущего собирается уничтожить Специальный Корпус в прошлом, до его возникновения, а затем захватить всю галактику. Чтобы предотвратить катастрофу, Джеймс Боливар ди Гриз вынужден отправиться на 30 тысяч лет назад на планету, называемую то ли "Грязь", то ли "Земля". Некоторые утверждают, что эта планета и была мифическая прародина всего человечества.

Отправка в прошлое должна пройти скрытно. В Лиге есть несколько компаний, которые занимаются перевозками во времени и пространстве. Схемы передвижений в каждой компании засекретили, пометив точки маршрута цифрами и маленькими латинскими буквами, причем каждая компания ввела свою систему пометки этих точек. С большим трудом Джим достал схемы их маршрутов. Каждая такая схема представляет собой дерево, вершины которого и есть точки маршрута.

А еще секретные агенты Лиги узнали, что преступники воспользовались услугами одной из компаний, прошли всеми маршрутами этой компании, причем схема их передвижений тоже представлена в форме дерева. К сожалению, корни у деревьев могут быть различны, поскольку каждый составлял схему от той планеты, на которой находился - транспортные компании начинали от планеты, где находится их главный офис, а преступники - от той неизвестной Джиму планеты, где они построили временную базу. Этот факт существенно усложняет задачу определения совпадения схем. Но Джиму обязательно надо понять, совпадают эти схемы или нет.

Джим знает, что транспортировка между пунктами осуществляется в двух направлениях, поэтому попытался нарисовать примеры эквивалентных и неэквивалентных схем:

Входные данные

Во входном файле задано несколько вариантов пар схем для сравнения. В первой строке задано целое число N (N <= 10) - количество вариантов. Далее во входном файле содержатся 2*N строк, в каждой из которых указана запись каждого из двух сравниваемых маршрутов. Дерево описывается в порядке от корня к потомкам до тех пор, пока не будет достигнут лист. Такой список заканчивается знаком "#". Таким образом, такой знак означает конец описания вершины. Затем описание дерева продолжается с последней неописанной вершины. В конце строки допускаются незначащие пробелы. Например, дерево из примеров представимо следующим описанием:

Схема       Строка описания       
abd#e##cf##g##           

Выходные данные

В результирующий файл для каждого варианта исходных данных Вы должны вывести ответ на задачу - слово "YES" или "NO" в зависимости от того, совпадают схемы маршрутов или нет.

Пример входного и выходного файлов

        input.txt               output.txt       
3
abd#e##c## 
xyu##z##
abd#e##cf##g## 
xyv##u#zw#t###
12a###
123###
         
NO
YES
YES