{"trustable":true,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\n\u003cdiv class\u003d\"panel_content\"\u003e\n著名的ACM(高级计算机制造商)公司租了一栋楼的一层,其形状如下图所示。\n\u003cbr\u003e\n\u003cbr\u003e\n\u003ccenter\u003e\n \u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/a74c8ffcd138148ec900dc6bb09d32dd?v\u003d1697073306\"\u003e\n\u003c/center\u003e\n\u003cbr\u003e\n\u003cbr\u003e\n该楼层有200个房间,分别位于走廊的北侧和南侧。最近,公司制定了一项改革计划。改革包括在房间之间移动许多桌子。由于走廊很窄,而且所有的桌子都很大,只能通过一个桌子。需要制定一些计划以提高移动效率。经理想出了以下计划:将一张桌子从一个房间移动到另一个房间可以在10分钟内完成。当将一张桌子从房间i移动到房间j时,使用的是房间i前面和房间j前面之间的走廊部分。因此,在每10分钟内,将同时进行几次在走廊的不同部分之间移动的操作。为了清楚起见,经理说明了同时移动的可能情况和不可能情况。\n\u003cbr\u003e\n\u003cbr\u003e\n\u003ccenter\u003e\n \u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/bb95b88268c2f9e12a0430067bc6669e?v\u003d1697073306\"\u003e\n\u003c/center\u003e\n\u003cbr\u003e\n\u003cbr\u003e\n对于每个房间,最多只能移动一张桌子。现在,经理正在寻找一种方法来最小化移动所有桌子所需的时间。您的任务是编写一个程序来解决经理的问题。\n\u003cbr\u003e\n\u003c/div\u003e\n"}},{"title":"输入","value":{"format":"HTML","content":"输入由T个测试用例组成。第一行给出了测试用例的数量T。每个测试用例以包含一个整数N的行开始,其中1≤N≤200,表示要移动的桌子数量。接下来的N行中,每行包含两个正整数s和t,表示要将一张桌子从房间号s移动到房间号t(每个房间号在N行中最多出现一次)。从第N+3行开始,以与上述相同的方式列出剩余的测试用例。\n\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"输出应包含完成移动所需的最短时间(以分钟为单位),每行一个。\n\u003cbr\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003e输入\u003c/th\u003e\n \u003cth\u003e输出\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 \r\n4 \r\n10 20 \r\n30 40 \r\n50 60 \r\n70 80 \r\n2 \r\n1 3 \r\n2 200 \r\n3 \r\n10 100 \r\n20 80 \r\n30 50 \r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\r\n20\r\n30\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}