{"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\u003eUma equipe de espeleólogos organiza um treinamento na Grande Caverna das Montanhas Byte. Durante o treinamento, cada espeleólogo explora uma rota da Câmara Superior para a Câmara Inferior. Os espeleólogos só podem se mover para baixo, ou seja, o nível de cada câmara consecutiva em uma rota deve ser menor do que a anterior. Além disso, cada espeleólogo deve começar na Câmara Superior por um corredor diferente e cada um deles deve entrar na Câmara Inferior usando um corredor diferente. Os corredores restantes podem ser percorridos por mais de um espeleólogo. Quantos espeleólogos podem treinar simultaneamente?\u003c/p\u003e\n\n\n\u003ch3\u003eTarefa\u003c/h3\u003e\n\n\u003cp\u003e\nEscreva um programa que:\n\u003c/p\u003e\u003cul\u003e \n \t\u003cli\u003eleia a descrição da caverna da entrada padrão,\n \t\u003c/li\u003e\u003cli\u003ecalcule o número máximo de espeleólogos que podem treinar simultaneamente,\n \t\u003c/li\u003e\u003cli\u003eescreva o resultado na saída padrão.\n\u003c/li\u003e\u003c/ul\u003e \n\n\u003ch3\u003eEntrada\u003c/h3\u003e\n\u003cp\u003e\nO número de casos de teste t está na primeira linha da entrada, seguido por t casos de teste separados por uma linha em branco.\nNa primeira linha de cada caso de teste há um número inteiro \u003ci\u003en\u003c/i\u003e (\u003ci\u003e2\u0026lt;\u003dn\u0026lt;\u003d200\u003c/i\u003e), igual ao número de câmaras na caverna. As câmaras são numeradas com inteiros de \u003ci\u003e 1\u003c/i\u003e a \u003ci\u003e n\u003c/i\u003e em ordem decrescente de nível - a câmara de número maior está em um nível mais alto do que a câmara de número menor. (A Câmara Superior tem o número \u003ci\u003e1,\u003c/i\u003e e a Câmara Inferior tem o número \u003ci\u003en\u003c/i\u003e). Nas \u003ci\u003en-1\u003c/i\u003e linhas seguintes (ou seja, linhas \u003ci\u003e2,3,...,n\u003c/i\u003e) são dadas as descrições dos corredores. A linha (\u003ci\u003ei+1\u003c/i\u003e-ésima) contém os números das câmaras conectadas por corredores com a câmara \u003ci\u003ei\u003c/i\u003e-ésima. (apenas câmaras com números maiores do que \u003ci\u003ei\u003c/i\u003e são mencionadas). O primeiro número em uma linha, \u003ci\u003em\u003c/i\u003e, \u003ci\u003e\n0\u0026lt;\u003dm\u0026lt;\u003d\u003c/i\u003e(\u003ci\u003en-i+1\u003c/i\u003e), é o número de corredores saindo da câmara sendo descrita. Em seguida, os \u003ci\u003e m\u003c/i\u003e inteiros seguintes são os números das câmaras para as quais os corredores estão levando.\n\u003c/p\u003e\n\n\u003ch3\u003eSaída\u003c/h3\u003e\n\n\u003cp\u003e\nSeu programa deve escrever um número inteiro para cada caso de teste. Este número deve ser igual ao número máximo de espeleólogos capazes de treinar simultaneamente.\n\u003c/p\u003e\n\n\u003ch3\u003eExemplo\u003c/h3\u003e\n\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\n\n\u003cp\u003eA entrada de exemplo corresponde à seguinte caverna:\u003cbr\u003e\n\u003cimg src\u003d\"CDN_BASE_URL/f0ec3f4dad2ae31541a65d422c3bf9bf?v\u003d1703496886\" height\u003d\"426\" width\u003d\"249\"\u003e \n\u003c/p\u003e\n\n\u003c/div\u003e"}}]}