{"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\u003eJack and Jill are tired of the New Year tree, now they\u0027ve got a New Year cactus at home! A cactus is a connected undirected graph where any two simple cycles have at most one common vertex. In other words, this graph doesn\u0027t have any edges that lie on more than one simple cycle.\u003c/p\u003e\u003cp\u003eOn the 31st of December they are going to decorate the cactus by hanging toys to its vertices. At most one toy is going to hang on each vertex — it\u0027s either the toy Jack hung or the toy Jill hung. It\u0027s possible for a vertex to have no toys.\u003c/p\u003e\u003cp\u003eJack and Jill has been arguing, so they don\u0027t want any edge to connect two vertices where one vertex has Jack\u0027s toy and the other vertex has Jill\u0027s toy.\u003c/p\u003e\u003cp\u003eJack has decided to hang \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e toys. What maximum number of toys \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003c/span\u003e can Jill hang if they both cooperate to maximize this value? Your task is to write a program that finds the sought \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003c/span\u003e for all \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e from 0 to the number of vertices on the New Year Cactus.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 2500, \u003ci\u003en\u003c/i\u003e - 1 ≤ \u003ci\u003em\u003c/i\u003e\u003c/span\u003e) — the number of vertices and the number of edges, correspondingly. The next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e lines contain two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003c/span\u003e each (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e, \u003ci\u003eb\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003ea\u003c/i\u003e ≠ \u003ci\u003eb\u003c/i\u003e\u003c/span\u003e) that mean that there is an edge connecting vertices \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e и \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003c/span\u003e. Any pair of vertices has at most one edge between them.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eThe first line must contain space-separated \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (for all \u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003ea\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e equals the maximum number of Jill\u0027s toys on the cactus considering that it has \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e Jack\u0027s toys. Numbers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e go in the order of increasing \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e.\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\u003e1 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 0 \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\u003e16 20\n1 2\n3 4\n5 6\n6 7\n7 8\n9 10\n10 11\n11 12\n13 14\n15 16\n1 5\n9 13\n14 10\n10 6\n6 2\n15 11\n11 7\n7 3\n16 12\n8 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e16 13 12 12 10 8 8 7 6 4 4 3 3 1 0 0 0 \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\u003eThe cactus from the second example is:\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/f46aa6e98a639a978d838a7c6f410609?v\u003d1715663101\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e"}}]}