{"trustable":true,"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":"","value":{"format":"HTML","content":"\u003cp\u003eAlthough Inzane successfully found his beloved bone, Zane, his owner, has yet to return. To search for Zane, he would need a lot of money, of which he sadly has none. To deal with the problem, he has decided to hack the banks.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/f4efb9730d24d9dd4d73a2f0e7f0fb79?v\u003d1715256282\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eThere are \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e banks, numbered from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e. There are also \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/span\u003e wires connecting the banks. All banks are initially \u003cspan class\u003d\"tex-font-style-it\"\u003eonline\u003c/span\u003e. Each bank also has its initial strength: bank \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e has initial strength \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eLet us define some keywords before we proceed. Bank \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e and bank \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e are \u003cspan class\u003d\"tex-font-style-it\"\u003eneighboring\u003c/span\u003e if and only if there exists a wire directly connecting them. Bank \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e and bank \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e are \u003cspan class\u003d\"tex-font-style-it\"\u003esemi-neighboring\u003c/span\u003e if and only if there exists an \u003cspan class\u003d\"tex-font-style-bf\"\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eonline\u003c/span\u003e\u003c/span\u003e bank \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e such that bank \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e and bank \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e are \u003cspan class\u003d\"tex-font-style-it\"\u003eneighboring\u003c/span\u003e and bank \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e and bank \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e are \u003cspan class\u003d\"tex-font-style-it\"\u003eneighboring\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eWhen a bank is hacked, it becomes \u003cspan class\u003d\"tex-font-style-it\"\u003eoffline\u003c/span\u003e (and no longer \u003cspan class\u003d\"tex-font-style-it\"\u003eonline\u003c/span\u003e), and other banks that are \u003cspan class\u003d\"tex-font-style-it\"\u003eneighboring\u003c/span\u003e or \u003cspan class\u003d\"tex-font-style-it\"\u003esemi-neighboring\u003c/span\u003e to it have their strengths increased by \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eTo start his plan, Inzane will choose a bank to hack first. Indeed, the strength of such bank must not exceed the strength of his computer. After this, he will repeatedly choose some bank to hack next until all the banks are hacked, but he can continue to hack bank \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e if and only if all these conditions are met:\u003c/p\u003e\u003col\u003e \u003cli\u003e Bank \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e is \u003cspan class\u003d\"tex-font-style-it\"\u003eonline\u003c/span\u003e. That is, bank \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e is not hacked yet. \u003c/li\u003e\u003cli\u003e Bank \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e is \u003cspan class\u003d\"tex-font-style-it\"\u003eneighboring\u003c/span\u003e to some \u003cspan class\u003d\"tex-font-style-it\"\u003eoffline\u003c/span\u003e bank. \u003c/li\u003e\u003cli\u003e The strength of bank \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e is less than or equal to the strength of Inzane\u0027s computer. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eDetermine the minimum strength of the computer Inzane needs to hack all the banks.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains one integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 3·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e)\u0026nbsp;— the total number of banks.\u003c/p\u003e\u003cp\u003eThe second line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e - 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e)\u0026nbsp;— the strengths of the banks.\u003c/p\u003e\u003cp\u003eEach of the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/span\u003e lines contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\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\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≠ \u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e)\u0026nbsp;— meaning that there is a wire directly connecting banks \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIt is guaranteed that the wires connect the banks in such a way that Inzane can somehow hack all the banks using a computer with appropriate strength.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint one integer\u0026nbsp;— the minimum strength of the computer Inzane needs to accomplish the goal.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","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\u003e5\n1 2 3 4 5\n1 2\n2 3\n3 4\n4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","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\u003e7\n38 -29 87 93 39 28 -55\n1 2\n2 5\n3 2\n2 4\n1 7\n7 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e93\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","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\u003e5\n1 2 7 6 7\n1 5\n5 3\n3 4\n2 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first sample, Inzane can hack all banks using a computer with strength \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e. Here is how:\u003c/p\u003e\u003cul\u003e \u003cli\u003e Initially, strengths of the banks are \u003cspan class\u003d\"tex-span\"\u003e[1, 2, 3, 4, 5]\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e He hacks bank \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e, then strengths of the banks become \u003cspan class\u003d\"tex-span\"\u003e[1, 2, 4, 5, - ]\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e He hacks bank \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e, then strengths of the banks become \u003cspan class\u003d\"tex-span\"\u003e[1, 3, 5, - , - ]\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e He hacks bank \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e, then strengths of the banks become \u003cspan class\u003d\"tex-span\"\u003e[2, 4, - , - , - ]\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e He hacks bank \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e, then strengths of the banks become \u003cspan class\u003d\"tex-span\"\u003e[3, - , - , - , - ]\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e He completes his goal by hacking bank \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eIn the second sample, Inzane can hack banks \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e7\u003c/span\u003e, and \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e, in this order. This way, he can hack all banks using a computer with strength \u003cspan class\u003d\"tex-span\"\u003e93\u003c/span\u003e.\u003c/p\u003e"}}]}