{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"Problema","value":{"format":"MD","content":"\u003cp\u003eComo muitos sabem, as capivaras respeitam uma hierarquia. Na UFV, há \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e capivaras (com códigos entre \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e) e cada animal pode ter até um líder (que nunca é ela mesma). \u003c/p\u003e\n\nUm animal A é considerado de uma hierarquia superior de B se, A é o líder imediato de B ou se A é o líder imediato de algum roedor C, que está em uma hierarquia superior de B.\n\nAssim como na computação, na hierarquia das capivaras não há ciclos (ou seja, não pode acontecer algo como: A estar acima de B, B acima de C e C acima de A)\n\nPara reduzir as frequentes brigas que acontecem nas lagoas, o reitor decidiu dividir as $k$ capivaras de modo que em cada lagoa não existam duas capivaras onde uma está em uma hierarquia superior da outra.\n\nQuantas lagoas precisaremos para abrigar todas as capivaras?"}},{"title":"Entrada","value":{"format":"MD","content":"\u003cp\u003eA primeira linha contém um inteiro \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ek\u003c/i\u003e ≤ 3000\u003c/span\u003e) — o número de capivaras.\u003c/p\u003e\n\n\u003cp\u003eAs próximas \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e linhas contém inteiros \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003ek\u003c/i\u003e\u003c/span\u003e ou \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u003d \u003c/span\u003e-1). Cada \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e indica a capivara em uma hierarquia imediatamente acima da \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-ésima capivara. Se \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e for -1, então a \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-ésima capivara não possui nenhuma outra acima dela.\u003c/p\u003e\n\n"}},{"title":"Saída","value":{"format":"MD","content":"\u003cp\u003eImprima o número de lagoas que precisaremos para abrigar todas capivaras seguindo a condição explicada acima.\u003c/p\u003e"}},{"title":"Exemplo","value":{"format":"MD","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\u003e6\n-1\n1\n4\n1\n-1\n-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Explicação","value":{"format":"MD","content":"\u003cp\u003eUma possível divisão:\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003eLagoa 1: capivara 1\u003c/li\u003e\n \u003cli\u003eLagoa 2: capivaras 2, 4 e 6\u003c/li\u003e\n \u003cli\u003eLagoa 3: capivaras 5 e 3\u003c/li\u003e\n\u003c/ul\u003e"}}]}