Клінгонська війна
Війна спалахнула між двома клінгонськими кланами. Але війна між клінгонами - це не просто війна; вона повинна бути і почесною, і славною. Для честі обидві сторони повинні бути точно зрівняні. Для слави повинно бути якомога більше учасників.
Кожен клан дотримується суворої ієрархії: є один лідер усього клану. Цей лідер може мати нуль або більше прямих підлеглих, які впорядковані від найстаршого до наймолодшого. Кожен підлеглий, у свою чергу, може мати нуль або більше прямих підлеглих, також впорядкованих від найстаршого до наймолодшого (і так далі). За традицією, кожен воїн клану молодший за свого начальника. Крім того, кожен окремий воїн клану спеціалізується на одному з кількох різних стилів бою.
Підклан, яким командує воїн клану, складається з самого воїна та всіх прямих або непрямих підлеглих (тобто підлеглих, підлеглих підлеглих тощо). Пара підкланів вважається точно відповідною, якщо виконуються дві умови. По-перше, лідери кожного підклану повинні мати однаковий стиль бою та кількість підлеглих. По-друге, якщо прямі підлеглі кожного лідера впорядковані за зменшенням віку, то підклани, якими командують перші прямі підлеглі, повинні точно відповідати, підклани, якими командують другі прямі підлеглі, повинні точно відповідати, і так далі.
Кожен клан обере своїх учасників у війні, що складаються з одного воїна та його підклану. Обрані два підклани повинні точно відповідати і бути якомога більшими. Скільки воїнів боротиметься за кожен клан?
Вхідні дані
Вхід починається з рядка з одним цілим числом 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 другого клану.
Вихідні дані
Для кожного тестового випадку виведіть рядок з одним цілим числом, що дорівнює максимальній кількості воїнів, яких кожен клан може відправити на бій.