P9831 [ICPC 2020 Shanghai R] Gitignore

Your git project (you don't need to be familiar with git to solve this problem) has some files that should be ignored from synchronizing. You need to calculate the minimum number of lines needed for gitignore. Formally, your project is a folder. A folder can have files and sub folders. There are no empty folders (i.e. folders without any files or sub folders inside). Initially, the git software will synchronize all the files in your project. However, you can specify some files and folders in the settings (which is called gitignore) to exclude them from synchronizing. For each line in gitignore, you can specify either a file or all the files in a folder. You can $\textbf{not}$ ignore the whole project folder (i.e. an empty line in gitignore). You are given paths for all the files in the project and whether they should be ignored or shouldn't. Your task is to calculate the minimum number of lines for gitignore.

无

无

In the first sample test case, the corresponding gitignore file contains $2$ lines: a folder line ``data/`` and a file name ``model``. In the second sample test case, the corresponding gitignore file contains $3$ file lines: ``data/train``, ``data/test`` and ``model``.