{"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/db570b196548330ad7e884748ac38028?v\u003d1714723416\" alt\u003d\"/problems/floatingformation/file/statement/en/img-0001.png\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\n\n \u003cp\u003eIndustrial design students have come up with an amazing\n idea: they have made some awesome pieces of design and they\n want to showcase them floating on the water of the IJsselmeer!\n Unfortunately, their designs do not stay afloat by themselves,\n so they took a few boats and used them to tie designs\n together.\u003c/p\u003e\n\n \u003cp\u003eThe left and right sides of a boat have rope connection\n points that can be tied to designs. A boat can therefore be\n attached to at most two designs. A design that is connected to\n two or more boats will stay afloat indefinitely. Unfortunately,\n designs that are connected to only one boat will not float\n properly: the part of the design furthest away from the boat\n will sink a bit and be partially in the water, so it will soak,\n making the design heavier, which will eventually sink the\n design, making it too heavy for the boat to keep afloat. A boat\n that is attached to a design that has sunk will detach itself\n from the other design it is attached to, if applicable, and\n will carry the soaked design back to shore. Designs that are\n soaked are placed on the beach, but the students want the ship\n that brought the design to shore to stay attached to the soaked\n design, as they feel this composition has artistic value. The\n boat will therefore not go back to the designs that are still\n floating, which means that if the boat was attached to another\n design, that design loses a supporting boat and will also start\n to sink!\u003c/p\u003e\n\n \u003cp\u003eKeeping the above in mind, there are simple ways to string\n the designs together with boats so that no design sinks, such\n as forming a circle. This is not the approach that the students\n used: their approach involved much creativity. The result,\n although a single connected component, is a configuration that\n leaves many designs connected by only one boat and hence in\n danger of sinking. You also note that the students have always\n attached boats to two designs: there are no boats that are\n attached to a single design. Also, boats can never be attached\n to a single design twice, and there are no two boats that are\n attached to the same pair of designs.\u003c/p\u003e\n\n \u003cp\u003eReluctantly, the students have admitted that they may have\n made mistakes, so they have asked you to use the few boats they\n have left to keep as many designs afloat as possible. As the\n current configuration has much artistic value, you are not\n allowed to change it. In fact, you are only allowed to use the\n connection points on the left sides of the spare boats (you are\n not allowed to use the right side), so that the geometric\n ordering of the boats is not changed.\u003c/p\u003e\n\n \u003cp\u003eGiven this situation, how can you use the boats so that the\n number of designs that end up sunk is minimized? Note that we\n want your program to be able to handle non-planar\n configurations as well, in case the students ever turn to air\n balloons. For all testcases, you may assume that at least one\n design would stay afloat, even if none of the spare boats are\n used.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eOn the first line one positive number: the number of test\n cases, at most \u003cspan class\u003d\"tex2jax_process\"\u003e$20$\u003c/span\u003e. After\n that per test case:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eone line with three space-separated integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq n, m, k \\leq 10\\, 000$\u003c/span\u003e):\n the number of designs, used boats and spare boats\n respectively.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e lines, each\n with two space-separated integers \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq a, b \\leq n$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$a \\neq b$\u003c/span\u003e): a boat is\n attached to design \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e\n on its left side and design \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e on its right side.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003ePer test case:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eone line with a single integer: the smallest number of\n designs that are eventually sunk after employing the spare\n ships.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\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\u003e2\n6 6 1\n1 2\n2 3\n1 3\n1 4\n4 5\n1 6\n11 11 3\n1 2\n2 3\n1 3\n1 4\n4 5\n2 6\n3 7\n7 8\n7 9\n8 10\n9 11\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}