{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e The software installation is becoming more and more complex. An automatic tool is often useful to manage this process. An IT company is developing a system management utility to install a set of software packages automatically with the dependencies. They found that reboot is often required to take effect after installing some software. A software package cannot be installed until all software packages it depends on are installed and take effect. \u003cbr\u003e\u003cbr\u003e In the beginning, they implemented a simple installation algorithm, but the system would reboot many times during the installation process. This will have a great impact on the user experience. After some study, they think that this process can be further optimized by means of installing as much packages as possible before each reboot.\u003cbr\u003e\u003cbr\u003e Now, could you please design and implement this algorithm for them to minimize the number of restart during the entire installation process?\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":" The first line is an integer n (1 \u0026lt;\u003d n \u0026lt;\u003d 100), which is the number of test cases. The second line is blank. The input of two test cases is separated by a blank line.\u003cbr\u003e\u003cbr\u003e Each test case contains m (1 \u0026lt;\u003d n \u0026lt;\u003d 1000) continuous lines and each line is no longer than 1024 characters. Each line starts with a package name and a comma (:). If an asterisk (*) exists between the package name and the comma, the reboot operation is required for this package. The remaining line is the other package names it depends on, separated by whitespace. Empty means that there is no dependency for this software. For example, “a: b” means package b is required to be installed before package a. Package names consist of letters, digits and underscores, excluding other special symbols.\u003cbr\u003e\u003cbr\u003e Assume all packages here need to be installed and all referenced packages will be listed in an individual line to define the reboot property. It should be noted that cyclic dependencies are not allowed in this problem."}},{"title":"Output","value":{"format":"HTML","content":" For each test case, you should output a line starting with “Case #: \" (# is the No. of the test case, starting from 1) and containing the reboot count for this test case. (Refer to the sample format)"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n\r\nglibc:\r\ngcc*: glibc\r\n\r\nuefi*:\r\ngcc*:\r\nraid_util*: uefi\r\ngpu_driver*: uefi\r\nopencl_sdk: gpu_drivergcc\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 1\r\nCase 2: 2 \u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}