{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"著名的ACM(高级计算机制造商)公司租用了一栋建筑的一层,其形状如下图所示。\r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/c388b4e0fadc0651cd966f3adb41cf17?v\u003d1708863260\"\u003e\u003c/center\u003e\r\u003cbr\u003e该楼层有200间房间,沿走廊分布在北侧和南侧。最近,公司制定了一项改革计划。改革包括在房间之间搬动大量桌子。由于走廊狭窄且所有桌子都很大,只能通过一个桌子。需要一些计划来使搬运更加高效。经理想出了以下计划:从一个房间搬动桌子到另一个房间可以在10分钟内完成。当从房间i搬动桌子到房间j时,使用的是房间i前面到房间j前面之间的走廊部分。因此,在每10分钟内,将同时进行几次两个不共享走廊部分的房间之间的搬运。为了使其清晰,经理说明了同时搬运的可能情况和不可能情况。\r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/d8b055423140e9f59c854b7497237913?v\u003d1708863260\"\u003e\u003c/center\u003e\r\u003cbr\u003e对于每个房间,最多只能搬进或搬出一张桌子。现在,经理正在寻找一种方法来最小化搬动所有桌子所需的时间。你的任务是编写一个程序来解决经理的问题。"}},{"title":"输入","value":{"format":"HTML","content":"输入包含T个测试用例。输入文件的第一行给出测试用例的数量T。每个测试用例以包含一个整数N的行开始,其中1 \u003c\u003d N \u003c\u003d 200,表示要移动的桌子数量。\r\u003cbr\u003e接下来的N行中,每行包含两个正整数s和t,表示要从房间号为s的房间移动到房间号为t的房间(每个房间号在N行中最多出现一次)。从第3+N行开始,其余测试用例以与上述相同的方式列出。"}},{"title":"输出","value":{"format":"HTML","content":"输出应包含完成搬运所需的最短时间(以分钟为单位),每行一个。"}},{"title":"示例","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\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\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}