Hòa nhạc bàn phím (Keyboards in Concert)

Nguồn: Kattis

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ bàn phím điện tử. Mỗi bàn phím chỉ chơi được một tập nốt nhất định. Một bản nhạc gồm $m$ nốt theo thứ tự. Hãy chơi toàn bộ bản nhạc với số lần đổi bàn phím ít nhất.

Input

Dòng đầu chứa $n,m$. Mỗi trong $n$ dòng tiếp theo bắt đầu bằng $k_i$ rồi liệt kê các nốt bàn phím $i$ chơi được. Dòng cuối chứa $m$ nốt của bản nhạc.

Output

In số lần đổi bàn phím nhỏ nhất.

Subtask

• Subtask 1 — 20 điểm: dữ liệu nhỏ, phù hợp để kiểm tra cách trực tiếp hoặc DP cơ bản.
• Subtask 2 — 30 điểm: dữ liệu trung bình, yêu cầu lưu trạng thái hợp lý.
• Subtask 3 — 50 điểm: toàn bộ giới hạn của gói Phước Hưng OJ.

Ví dụ

Input

3 9
2 1 2
2 2 3
1 3
1 2 1 2 3 3 2 3 1

Output

2

Giải thích

Kết quả được tính đúng theo quy tắc của đề. Đây là một trường hợp nhỏ để đối chiếu định dạng vào/ra trước khi nộp bài.