{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eA team of speleologists organizes a training in the Great Cave of\u0026nbsp;Byte Mountains.\r\nDuring the training each speleologist explores a route from Top Chamber\r\nto Bottom Chamber. The speleologists may move down only, i.e. the level of every\r\nconsecutive chamber on a route should be lower then the previous one. Moreover, each\r\nspeleologist has to start from Top Chamber through a different corridor and each of them must enter\r\nBottom Chamber using different corridor. The remaining corridors may be traversed by\r\nmore than one speleologist. How many speleologists can train\r\nsimultaneously?\u0026nbsp;\r\n\u003c/p\u003e\r\n\r\n\r\n\u003ch3\u003eTask\u003c/h3\u003e\r\n\r\n\u003cp\u003e\r\nWrite a program which:\r\n\u003c/p\u003e\u003cul\u003e \r\n \t\u003cli\u003ereads the cave description from the standard input,\r\n \t\u003c/li\u003e\u003cli\u003ecomputes the maximal number of speleologists that may train\r\n simultaneously,\r\n \t\u003c/li\u003e\u003cli\u003ewrites the result to the standard output.\r\n\u003c/li\u003e\u003c/ul\u003e \r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003e\r\nThe number of test cases t is in the first line of input, then t test cases follow separated by an empty line.\r\nIn the first line of each test case there is one integer \u003ci\u003en\u003c/i\u003e\r\n(\u003ci\u003e2\u0026lt;\u003dn\u0026lt;\u003d200\u003c/i\u003e), equal to the number of chambers in the cave. The chambers are\r\nnumbered with integers from \u003ci\u003e 1\u003c/i\u003e to \u003ci\u003e n\u003c/i\u003e in descending level order - the chamber of\r\ngrater number is at the higher level than the chamber of the lower one. (Top\r\nChamber has\r\nnumber \u003ci\u003e1,\u003c/i\u003e and Bottom Chamber has number \u003ci\u003en\u003c/i\u003e). In the following \u003ci\u003en-1\u003c/i\u003elines\r\n(i.e. lines \u003ci\u003e2,3,...,n\u003c/i\u003e) the descriptions of corridors are given. The (\u003ci\u003ei+1\u003c/i\u003e)-th\r\nline contains numbers of chambers connected by corridors with the \u003ci\u003ei\u003c/i\u003e-th chamber. (only\r\nchambers with numbers grater then \u003ci\u003ei\u003c/i\u003e are mentioned). The first number in a line, \u003ci\u003em\u003c/i\u003e, \u003ci\u003e\r\n0\u0026lt;\u003dm\u0026lt;\u003d\u003c/i\u003e(\u003ci\u003en-i+1\u003c/i\u003e), is a number of corridors exiting the chamber being described.\r\nThen the following\u003ci\u003e m\u003c/i\u003e integers are the numbers of\r\nthe chambers the corridors are leading to.\u0026nbsp;\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\r\n\u003cp\u003e\r\nYour program should write one integer for each test case.\r\nThis number should be equal to the maximal number of\r\nspeleologists able to train simultaneously,\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\r\n\u003cdiv\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\u003e1\r\n12\r\n4 3 4 2 5\r\n1 8\r\n2 9 7\r\n2 6 11\r\n1 8\r\n2 9 10\r\n2 10 11\r\n1 12\r\n2 10 12\r\n1 12\r\n1 12\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\r\n\u003cp\u003eThe sample input corresponds to the following cave:\u003cbr\u003e\r\n\u003cimg src\u003d\"CDN_BASE_URL/f0ec3f4dad2ae31541a65d422c3bf9bf?v\u003d1713994228\" height\u003d\"426\" width\u003d\"249\"\u003e \r\n\u003c/p\u003e\r\n\n\u003c/div\u003e"}}]}