Ми перепрошуємо за будь-які незручності.
Навчання в Ягеллонському університеті в Кракові має свої переваги та недоліки. Переваги: Ягеллонський університет. Недоліки: Краків... А точніше, постійна необхідність ремонту трамвайних шляхів.
Спочатку мережа громадського транспорту складається з певної кількості трамвайних ліній. Потім одну з них призупиняють, потім іншу, і так далі... Як ви знаєте, у Кракові існує непорушне правило: завжди призупиняти лінію до того, як відновить роботу якась із раніше призупинених ліній. Наразі ще не всі лінії призупинені, і ви сидите в трамваї, дратуючись, що ваше пряме сполучення з університетом щойно зникло. Дивитеся у вікно і запитуєте себе: "Чи я дійсно найневезучіший пасажир у цьому місті? Чи є хтось, кому потрібно пересідати ще більше разів, щоб дістатися туди, куди він хоче?"
Точніше, ми говоримо, що зупинка B досяжна із зупинки A з c пересадками, якщо існують такі лінії l[0], ..., l[c], що l[0] обслуговує зупинку A, l[c] обслуговує зупинку B, і для кожного 0 ≤ i < c існує деяка зупинка, обслуговувана l[i] і l[i+1]. У кожний момент часу ви хочете знати найбільше значення c, при якому існує така пара зупинок (A, B), що в B можна дістатися з A з c пересадками, але при цьому B недосяжна з A з c' пересадками для будь-якого c' < c.
Зверніть увагу, що іноді взагалі неможливо проїхати між парою зупинок. Як випливає з наведеного вище визначення, ви вирішуєте не враховувати такі пари у своєму аналізі - якщо хтось захоче проїхати між цими зупинками, він скористається Uber.
Вхідні дані
Перший рядок містить кількість тестів z (1 ≤ z ≤ 35). Далі слідує опис тестів.
Перший рядок кожного тесту містить кількість зупинок n і кількість трамвайних шляхів k (2 ≤ n, k ≤ 750).
Зупинки пронумеровані від 1 до n, а лінії пронумеровані від 1 до k.
Потім слідують k рядків. i-й з цих рядків описує маршрут трамвайної лінії номер i. Кожен рядок починається з цілого числа r[i] (2 ≤ r[i] ≤ n), за яким слідують r[i] різних цілих чисел a[i,j] (1 ≤ a[i,j] ≤ n) - ідентифікатори зупинок, обслуговуваних i-им трамвайним маршрутом. Будь-яка трамвайна лінія йде в обох напрямках.
Наступний рядок містить одне ціле число s (1 ≤ s ≤ k − 1).
Потім слідують s рядків, що описують порядок зупинки трамвайних шляхів. Кожен з цих рядків містить єдине ціле число s[i] (1 ≤ s[i] ≤ k) - ідентифікатор зупиненої лінії трамвая. Будь-яка лінія може бути призупинена не більше одного разу.
Суми значень n і k у всіх тестах не перевищують 1000 кожне.
Вихідні дані
Для кожного тесту виведіть s + 1 рядків, кожен з яких містить одне ціле число. У i + 1-му рядку виведіть найбільшу кількість пересадок між лініями, які слід здійснити після i-ї події призупинення (перший рядок містить відповідь до будь-яких призупинень).
Примітка
Спочатку для проїзду, наприклад, від зупинки 4 до зупинки 5 (або навпаки) потрібна одна пересадка. Такий проїзд можливий за маршрутом 2, потім за маршрутом 1. Немає пар зупинок, що вимагають 2 або більше пересадок.
Після видалення лінії 1 для проїзду від зупинки 1 до зупинки 3 (або навпаки) потрібно дві пересадки.
Після видалення ліній 1 і 4 єдиними парами зупинок, які все ще можуть бути досягнуті одна з одної, є (1, 4) і (2, 3), і в обох випадках для проїзду між ними не потрібно жодних пересадок.
Після видалення ліній 1, 4 і 3 єдина пара зупинок, досяжна одна з одної, - це (1, 4). Для проїзду між цими зупинками не потрібно жодних пересадок.