{"problem":{"name":"[ICPC 2020 Nanjing R] Certain Scientific Railgun","description":{"content":"Misaka Mikoto is the third-ranked Level 5 esper in $\\textit{Academy City}$ and has been nicknamed $\\textit{Railgun}$ due to her signature move. One day, several evil robots invade Academy City and Mis","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9624"},"statements":[{"statement_type":"Markdown","content":"Misaka Mikoto is the third-ranked Level 5 esper in $\\textit{Academy City}$ and has been nicknamed $\\textit{Railgun}$ due to her signature move. One day, several evil robots invade Academy City and Misaka is planning to terminate all of them.\n\nConsider Academy City as a 2-dimensional plane. There are $n$ robots in total and the position of the $i$-th robot is $(x_i, y_i)$. Misaka will start moving from $(0, 0)$ and her railgun ability will terminate all robots sharing the same $x$- or $y$-coordinate with her. More formally, if Misaka is now located at $(x_m, y_m)$, all robots whose $x_i = x_m$ or $y_i = y_m$ will be terminated.\n\nAs Misaka hates decimals and Euclidean geometry, she will only move from one integer point to another integer point and can only move horizontally (parallel to the $x$-axis) or vertically (parallel to the $y$-axis). As moving among the city is quite tiresome, Misaka asks you to calculate the minimum distance she has to move to terminate all robots.\n\nRecall that an integer point is a point whose $x$-coordinate and $y$-coordinate are both integers.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe first line contains an integer $n$ ($1 \\leq n \\leq 10^5)$ indicating the number of robots.\n\nFor the following $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($-10^9 \\le x_i, y_i \\le 10^9$) indicating the position of the $i$-th robot.\n\nIt is guaranteed that the sum of $n$ of all test cases will not exceed $10^5$.\n\n## Output\n\nFor each test case output one line containing one integer indicating the minimum distance Misaka needs to move to terminate all robots.\n\n[samples]\n\n## Note\n\n### Note\n\nFor the second sample test case, Misaka should first go to $(0, 1)$, then to $(0, 2)$, then to $(0, -3)$, then to $(0, -4)$.\n\nFor the third sample test case, Misaka should first go to $(1, 0)$, then to $(1, 1)$, then to $(3, 1)$.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9624","tags":["2020","线段树","二分","O2优化","ICPC","吉司机线段树 segment tree beats","南京"],"sample_group":[["3\n2\n0 1\n1 0\n4\n1 1\n-3 -3\n4 -4\n-2 2\n4\n1 100\n3 100\n-100 1\n3 -100\n","0\n8\n4\n"]],"created_at":"2026-03-03 11:09:25"}}