{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"G - JOJO\u0027s Factory \u003cp\u003eAki is the prime minister in JOJO\u0027s Factory.\u003c/p\u003e\n\u003cp\u003eThere are two types of machines in the factory, which are called A-machine and B-machine respectively. Both the number of two types of machines are $$$N$$$. One A-machine should work with exactly one B-machine and one B-machine should work with exactly one A-machine.\u003c/p\u003e\n\u003cp\u003eUnfortunately, some pairs of machines can not work together due to some unknown reason. A pair $$$(i,j)$$$ means $$$i$$$-th A-machine can not work with $$$j$$$-th B-machine.\u003c/p\u003e\n\u003cp\u003eIn order to improve the efficiency, you, his staff, should find a plan that the most A-machines can run normally.\u003c/p\u003e\n\u003cp\u003eLuckily, Aki is a talented prime minister, so the number of un-working pairs is no more than $$$2N-3$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers $$$N, M ~ (5 \\leq N \\leq 5 \\times 10^5; ~ 0 \\leq M \\leq 2N-3)$$$ denoting the count of machines and the count of pairs of machines that don\u0027t work together.\u003c/p\u003e\n\u003cp\u003eThen next $$$M$$$ lines follows, each containing two integers $$$i, j ~ (1 \\leq i, j \\leq N)$$$ denoting the un-working pairs. It is guaranteed that all pairs of $$$(i,j)$$$ are different.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput one line containing the maximal number of normally running A-machines.\u003c/p\u003e"}},{"title":"Example","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e4 5\n1 2\n3 1\n1 3\n1 4\n1 1\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e3\n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}}]}