{"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\u003eAndi has a network $$$G$$$ with $$$N$$$ machines and $$$M$$$ links; each link connects exactly two different machines. Due to some circumstances, Andi has to make his network \"complete\", i.e. every machine is directly linked to every other machine. This means Andy has to add a new link between any pair of machines which are not already directly linked.\u003c/p\u003e\u003cp\u003eIn order to accomplish his goal, Andi outsources the work to a company, Go. Go accepts any work order on a network $$$G$$$ with a requested integer $$$k$$$, i.e. $$$go(G,k)$$$. The way Go works: First, it creates a list $$$L$$$ containing \u003cspan class\u003d\"tex-font-style-bf\"\u003eall\u003c/span\u003e pair of machines which are \u003cspan class\u003d\"tex-font-style-bf\"\u003enot\u003c/span\u003e yet directly linked. Then, Go evaluates each pair of machines $$$(a,b)$$$ from $$$L$$$ and create a new link between them if $$$\\delta_a + \\delta_b \\ge k$$$. Note that $$$\\delta_a$$$ is the degree of machine $$$a$$$, i.e. the number of links $$$a$$$ has at the time of evaluation. Similarly, $$$\\delta_b$$$ is for machine $$$b$$$.\u003c/p\u003e\u003cp\u003eThe problem with Go\u0027s procedure is it evaluates each pair of machines in the order appeared in $$$L$$$. For example, let $$$G$$$ be a network with $$$N \u003d 4$$$ machines (machine $$$1$$$, $$$2$$$, $$$3$$$, and $$$4$$$) and $$$M \u003d 3$$$ links; the links are $$$\\{(1, 2), (2, 3), (3, 4)\\}$$$. The degree of each machine before a work order is requested is: $$$\\delta_1 \u003d 1$$$, $$$\\delta_2 \u003d 2$$$, $$$\\delta_3 \u003d 2$$$, $$$\\delta_4 \u003d 1$$$, or simply can be written as $$$[1, 2, 2, 1]$$$. Let say a work order with $$$k \u003d 3$$$ is requested ($$$go(G,3)$$$).\u003c/p\u003e\u003cp\u003eConsider these two lists: \u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$L_1 \u003d ((1,4),(1,3),(2,4))$$$. \u003cul\u003e \u003cli\u003e Evaluate $$$(1,4)$$$ and don\u0027t create a new link since $$$\\delta_1 + \\delta_4 \u003d 1 + 1 \u003d 2$$$. The degree is still $$$[1, 2, 2, 1]$$$. \u003c/li\u003e\u003cli\u003e Evaluate $$$(1,3)$$$ and create a new link since $$$\\delta_1 + \\delta_3 \u003d 1 + 2 \u003d 3$$$. The degree becomes $$$[2, 2, 3, 1]$$$. \u003c/li\u003e\u003cli\u003e Evaluate $$$(2,4)$$$ and create a new link since $$$\\delta_2 + \\delta_4 \u003d 2 + 1 \u003d 3$$$. The degree becomes $$$[2, 3, 3, 2]$$$. \u003c/li\u003e\u003c/ul\u003e The final result is a network with $$$5$$$ links, which is not complete as it misses the $$$(1,4)$$$ link. \u003c/li\u003e\u003cli\u003e $$$L_2 \u003d ((2,4),(1,3),(1,4))$$$. \u003cul\u003e \u003cli\u003e Evaluate $$$(2,4)$$$ and create a new link since $$$\\delta_2 + \\delta_4 \u003d 2 + 1 \u003d 3$$$. The degree becomes $$$[1, 3, 2, 2]$$$. \u003c/li\u003e\u003cli\u003e Evaluate $$$(1,3)$$$ and create a new link since $$$\\delta_1 + \\delta_3 \u003d 1 + 2 \u003d 3$$$. The degree becomes $$$[2, 3, 3, 2]$$$. \u003c/li\u003e\u003cli\u003e Evaluate $$$(1,4)$$$ and create a new link since $$$\\delta_1 + \\delta_4 \u003d 2 + 2 \u003d 4$$$. The degree becomes $$$[3, 3, 3, 3]$$$. \u003c/li\u003e\u003c/ul\u003e The final result is a network with $$$6$$$ links and complete. \u003c/li\u003e\u003c/ul\u003e As we can see, $$$L_2$$$ produces a complete network, while $$$L_1$$$ is not.\u003cp\u003eOrdering a work to Go can be very expensive with lower $$$k$$$, thus, Andi has to make $$$k$$$ as high as possible while maintaining the possibility that a complete network can be achieved with $$$k$$$. In other words, Andi wants the highest $$$k$$$ such that there exists $$$L$$$ such that $$$go(G,k)$$$ can produce a complete network, and for any $$$j$$$ ($$$j \u0026gt; k$$$), there is no valid $$$L$$$ for $$$go(G,j)$$$ which can produce a complete network. Your task in this problem is to find such $$$k$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eInput begins with a line containing two integers: $$$N$$$ $$$M$$$ ($$$2 \\le N \\le 500$$$; $$$0 \\le M \u0026lt; \\frac{N \\times (N - 1)}{2}$$$) representing the number of machines and the number existing links, respectively. The machines are numbered from $$$1$$$ to $$$N$$$. The next $$$M$$$ lines, each contains two integers: $$$a_i$$$ $$$b_i$$$ ($$$1 \\le a_i \u0026lt; b_i \\le N$$$) representing an existing link connecting machine $$$a_i$$$ and $$$b_i$$$. You are guaranteed that each pair $$$(a_i, b_i)$$$ will appear at most once in the input.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput contains an integer $$$k$$$ in a line, as requested.\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\u003e4 3\n1 2\n2 3\n3 4\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":"","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 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\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 2\n1 2\n3 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\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\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eExplanation for the sample input/output #2\u003c/span\u003e\u003c/p\u003e\u003cp\u003eAndi\u0027s network has no link at all at the beginning. To make his network complete, Andi has to order $$$go(G,0)$$$.\u003c/p\u003e"}}]}