Müharibə iki Klingon klanı arasında baş verir. Lakin Klingonlar üçün müharibə yalnız adi bir döyüş deyil; həm şərəfli, həm də şanlı olmalıdır. Şərəf üçün, iki tərəf tam uyğun olmalıdır. Şan üçün isə mümkün qədər çox iştirakçı olmalıdır.
Hər klan ciddi bir iyerarxiyaya malikdir: bütün klanın bir lideri var. Bu liderin sıfır və ya daha çox birbaşa tabeçiliyi ola bilər və onlar ən yaşlıdan ən gəncə doğru sıralanır. Hər bir tabe öz növbəsində sıfır və ya daha çox birbaşa tabeçiliyə sahib ola bilər, onlar da ən yaşlıdan ən gəncə doğru sıralanır (və s.). Ənənəyə görə, hər bir klan döyüşçüsü öz üstünündən daha gəncdir. Bundan əlavə, hər bir klan döyüşçüsü bir neçə fərqli döyüş üslubundan birində ixtisaslaşır.
Klan döyüşçüsü tərəfindən idarə olunan alt klan, döyüşçünün özü və bütün birbaşa və dolayı hesabatlardan (yəni, tabeçiliyi, tabeçiliyinin tabeçiliyi və s.) ibarətdir. İki alt klan tam uyğun hesab olunur, əgər iki şərt yerinə yetirilərsə. Birincisi, hər bir alt klanın liderləri eyni döyüş üslubuna və tabeçiliyin sayına malik olmalıdır. İkincisi, əgər hər bir liderin birbaşa tabeçiliyi azalan yaş sırasına görə sıralanırsa, onda birinci birbaşa tabeçiliyin idarə etdiyi alt klanlar tam uyğun olmalıdır, ikinci birbaşa tabeçiliyin idarə etdiyi alt klanlar tam uyğun olmalıdır və s.
Hər klan müharibədə iştirakçılarını seçəcək, bir döyüşçü və onun alt klanından ibarət olacaq. Seçilmiş iki alt klan tam uyğun olmalıdır və mümkün qədər böyük olmalıdır. Hər klan üçün neçə döyüşçü mübarizə aparır?
Giriş bir tam ədəd T (1 ≤ T ≤ 50) ilə başlayır, bu da test hallarının sayını göstərir. Hər test halı iki tam ədəd M və N (1 ≤ M, N ≤ 10000) ilə başlayır, bu da iki klanın ölçüsünü göstərir. Sonra M sətir gəlir, burada böyük hərf f_i və tam ədəd s_i (s_0 = -1, 0 ≤ s_i < i, sıfır indeksli) birinci klanın döyüşçüsü i-nin döyüş üslubunu və üstününü göstərir. Döyüşçü 0 həmişə klan lideridir (və bunu göstərmək üçün "üstün" -1 olur). Döyüşçülər ən yaşlıdan ən gəncə doğru sıralanır. Sonra N sətir gəlir, burada böyük hərf f_j və tam ədəd s_j (eyni məhdudiyyətlər) ikinci klanın döyüşçüsü j-nin döyüş üslubunu və üstününü göstərir.
Hər test halı üçün, hər klanın mübarizə aparmaq üçün göndərə biləcəyi maksimum döyüşçü sayına bərabər olan bir tam ədəd ilə bir sətir çap edin.
Nümunə 1