Ми перепрошуємо за будь-які незручності.#11109

Ми перепрошуємо за будь-які незручності.

5 секунд

128 мегабайтів

Складна

Навчання в Ягеллонському університеті в Кракові має свої переваги та недоліки. Переваги: Ягеллонський університет. Недоліки: Краків... А точніше, постійна необхідність ремонту трамвайних шляхів.

Спочатку мережа громадського транспорту складається з певної кількості трамвайних ліній. Потім одну з них призупиняють, потім іншу, і так далі... Як ви знаєте, у Кракові існує непорушне правило: завжди призупиняти лінію до того, як відновить роботу якась із раніше призупинених ліній. Наразі ще не всі лінії призупинені, і ви сидите в трамваї, дратуючись, що ваше пряме сполучення з університетом щойно зникло. Дивитеся у вікно і запитуєте себе: "Чи я дійсно найневезучіший пасажир у цьому місті? Чи є хтось, кому потрібно пересідати ще більше разів, щоб дістатися туди, куди він хоче?"

Точніше, ми говоримо, що зупинка $B$ досяжна із зупинки $A$ з $c$ пересадками, якщо існують такі лінії $l_{0}, \dots, l_{c}$ l_0, \ldots, l_c, що $l_{0}$ l_0 обслуговує зупинку $A$ , $l_{c}$ l_c обслуговує зупинку $B$ , і для кожного $0 \leq i < c$ 0 \le i < c існує деяка зупинка, обслуговувана $l_{i}$ l_i і $l_{i + 1}$ l_{i+1}. У кожний момент часу ви хочете знати найбільше значення $c$ , при якому існує така пара зупинок ( $A$ , $B$ ), що в $B$ можна дістатися з $A$ з $c$ пересадками, але при цьому $B$ недосяжна з $A$ з $c^{'}$ c' пересадками для будь-якого $c^{'} < c$ c' < c.

Зверніть увагу, що іноді взагалі неможливо проїхати між парою зупинок. Як випливає з наведеного вище визначення, ви вирішуєте не враховувати такі пари у своєму аналізі - якщо хтось захоче проїхати між цими зупинками, він скористається Uber.

Вхідні дані

Перший рядок містить кількість тестів $z$ ( $1 \leq z \leq 35$ 1 \le z \le 35). Далі слідує опис тестів.

Перший рядок кожного тесту містить кількість зупинок $n$ і кількість трамвайних шляхів $k$ ( $2 \leq n, k \leq 750$ 2 \le n, k \le 750).

Зупинки пронумеровані від $1$ до $n$ , а лінії пронумеровані від $1$ до $k$ .

Потім слідують $k$ рядків. $i$ -й з цих рядків описує маршрут трамвайної лінії номер $i$ . Кожен рядок починається з цілого числа $r_{i}$ r_i ( $2 \leq r_{i} \leq n$ 2 \le r_i \le n), за яким слідують $r_{i}$ r_i різних цілих чисел $a_{i, j}$ a_{i,j} ( $1 \leq a_{i, j} \leq n$ 1 \le a_{i,j} \le n) - ідентифікатори зупинок, обслуговуваних $i$ -им трамвайним маршрутом. Будь-яка трамвайна лінія йде в обох напрямках.

Наступний рядок містить одне ціле число $s$ ( $1 \leq s \leq k - 1$ 1 \le s \le k - 1).

Потім слідують $s$ рядків, що описують порядок зупинки трамвайних шляхів. Кожен з цих рядків містить єдине ціле число $s_{i}$ s_i ( $1 \leq s_{i} \leq k$ 1 \le s_i \le k) - ідентифікатор зупиненої лінії трамвая. Будь-яка лінія може бути призупинена не більше одного разу.

Суми значень $n$ і $k$ у всіх тестах не перевищують $1000$ кожне.

Вихідні дані

Для кожного тесту виведіть $s + 1$ s + 1 рядків, кожен з яких містить одне ціле число. У $i + 1$ i + 1-му рядку виведіть найбільшу кількість пересадок між лініями, які слід здійснити після $i$ -ї події призупинення (перший рядок містить відповідь до будь-яких призупинень).

Приклади

Приклад 1

Примітка

Спочатку для проїзду, наприклад, від зупинки $4$ до зупинки $5$ (або навпаки) потрібна одна пересадка. Такий проїзд можливий за маршрутом $2$ , потім за маршрутом $1$ . Немає пар зупинок, що вимагають $2$ або більше пересадок.

Після видалення лінії $1$ для проїзду від зупинки $1$ до зупинки $3$ (або навпаки) потрібно дві пересадки.

Після видалення ліній $1$ і $4$ єдиними парами зупинок, які все ще можуть бути досягнуті одна з одної, є ( $1$ , $4$ ) і ( $2$ , $3$ ), і в обох випадках для проїзду між ними не потрібно жодних пересадок.

Після видалення ліній $1$ , $4$ і $3$ єдина пара зупинок, досяжна одна з одної, - це ( $1$ , $4$ ). Для проїзду між цими зупинками не потрібно жодних пересадок.