{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:40.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/97de6c3d979b594c63ed47a34f264cc0?v\u003d1719560373\" alt\u003d\"/problems/importspaghetti/file/statement/en/img-0001.png\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003eYou just graduated from programming school and nailed a\n Python programming job. The first day at work you realize that\n you have inherited a mess. The \u003cem\u003espaghetti\u003c/em\u003e design\n pattern was chosen by the previous maintainer, who recently\n fled the country. You try to make sense of the code, but\n immediately discover that different files depend cyclically on\n each other. Testing the code, in fact running the code, has not\n yet been attempted.\n\n \u003cp\u003eAs you sit down and think, you decide that the first thing\n to do is to eliminate the cycles in the dependency graph. So\n you start by finding a shortest dependency cycle.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe first line of input contains a number \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le n \\le 500$\u003c/span\u003e, the number of files. Then follows one\n line with\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e\n distinct names of files. Each name is a string with at least\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e and at most\n \u003cspan class\u003d\"tex2jax_process\"\u003e$8$\u003c/span\u003e lower case letters\n ‘\u003ctt class\u003d\"ttfamily\"\u003ea\u003c/tt\u003e’ to ‘\u003ctt class\u003d\"ttfamily\"\u003ez\u003c/tt\u003e’.\n Then follow\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e\n sections, one section per file name, in the order they were\n given on the second line. Each section starts with one line\n containing the name of the file and an\n integer\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e, followed\n by\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e lines, each\n starting with “\u003ctt class\u003d\"ttfamily\"\u003eimport\u003c/tt\u003e”.\u003c/p\u003e\n\n \u003cp\u003eEach “\u003ctt class\u003d\"ttfamily\"\u003eimport\u003c/tt\u003e” line is a\n comma-space separated line of dependencies. No file imports the\n same file more than once, and every file imported is listed in\n the second line of the input. Comma-space separated means that\n every line will start with “\u003ctt class\u003d\"ttfamily\"\u003eimport\u003c/tt\u003e”,\n then have a list of file names separated by \u003ctt class\u003d\"ttfamily\"\u003e“, ”\u003c/tt\u003e (see sample inputs for examples). Each\n import statement is followed by at least one file name.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eIf the code base has no cyclic dependencies, output\n “\u003ctt class\u003d\"ttfamily\"\u003eSHIP IT\u003c/tt\u003e”. Otherwise, output a line\n containing the names of files in a shortest cycle, in the order\n of the cycle (i.e., the \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eth file listed must import the\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(i+1)$\u003c/span\u003est file listed, and\n the last file listed must import the first). If there are many\n shortest cycles, any one will be accepted.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e4\na b c d\na 1\nimport d, b, c\nb 2\nimport d\nimport c\nc 1\nimport c\nd 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003ec\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e5\nclassa classb myfilec execd libe\nclassa 2\nimport classb\nimport myfilec, libe\nclassb 1\nimport execd\nmyfilec 1\nimport libe\nexecd 1\nimport libe\nlibe 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eSHIP IT\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 3\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e5\nclassa classb myfilec execd libe\nclassa 2\nimport classb\nimport myfilec, libe\nclassb 1\nimport execd\nmyfilec 1\nimport libe\nexecd 1\nimport libe, classa\nlibe 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eclassa classb execd\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}