{"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 \u003cp\u003eAs we all know, Brexit negotiations are on their way—but we\n still do not know whether they will actually finish in\n time.\u003c/p\u003e\n \u003cp\u003eThe negotiations will take place topic-by-topic. To organise\n the negotiations in the most effective way, the topics will all\n be discussed and finalised in separate meetings, one meeting at\n a time.\u003c/p\u003e\n \u003cp\u003eThis system exists partly because there are (non-cyclic)\n dependencies between some topics: for example, one cannot have\n a meaningful talk about tariffs before deciding upon the\n customs union. The EU can decide on any order in which to\n negotiate the topics, as long as the mentioned dependencies are\n respected and all topics are covered.\u003c/p\u003e\n \u003cp\u003eEach of the topics will be discussed at length using every\n available piece of data, including key results from past\n meetings. At the start of each meeting, the delegates will take\n one extra minute for each of the meetings that has already\n happened by that point, even unrelated ones, to recap the\n discussions and understand how their conclusions were reached.\n See Figure\u0026nbsp;1 for an example.\u003c/p\u003e\n \u003cp\u003eNobody likes long meetings. The EU would like you to help\n order the meetings in a way such that the longest meeting takes\n as little time as possible.\u003c/p\u003e\n \u003cdiv id\u003d\"fig:brexit\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/957989ce768a921a3a8a02412faca66a?v\u003d1714351384\" alt\u003d\"\\includegraphics[width\u003d0.9\\textwidth ]{sample1}\" style\u003d\"width:90.00%\"\u003e\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: Illustration of how time is spent in\n each meeting in a solution to Sample Input 2.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe input consists of:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eOne line containing an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq n \\leq 4 \\cdot 10^5$\u003c/span\u003e), the\n number of topics to be discussed. The topics are numbered\n from \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines,\n describing the negotiation topics.\u003c/p\u003e\n \u003cp\u003eThe \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eth such line\n starts with two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$e_\n i$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$d_ i$\u003c/span\u003e\n (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq e_ i \\leq\n 10^6$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq d_ i\n \u0026lt; n$\u003c/span\u003e), the number of minutes needed to reach a\n conclusion on topic \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e and the number of other\n specific topics that must be dealt with before topic\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e can be\n discussed.\u003c/p\u003e\n \u003cp\u003eThe remainder of the line has \u003cspan class\u003d\"tex2jax_process\"\u003e$d_ i$\u003c/span\u003e distinct integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$b_{i,1}, \\ldots ,\n b_{i,d_{i}}$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le\n b_{i,j} \\le n$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$b_{i,j} \\ne i$\u003c/span\u003e for each\n \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e), the list of\n topics that need to be completed before topic \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eIt is guaranteed that there are no cycles in the topic\n dependencies, and that the sum of \u003cspan class\u003d\"tex2jax_process\"\u003e$d_ i$\u003c/span\u003e over all topics is at most\n \u003cspan class\u003d\"tex2jax_process\"\u003e$4 \\cdot 10^5$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eOutput the minimum possible length of the longest of all\n meetings, if meetings are arranged optimally according to the\n above rules.\u003c/p\u003e\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\u003e3\n10 0\n10 0\n10 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e12\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\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\u003e6\n2 2 4 3\n4 1 5\n1 2 2 4\n3 1 5\n2 0\n4 1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}