{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:30.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/db8d103622e663b40d4d598243626d8f?v\u003d1718970864\" alt\u003d\"/problems/amanda/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\n\n \u003cp\u003e\u003cspan class\u003d\"scshape\"\u003eAmanda Air\u003c/span\u003e has routes between\n many different airports, and has asked their most important\n frequent flyers, members of the AA\u0026nbsp;Frequent\u0026nbsp;Flyer\n program, which routes they most often fly. Based on this\n survey, Amanda, the CEO and owner, has concluded that\n \u003cspan class\u003d\"scshape\"\u003eAmanda Air\u003c/span\u003e will place lounges at\n some of the airports at which they operate.\u003c/p\u003e\n\n \u003cp\u003eHowever, since there are so many routes going between a wide\n variety of airports, she has hired you to determine how many\n lounges she needs to build, if at all possible, given the\n constraints set by her. This calculation is to be provided by\n you, before any lounges are built. Her requirements specifies\n that for some routes, there must be lounges at both airports,\n for other routes, there must be lounges at exactly one of the\n airports, and for some routes, there will be no lounges at the\n airports.\u003c/p\u003e\n\n \u003cp\u003eShe is very economically minded and is demanding the\n absolute minimum number of lounges to be built.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe first line contains two non-negative integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq n,m \\leq 200\\;\n 000$\u003c/span\u003e, giving the number of airports and routes in the\n Amanda Catalog respectively. Thereafter\n follow\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e lines,\n each describing a route by three non-negative integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq a, b \\leq n$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$c \\in \\{ 0,1,2\\} $\u003c/span\u003e,\n where\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e\n and\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e are the\n airports the route connects and\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e is the number of lounges.\u003c/p\u003e\n\n \u003cp\u003eNo route connects any airport with itself, and for any two\n airports at most one requirement for that route is given. As\n one would expect,\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e\n is a request for no lounge,\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e for a lounge at exactly one of the\n two airports and\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e\n for lounges at both airports.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eIf it is possible to satisfy the requirements, give the\n minimum number of lounges necessary to do so. If it is not\n possible, output \u003ctt class\u003d\"ttfamily\"\u003eimpossible\u003c/tt\u003e.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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 4\n1 2 2\n2 3 1\n3 4 1\n4 1 2\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\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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 5\n1 2 1\n2 3 1\n2 4 1\n2 5 1\n4 5 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eimpossible\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 3\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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 5\n1 2 1\n2 3 0\n2 4 1\n3 1 1\n3 4 1\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\u003c/body\u003e\n "}}]}