Việc học tập tại Đại học Jagiellonian ở Krakow có những ưu và nhược điểm. Ưu điểm: Đại học Jagiellonian. Nhược điểm: Krakow... Hay nói chính xác hơn, là sự cần thiết liên tục phải đối mặt với việc tái thiết đường ray xe điện.

Ban đầu, mạng lưới giao thông công cộng bao gồm một số tuyến xe điện. Sau đó, một tuyến bị tạm dừng, rồi đến tuyến khác, và cứ thế... Như bạn có thể biết, quy tắc bất di bất dịch ở Krakow là luôn tạm dừng một tuyến trước khi bất kỳ tuyến nào đã bị tạm dừng trước đó được hoạt động trở lại. Hiện tại, không phải tất cả các tuyến đều đã bị tạm dừng, và bạn đang ngồi trên một chiếc xe điện, khó chịu vì kết nối trực tiếp đến trường đại học của bạn vừa biến mất. Bạn nhìn ra ngoài cửa sổ và tự hỏi: "Mình có thực sự là hành khách xui xẻo nhất trong thành phố này không? Hay có ai đó ở ngoài kia cần phải đổi tuyến nhiều lần hơn nữa để đến nơi họ muốn?"

Cụ thể hơn, chúng ta nói rằng điểm dừng $B$ có thể đến được từ điểm dừng $A$ với $c$ lần đổi tuyến nếu tồn tại các tuyến $l_0, \dots, l_c$ sao cho $l_0$ phục vụ điểm dừng $A$, $l_c$ phục vụ điểm dừng $B$, và với mỗi $0 \le i < c$ luôn tồn tại một điểm dừng được phục vụ bởi cả $l_i$ và $l_{i+1}$. Tại mỗi thời điểm, bạn muốn biết giá trị lớn nhất của $c$ sao cho tồn tại một cặp điểm dừng $(A, B)$ mà $B$ có thể đến được từ $A$ với $c$ lần đổi tuyến và $B$ không thể đến được từ $A$ với $c'$ lần đổi tuyến cho bất kỳ $c' < c$.

Lưu ý rằng đôi khi việc di chuyển giữa một cặp điểm dừng là không thể. Theo định nghĩa trên, bạn quyết định không đưa những cặp đó vào phân tích của mình – bạn kết luận rằng nếu ai đó muốn di chuyển giữa các điểm dừng đó, họ sẽ gọi Uber.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số lượng bộ test $z$ ($1 \le z \le 35$). Tiếp theo là mô tả của các bộ test.

Dòng đầu tiên của mỗi bộ test chứa số lượng điểm dừng $n$ và số lượng tuyến xe điện $k$ ($2 \le n, k \le 750$). Các điểm dừng được đánh số từ $1$ đến $n$ và các tuyến được đánh số từ $1$ đến $k$.

Tiếp theo là $k$ dòng. Dòng thứ $i$ trong số đó mô tả lộ trình của tuyến xe điện số $i$. Mỗi dòng bắt đầu bằng một số nguyên $r_i$ ($2 \le r_i \le n$) theo sau là $r_i$ số nguyên phân biệt $a_{i,j}$ ($1 \le a_{i,j} \le n$) – các định danh của các điểm dừng được phục vụ bởi tuyến xe điện thứ $i$. Mọi tuyến xe điện đều chạy theo cả hai hướng.

Dòng tiếp theo chứa một số nguyên duy nhất $s$ ($1 \le s \le k - 1$).

Tiếp theo là $s$ dòng, mô tả thứ tự các tuyến xe điện bị tạm dừng. Mỗi dòng trong số đó chứa một số nguyên $s_i$ ($1 \le s_i \le k$) – định danh của tuyến xe điện bị tạm dừng. Mỗi tuyến có thể bị tạm dừng tối đa một lần.

Tổng các giá trị của $n$ và $k$ trong tất cả các bộ test không vượt quá $1000$ mỗi loại.

Dữ liệu ra

Với mỗi bộ test, hãy in ra $s + 1$ dòng, mỗi dòng chứa một số nguyên duy nhất. Dòng thứ $i + 1$ biểu thị số lần đổi tuyến lớn nhất cần thiết sau sự kiện tạm dừng thứ $i$ (dòng đầu tiên biểu thị câu trả lời trước khi có bất kỳ sự tạm dừng nào).

Ví dụ

Dữ liệu vào 1

1
5 4
3 1 3 5
2 1 4
2 2 3
2 2 4
3
1
4
3

Dữ liệu ra 1

1
2
0
0

Ghi chú

Ban đầu, cần một lần đổi tuyến để di chuyển, ví dụ, từ điểm dừng 4 đến điểm dừng 5 (hoặc ngược lại). Việc di chuyển như vậy có thể thực hiện bằng cách đi tuyến 2, sau đó là tuyến 1. Không có cặp điểm dừng nào yêu cầu từ 2 lần đổi tuyến trở lên.

Sau khi tuyến 1 bị loại bỏ, cần hai lần đổi tuyến để di chuyển từ điểm dừng 1 đến điểm dừng 3 (hoặc ngược lại).

Khi các tuyến 1 và 4 bị loại bỏ, các cặp điểm dừng duy nhất vẫn có thể đến được với nhau là (1, 4) và (2, 3), và trong cả hai trường hợp đều không cần đổi tuyến để di chuyển giữa chúng.

Khi các tuyến 1, 4 và 3 bị loại bỏ, cặp điểm dừng duy nhất vẫn có thể đến được với nhau là (1, 4). Không cần đổi tuyến để di chuyển giữa các điểm dừng này.