Клингонская война
Война вспыхнула между двумя кланами клингонов. Однако война у клингонов — это не просто сражение; она должна быть как почетной, так и славной. Для чести обе стороны должны быть абсолютно равны. Для славы необходимо участие как можно большего числа воинов.
Каждый клан имеет строгую иерархию: во главе стоит лидер клана. Этот лидер может иметь ноль или более прямых подчиненных, расположенных от старшего к младшему. Каждый подчиненный, в свою очередь, может иметь ноль или более прямых подчиненных, также расположенных от старшего к младшему (и так далее). По традиции, каждый воин клана моложе своего начальника. Более того, каждый воин клана специализируется на одном из нескольких различных стилей боя.
Подклан, которым командует воин клана, состоит из самого воина и всех его прямых или косвенных подчиненных (т.е. подчиненных, подчиненных подчиненных и т.д.). Пара подкланов считается точно совпадающей, если выполняются два условия. Во-первых, лидеры каждого подклана должны иметь одинаковый стиль боя и одинаковое количество подчиненных. Во-вторых, если прямые подчиненные каждого лидера расположены по убыванию возраста, то подкланы, которыми командуют первые прямые подчиненные, должны точно совпадать, подкланы, которыми командуют вторые прямые подчиненные, должны точно совпадать, и так далее.
Каждый клан выберет своих участников для войны, состоящих из одного воина и его подклана. Выбранные два подклана должны точно совпадать и быть как можно больше. Сколько воинов сражается за каждый клан?
Входные данные
Входные данные начинаются с строки с одним целым числом T (1 ≤ T ≤ 50), обозначающим количество тестовых случаев. Каждый тестовый случай начинается с строки с двумя целыми числами M и N (1 ≤ M, N ≤ 10000), обозначающими размер двух кланов. Далее следуют M строк с заглавной буквой f_i и целым числом s_i (s_0 = -1, 0 ≤ s_i < i, нумерация с нуля), обозначающими стиль боя и начальника соответственно воина i первого клана. Воин 0 всегда является лидером клана (и имеет "начальника" -1, чтобы указать на это). Воины расположены от старшего к младшему. Далее следуют N строк с заглавной буквой f_j и целым числом s_j (те же ограничения), обозначающими стиль боя и начальника соответственно воина j второго клана.
Выходные данные
Для каждого тестового случая выведите строку с одним целым числом, равным максимальному количеству воинов, которых каждый клан может отправить на бой.