{"problem":{"name":"Must Be Rectangular!","description":{"content":"There are $N$ dots in a two-dimensional plane. The coordinates of the $i$\\-th dot are $(x_i, y_i)$. We will repeat the following operation as long as possible: *   Choose four integers $a$, $b$, $c$,","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc131_f"},"statements":[{"statement_type":"Markdown","content":"There are $N$ dots in a two-dimensional plane. The coordinates of the $i$\\-th dot are $(x_i, y_i)$.\nWe will repeat the following operation as long as possible:\n\n*   Choose four integers $a$, $b$, $c$, $d$ $(a \\neq c, b \\neq d)$ such that there are dots at exactly three of the positions $(a, b)$, $(a, d)$, $(c, b)$ and $(c, d)$, and add a dot at the remaining position.\n\nWe can prove that we can only do this operation a finite number of times. Find the maximum number of times we can do the operation.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^5$\n*   $1 \\leq x_i, y_i \\leq 10^5$\n*   If $i \\neq j$, $x_i \\neq x_j$ or $y_i \\neq y_j$.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$x_1$ $y_1$\n$:$\n$x_N$ $y_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc131_f","tags":[],"sample_group":[["3\n1 1\n5 1\n5 5","1\n\nBy choosing $a = 1$, $b = 1$, $c = 5$, $d = 5$, we can add a dot at $(1, 5)$. We cannot do the operation any more, so the maximum number of operations is $1$."],["2\n10 10\n20 20","0\n\nThere are only two dots, so we cannot do the operation at all."],["9\n1 1\n2 1\n3 1\n4 1\n5 1\n1 2\n1 3\n1 4\n1 5","16\n\nWe can do the operation for all choices of the form $a = 1$, $b = 1$, $c = i$, $d = j$ $(2 \\leq i,j \\leq 5)$, and no more. Thus, the maximum number of operations is $16$."]],"created_at":"2026-03-03 11:01:13"}}