{"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\u003eThere are thousands of Buddhist temples in Thailand, known as \"wat\". Some of them, such as the \"Wat Phra Kaew\" in Bangkok\u0027s Grand Palace, are specially regarded for their importance and they\u0027re called royal temples. The \"Wat Phra Kaew\" is famous for housing the Emerald Buddha statue, a national treasure. In 2016, the ACM ICPC World Finals will take place in Phuket, Thailand, and so increased tourism is expected in this city. The authorities in Phuket thus want to improve security in its royal temples.\u003c/p\u003e\u003cp\u003ePhuket\u0027s Security Unit (PSU) hired the researcher Lua \"the ingenious\" Kuratowski. PSU needs to solve the following problem. Given \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e royal temples and\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e streets connecting them, they must position guards at these streets so that every royal temple can be under surveillance. They consider a temple as secured if there is a guard in at least one of the streets ending at the temple. Streets were laid out so that one can reach any temple from any other. Moreover, due to a cultural dislike of odd numbers, any time someone starts a walk at a temple and returns to it, the number of streets traversed is always even.\u003c/p\u003e\u003cp\u003eLua knows you wish to advance to the World Finals next year, and she considers this to be a good test for your skills. She challenges you to find a solution with the minimum number of guards.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line has a single integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e, the number of test cases.\u003c/p\u003e\u003cp\u003eEach test case spans several input lines. The first line has two integers, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e and\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e, the number of royal temples and the number of streets joining temples, respectively. Each temple is represented by an integer between\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e. The next\u0026nbsp;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e lines describe the streets. Each street is represented by two integers, corresponding to the temples it joins.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eLimits\u003c/span\u003e \u003c/p\u003e\u003cul\u003e \u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eT\u003c/i\u003e ≤ 10\u003c/span\u003e \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e3\u003c/sup\u003e\u003c/span\u003e \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eM\u003c/i\u003e ≤ 5·10\u003csup class\u003d\"upper-index\"\u003e3\u003c/sup\u003e\u003c/span\u003e \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each instance, print a single line with the minimum number of guards needed to have all royal temples under surveillance.\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\u003e2\n5 5\n1 2\n1 4\n2 3\n4 3\n3 5\n4 3\n1 2\n1 3\n1 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}