Trên các máy tính Unix, dữ liệu được lưu trữ trong các thư mục (directories). Có một thư mục gốc (root directory), và thư mục này có thể chứa nhiều thư mục con bên trong, mỗi thư mục có tên khác nhau. Các thư mục này lại có thể chứa thêm nhiều thư mục khác nữa, và cứ tiếp tục như vậy.

Một thư mục được xác định duy nhất bởi tên của nó và thư mục cha (thư mục trực tiếp chứa nó). Điều này thường được mã hóa trong một đường dẫn (path), bao gồm nhiều phần, mỗi phần được bắt đầu bằng một dấu gạch chéo ('/'). Phần cuối cùng là tên của thư mục, và tất cả các phần còn lại tạo nên đường dẫn của thư mục cha. Ví dụ, xét đường dẫn:

/home/gcj/finals

Đường dẫn này tham chiếu đến thư mục có tên "finals" nằm trong thư mục được mô tả bởi "/home/gcj", thư mục này lại tham chiếu đến thư mục có tên "gcj" trong thư mục được mô tả bởi đường dẫn "/home". Trong đường dẫn "/home", chỉ có một phần, nghĩa là nó tham chiếu đến thư mục có tên "home" trong thư mục gốc.

Để tạo một thư mục, bạn có thể sử dụng lệnh mkdir. Bạn chỉ định một đường dẫn, và sau đó mkdir sẽ tạo thư mục được mô tả bởi đường dẫn đó, nhưng chỉ khi thư mục cha của nó đã tồn tại. Ví dụ, nếu bạn muốn tạo các thư mục "/home/gcj/finals" và "/home/gcj/quals" từ đầu, bạn sẽ cần bốn lệnh:

mkdir /home
mkdir /home/gcj
mkdir /home/gcj/finals
mkdir /home/gcj/quals

Cho tập hợp đầy đủ các thư mục đã tồn tại trên máy tính của bạn và một tập hợp các thư mục mới mà bạn muốn tạo (nếu chúng chưa tồn tại), bạn cần sử dụng bao nhiêu lệnh mkdir?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test theo sau. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên \(N\) và \(M\), cách nhau bởi một khoảng trắng.

\(N\) dòng tiếp theo, mỗi dòng cho biết đường dẫn của một thư mục đã tồn tại trên máy tính của bạn. Danh sách này sẽ bao gồm mọi thư mục đã có trên máy tính ngoại trừ thư mục gốc. (Thư mục gốc có trên mọi máy tính, vì vậy không cần liệt kê rõ ràng.)

\(M\) dòng tiếp theo, mỗi dòng cho biết đường dẫn của một thư mục mà bạn muốn tạo.

Mỗi đường dẫn trong dữ liệu vào được định dạng như mô tả trong đề bài ở trên. Cụ thể, một đường dẫn bao gồm một hoặc nhiều chuỗi ký tự chữ-số thường (tức là các chuỗi chỉ chứa các ký hiệu 'a'-'z' và '0'-'9'), mỗi chuỗi được bắt đầu bởi một dấu gạch chéo duy nhất. Các chuỗi chữ-số này không bao giờ để trống.

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lượng lệnh mkdir bạn cần sử dụng.

Ràng buộc

• \(1 \le T \le 100\).
• Không có đường dẫn nào dài quá 100 ký tự.
• Không có đường dẫn nào xuất hiện hai lần trong danh sách các thư mục đã có, hoặc trong danh sách các thư mục muốn tạo. Tuy nhiên, một đường dẫn có thể xuất hiện một lần trong cả hai danh sách (Xem ví dụ 2 bên dưới).
• Nếu một thư mục được liệt kê là đã có trên máy tính, thì thư mục cha của nó cũng sẽ được liệt kê, trừ khi cha là thư mục gốc.
• Tệp dữ liệu vào sẽ không dài quá 100,000 bytes tổng cộng.

Phân nhóm

• Small dataset (Test set 1): \(0 \le N \le 10, 1 \le M \le 10\).
• Large dataset (Test set 2): \(0 \le N \le 100, 1 \le M \le 100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
0 2
/home/gcj/finals
/home/gcj/quals
2 1
/chicken
/chicken/egg
/chicken
1 3
/a
/a/b
/a/c
/b/b

Case #1: 4
Case #2: 0
Case #3: 4

Nguồn

Google Code Jam 2010, Vòng 1B, bài File Fix-it.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.