{"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 \u003cp\u003eYour sports club has a rivaling sports club in the same\n city. They did some awful things to you and you want to get\n back at them. You have learned that they are planning on doing\n a ’drop’: they drive people blindfolded to a city none of the\n participants know and tell them to find a specific place, the\n goal. They then have fun randomly walking through the city\n trying to find the goal.\u003c/p\u003e\n\n \u003cp\u003eYou intend to spoil their fun thoroughly: you know that they\n promise a prize for whoever reaches the goal first, so the\n participants will use all available means to get to the goal.\n Indeed, you are fairly sure that if you set up official-looking\n signposts in that city in advance, they will probably follow\n them. You therefore decide to place signposts throughout the\n city so that no matter where the participants get dropped, they\n can follow the signposts to the goal; this takes out the\n element of ’randomly walking around’ and therefore all the\n fun.\u003c/p\u003e\n\n \u003cp\u003eHowever, official-looking signposts are not cheap and\n attract a lot of attention, particularly from police officers.\n So you wish to minimize the number of signposts you have to\n place in the city. This may lead the participants to use a very\n slow detour, but they don’t know the city anyway, so they won’t\n find out.\u003c/p\u003e\n\n \u003cdiv id\u003d\"a0000000562\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/d0aa7895b9d740b2b8697fbe82afc30a?v\u003d1714790088\" alt\u003d\"\\includegraphics[width\u003d0.8\\textwidth ]{dropping}\" style\u003d\"width:80.00%\"\u003e\n\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: City of 2nd and 3rd sample input. The\n 2nd input has the goal at intersection 5 and the 3rd at\n 4.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n\n \u003cp\u003eYou get yourself a map of the city and start planning. You\n notice one nice aspect of the city: all intersections are\n cross-shaped, so it is easy to predict where participants will\n go to: they will just go to the opposite side of the\n intersection they arrive at. If a participant gets dropped at\n an intersection with a signpost, he or she will follow that\n sign; otherwise they go in an arbitrary direction until they\n hit a sign post. You know that participants never get dropped\n at the goal (that would be silly).\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 100. After that per test case:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eone line with two space-separated integers \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$g$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$5 \\leq n \\leq 100\\, 000$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq g \\leq n$\u003c/span\u003e):\n the number of intersections and the goal, respectively.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines, each\n with four space-separated integers \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$d$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq a, b, c, d \\leq n$\u003c/span\u003e). The\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e-th line gives the\n intersections you end up at if you follow one of the roads\n adjacent to the \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e-th\n intersection; more precisely, participants who approach the\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e-th intersection\n coming from intersection \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e will continue towards\n intersection \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e and\n vice versa, while participants coming from intersection\n \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e will continue\n towards intersection \u003cspan class\u003d\"tex2jax_process\"\u003e$d$\u003c/span\u003e and vice versa.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eEach intersection connects to four different other\n intersections.\u003c/p\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 signposts needed to ruin the fun.\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\u003e4\n5 5\n2 3 4 5\n3 4 5 1\n4 5 1 2\n5 1 2 3\n1 2 3 4\n5 5\n5 3 2 4\n4 5 3 1\n1 5 2 4\n1 3 5 2\n1 3 2 4\n5 4\n5 3 2 4\n4 5 3 1\n1 5 2 4\n1 3 5 2\n1 3 2 4\n5 5\n5 3 2 4\n4 5 3 1\n1 5 2 4\n1 5 2 3\n1 3 2 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n0\n1\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 "}}]}