Problem:
 Score : 600 points    Problem Statement 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 , 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.   We 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.      Constraints  1 \leq N \leq 10^5  1 \leq x_i, y_i \leq 10^5  If i \neq j , x_i \neq x_j or y_i \neq y_j .  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  x_1  y_1  :  x_N  y_N       Output Print the maximum number of times we can do the operation.        Sample Input 1 3
1 1
5 1
5 5      Sample Output 1 1  By 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 .       Sample Input 2 2
10 10
20 20      Sample Output 2 0  There are only two dots, so we cannot do the operation at all.       Sample Input 3 9
1 1
2 1
3 1
4 1
5 1
1 2
1 3
1 4
1 5      Sample Output 3 16  We 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 .

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    def Count(self, x):
        return -self.root[self.Find_Root(x)]

m = 100010
uf = UnionFind(m*2)
n = int(input())
for i in range(n):
    x,y = map(int,input().split())
    y = y+m
    uf.Unite(x,y)

lx = {}
ly = {}
ans = 0
for i in range(m):
    rx = uf.Find_Root(i)
    lx[rx] = lx.get(rx,0)+1
    ry = uf.Find_Root(i+m)
    ly[ry] = ly.get(ry,0)+1
for i in range(m*2):
    ans += lx.get(i,0)*ly.get(i,0)

print(ans-n)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return tuple(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, XY):
    g = [[] for _ in range((10**5)*2)]
    offset = 10**5
    cs = set()
    for x, y in XY:
        x -= 1
        y = y - 1 + offset
        g[x].append(y)
        g[y].append(x)
        cs.add(x)
        cs.add(y)
    ans = 0
    while cs:
        error_print(len(cs))
        q = set([cs.pop()])
        done = set()
        done_c = set()
        while q:
            v = q.pop()
            for u in g[v]:
                if v >= offset:
                    e = (u, v)
                else:
                    e = (v, u)
                if e not in done:
                    q.add(u)
                    done.add(e)
                    done_c.add(u)
                    done_c.add(v)
        xn = set()
        yn = set()
        for v, u in done:
            for z in (v, u):
                if z >= offset:
                    yn.add(z)
                else:
                    xn.add(z)
        ans += (len(xn) * len(yn)) - len(done)
        cs -= done_c

    return ans

def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, XY))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return tuple(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, XY):
    g = [[] for _ in range((10**5)*2)]
    offset = 10**5
    cs = set()
    for x, y in XY:
        x -= 1
        y = y - 1 + offset
        g[x].append(y)
        g[y].append(x)
        cs.add(x)
        cs.add(y)
    ans = 0
    while cs:
        error_print(len(cs))
        q = set([cs.pop()])
        done = set()
        done_c = set()
        while q:
            v = q.pop()
            for u in g[v]:
                if v >= offset:
                    e = (u, v)
                else:
                    e = (v, u)
                if e not in done:
                    q.add(u)
                    done.add(e)
                    done_c.add(u)
                    done_c.add(v)
        xn = set()
        yn = set()
        for v, u in done:
            for z in (v, u):
                if z >= offset:
                    yn.add(z)
                else:
                    xn.add(z)
        ans += (len(xn) * len(yn)) - len(done)
        cs -= done_c

    return ans

def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, XY))


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class DGraph:
    def __init__(self, n, edges):
        self._vertice = [{} for _ in range(n)]
        for e in edges:
            self._vertice[e[0]][e[1]] = e[2] if len(e) == 3 else 1

    def __len__(self):
        return len(self._vertice)

    def edges(self, n=None):
        srcs = range(len(self)) if n is None else [n]
        return sum([[(s, d, c) for d, c in self._vertice[s].items()] for s in srcs], [])

    def transpose(self):
        tedges = [(t, f, c) for f, t, c in self.edges()]
        return DGraph(len(self), tedges)

    def cost(self, src, dst):
        return self._vertice[src].get(dst, float('inf'))

class Graph(DGraph):
    def __init__(self, n, edges):
        nd_edges = edges + [(d, s, c) for s, d, c in edges]
        super().__init__(n, nd_edges)

    def transpose(self):
        return self


def solve(N: int, x: "List[int]", y: "List[int]"):
    xs = {v:i for i, v in enumerate(set(x))}
    ys = {v:i for i, v in enumerate(set(y), len(xs))}
    
    n = len(xs) + len(ys)
    es = [(xs[cx], ys[cy], 1) for cx, cy in zip(x, y)]
    g = Graph(n, es)

    visited = [False] * len(g)
    def dfs(g, src):
        nonlocal visited
        stack = [(src, 0)]
        while stack:
            n, c = stack.pop()
            if visited[n]:
                continue
            visited[n] = True

            for _, d, _ in g.edges(n):
                
                stack.append((d, c + 1))
            yield n

    def _f(i):
        ls = list(i)
        if len(ls) == 0:
            return 0

        xc = 0
        yc = 0
        es = 0
        for i in ls:
            es += len(g.edges(i))
            if i < len(xs):
                xc += 1
            else:
                yc += 1
        es //= 2

        if xc < 2 or yc < 2:
            return 0

        return xc * yc - es

    return sum([_f(dfs(g, i)) for i in range(n)])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    x = [int()] * (N)  
    y = [int()] * (N)  
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    result = solve(N, x, y)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class DGraph:
    def __init__(self, n, edges):
        self._vertice = [{} for _ in range(n)]
        for e in edges:
            self._vertice[e[0]][e[1]] = e[2] if len(e) == 3 else 1

    def __len__(self):
        return len(self._vertice)

    def edges(self, n=None):
        srcs = range(len(self)) if n is None else [n]
        return sum([[(s, d, c) for d, c in self._vertice[s].items()] for s in srcs], [])

    def transpose(self):
        tedges = [(t, f, c) for f, t, c in self.edges()]
        return DGraph(len(self), tedges)

    def cost(self, src, dst):
        return self._vertice[src].get(dst, float('inf'))

class Graph(DGraph):
    def __init__(self, n, edges):
        nd_edges = edges + [(d, s, c) for s, d, c in edges]
        super().__init__(n, nd_edges)

    def transpose(self):
        return self


def solve(N: int, x: "List[int]", y: "List[int]"):
    xs = {v:i for i, v in enumerate(set(x))}
    ys = {v:i for i, v in enumerate(set(y), len(xs))}
    
    n = len(xs) + len(ys)
    es = [(xs[cx], ys[cy], 1) for cx, cy in zip(x, y)]
    g = Graph(n, es)

    visited = [False] * len(g)
    def dfs(g, src):
        nonlocal visited
        stack = [(src, 0)]
        while stack:
            n, c = stack.pop()
            if visited[n]:
                continue
            visited[n] = True

            for _, d, _ in g.edges(n):
                
                stack.append((d, c + 1))
            yield n, c

    def _f(i):
        ls = list(i)
        if len(ls) == 0:
            return 0

        xc = 0
        yc = 0
        es = 0
        for i, _ in ls:
            es += len(g.edges(i))
            if i < len(xs):
                xc += 1
            else:
                yc += 1
        es //= 2

        if xc < 2 or yc < 2:
            return 0

        return xc * yc - es

    return sum([_f(dfs(g, i)) for i in range(n)])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    x = [int()] * (N)  
    y = [int()] * (N)  
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    result = solve(N, x, y)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind:

  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0] * n
    self.sizes = [1] * n

  def find(self, x):
    if self.par[x] != x:
      self.par[x] = self.find(self.par[x])
    return self.par[x]

  def union(self, x, y):
    x, y = self.find(x), self.find(y)
    if x == y:
      return False
    elif self.rank[x] < self.rank[y]:
      self.par[x] = y
      self.sizes[y] += self.sizes[x]
    elif self.rank[x] > self.rank[y]:
      self.par[y] = x
      self.sizes[x] += self.sizes[y]
    else:
      self.par[y] = x
      self.rank[x] += 1
      self.sizes[x] += self.sizes[y]
    return True

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def size(self, x):
    return self.sizes[self.find(x)]

n = int(input())
nx = [0 for i in range(200020)]
ny = [0 for i in range(200020)]
uf = UnionFind(200020)
for i in range(n):
  x, y = list(map(int, input().split()))
  uf.union(x, y+100010)
ans = 0
for i in range(100010):
  nx[uf.find(i)] += 1
  ny[uf.find(i+100010)] += 1
for i in range(200020):
  ans += nx[i]*ny[i]
print(ans-n)

Solution (Python):

import sys
from collections import defaultdict
from collections import deque


def solve(N: int, X: "List[int]", Y: "List[int]"):
    adj = defaultdict(list)
    done = set()
    for x, y in zip(X, Y):
        xnode = (x, 0)
        ynode = (y, 1)
        adj[xnode].append(ynode)
        adj[ynode].append(xnode)

    points_to_add = 0    
    for x, y in zip(X, Y):
        xnode = (x, 0)
        ynode = (y, 1)
        if xnode in done or ynode in done:
            continue
        x_count = 1
        y_count = 0
        done.add(xnode)
        Q = deque()
        Q.append(xnode)
        while len(Q) > 0:
            node = Q.pop()
            for node_next in adj[node]:
                if node_next in done:
                    continue
                if node_next[1] == 0:
                    x_count += 1
                else:
                    y_count += 1
                Q.append(node_next)
                done.add(node_next)
        points_to_add += x_count * y_count
    print(points_to_add - N)
        
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    x = [int()] * (N)  
    y = [int()] * (N)  
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
from scipy.sparse import csr_matrix, csgraph
import sys

input = sys.stdin.readline

U = 10 ** 5
n = int(input())
xy = np.array([input().split() for _ in range(n)], dtype=np.int32)

graph = csr_matrix((np.ones(n, dtype=np.bool), (xy[:, 0], U + xy[:, 1])), (2 * U + 1, 2 * U + 1))
_, component = csgraph.connected_components(graph)

x_cnt = np.bincount(component[:U + 1], minlength=2 * U + 2)
y_cnt = np.bincount(component[U + 1:], minlength=2 * U + 2)
pts_cnt = np.bincount(component[xy[:, 0]], minlength=2 * U + 2)
answer = (x_cnt * y_cnt - pts_cnt).sum()
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
from collections import defaultdict

class UnionFind:
    def __init__(self, N=None):
        if N is None or N < 1:
            self.parent = defaultdict(lambda: -1)
        else:
            self.parent = [-1]*int(N)

    def root(self, n):
        if self.parent[n] < 0:
            return n
        else:
            m = self.root(self.parent[n])
            self.parent[n] = m
            return m

    def merge(self, m, n):
        rm = self.root(m)
        rn = self.root(n)
        if rm != rn:
            if -self.parent[rm] < -self.parent[rn]:
                rm, rn = rn, rm
            self.parent[rm] += self.parent[rn]
            self.parent[rn] = rm

    def size(self, n):
        return -self.parent[self.root(n)]
    
    def connected(self, m, n):
        return self.root(m) == self.root(n)
    
    def groups(self):
        if isinstance(self.parent,list):
            return list(map(lambda x: x<0, self.parent)).count(True)
        else: 
            return list(map(lambda x: x<0, self.parent.values())).count(True) 

N = int(input())
uf = UnionFind()
for _ in range(N):
    x, y = inpl()
    uf.merge(2*x,2*y+1)

nxny = defaultdict(lambda: [0, 0])
for k in uf.parent.keys():
    nxny[uf.root(k)][k % 2] += 1

ans = sum([ nx * ny for nx, ny in nxny.values() ]) - N
print(ans)

Solution (Python):
N = int(input())
xy = [tuple(map(int,input().split())) for _ in range(N)]
shift = 10**5+1

nodes = {}
visited = {}

for x,y in xy:
    y += shift
    if x in nodes:
        nodes[x].append(y)
    else:
        nodes[x] = [y]
    if y in nodes:
        nodes[y].append(x)
    else:
        nodes[y] = [x]
    visited[x] = False
    visited[y] = False

ans = 0

def dfs(s, nodes,visited):
    q = [s]
    cnt_x = 0
    cnt_y = 0
    
    while q:
        v = q.pop()
        if visited[v]:
            continue
        visited[v] = True
        
        if v//shift < 1:
            cnt_x += 1
        else:
            cnt_y += 1
            
        q.extend(nodes[v])
        
    return visited, cnt_x*cnt_y

for s in nodes:
    if visited[s]:
        continue
    visited, cnt = dfs(s,nodes, visited)
    ans += cnt
    
print(ans - N)

Solution (Python):
import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
from collections import defaultdict

class UnionFind:
    def __init__(self, N=None):
        if N is None or N < 1:
            self.parent = defaultdict(lambda: -1)
        else:
            self.parent = [-1]*int(N)

    def root(self, n):
        if self.parent[n] < 0:
            return n
        else:
            m = self.root(self.parent[n])
            self.parent[n] = m
            return m

    def merge(self, m, n):
        rm = self.root(m)
        rn = self.root(n)
        if rm != rn:
            if -self.parent[rm] < -self.parent[rn]:
                rm, rn = rn, rm
            self.parent[rm] += self.parent[rn]
            self.parent[rn] = rm

    def size(self, n):
        return -self.parent[self.root(n)]
    
    def connected(self, m, n):
        return self.root(m) == self.root(n)
    
    def groups(self):
        if isinstance(self.parent,list):
            return list(map(lambda x: x<0, self.parent)).count(True)
        else: 
            return list(map(lambda x: x<0, self.parent.values())).count(True) 

class CountUp:
    def __init__(self, start=0):
        self.index = start-1

    def __call__(self):
        self.index += 1
        return self.index

N = int(input())
uf = UnionFind()
for _ in range(N):
    x, y = inpl()
    uf.merge(2*x+1,2*y)

Ng = uf.groups()
nx = [0]*Ng
ny = [0]*Ng
gi = defaultdict(CountUp())
for k in uf.parent.keys():
    if k % 2:
        nx[gi[uf.root(k)]] += 1
    else:
        ny[gi[uf.root(k)]] += 1

ans = sum([ nx[g]*ny[g] for g in range(Ng) ]) - N
print(ans)

Solution (Python):
"""
https://atcoder.jp/contests/abc131/submissions/6086380
"""
import os
import sys

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))
PAD = 10 ** 5 + 1
X = np.array(X)
Y = np.array(Y) + PAD

graph = csr_matrix(([True] * N, (X, Y)), shape=(PAD * 2, PAD * 2))

_, components = connected_components(graph)



x_cnt = np.bincount(components[:PAD], minlength=PAD * 2)
y_cnt = np.bincount(components[PAD:], minlength=PAD * 2)


print((x_cnt * y_cnt).sum() - N)

Solution (Python):
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

yx = defaultdict(lambda: set())
xy = defaultdict(lambda: set())
for x, y in zip(X, Y):
    xy[x].add(y)
    yx[y].add(x)


def connected(x=None, y=None, xret=None, yret=None):
    xret = xret if xret else set()
    yret = yret if yret else set()

    if x is not None:
        for y in xy[x]:
            if y in yret:
                continue
            yret.add(y)
            xret, yret = connected(y=y, xret=xret, yret=yret)
    if y is not None:
        for x in yx[y]:
            if x in xret:
                continue
            xret.add(x)
            xret, yret = connected(x=x, xret=xret, yret=yret)

    return xret, yret


x_counted = set()
y_counted = set()


ans = 0
for x in xy.keys():
    if x in x_counted:
        continue
    xs, ys = connected(x=x)
    
    ans += len(xs) * len(ys)
    x_counted |= xs
    y_counted |= ys

ans -= N
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

N = int(input().strip())

X = {}
Y = {}
G = (X, Y)

for _ in range(N):
  x, y = map(int, input().strip().split())
  if x not in X: X[x] = []
  if y not in Y: Y[y] = []
  X[x].append(y)
  Y[y].append(x)


def dfs_visit(visited, u, i):
  if u in visited[i]: return
  visited[i].add(u)
  for v in G[i][u]:
    dfs_visit(visited, v, (i + 1) % 2)


count = 0
i = 0
while len(X) > 0:
  visited = (set(), set())
  x = X.__iter__().__next__()
  dfs_visit(visited, x, 0)

  for x in visited[0]:
    count += len(visited[1]) - len(X.pop(x))

print(count)

Solution (Python):
import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())




sys.setrecursionlimit(100000)
class UnionFind():
    '''UnionFind木'''
    def __init__(self,n):
        self.data = [-1] * n
    
    def unite(self, x, y):
        '''x と y を結合'''
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        elif self.data[x] < self.data[y]:
            x, y = y, x  
        self.data[x] += self.data[y]
        self.data[y] = x
    
    def root(self, x):
        '''ノード x の親を返す'''
        if self.data[x] < 0:
            return x
        self.data[x] = self.root(self.data[x])
        return self.data[x]

    def same(self, x, y):
        '''x と y が同じグループに属するか判定'''
        return self.root(x) == self.root(y)
    
    def size(self, x):
        '''x を含むグループのノード数を返す'''
        return self.data[self.root(x)]
        


def ABC120_D():
    n, m = mi()
    a = [0] * m
    b = [0] * m
    for i in range(m):
        a[i], b[i] = mi()
        
    uf = UnionFind(n)
    ans = [0] * (m + 1)
    ans[m] = n * (n - 1) // 2

    for i in range(m - 1, -1, -1):
        a[i] -= 1
        b[i] -= 1
        ans[i] = ans[i + 1]
        if uf.same(a[i], b[i]):
            continue
        
        x = uf.size(a[i])
        y = uf.size(b[i])
        ans[i] -= x * y
        
        uf.unite(a[i],b[i])
    
    for i in range(1, m + 1):
        print(ans[i])




def ABC126_E():
    N, M = mi()
    uf = UnionFind(N)
    for i in range(M):
        _X, _Y, _Z = mi()
        uf.unite(_X - 1, _Y - 1)
    ans = 0
    for i in range(N):
        if uf.root(i) == i:
            ans += 1
    print(ans)



def ABC131_F():
    from collections import defaultdict
    MAX = 100010
    uf = UnionFind(2 * MAX)
    N = ii()
    for i in range(N):
        x, y = mi()
        uf.unite(x, y + MAX)
    
    mx = defaultdict(int)
    for i in range(MAX):
        mx[uf.root(i)] += 1
    my = defaultdict(int)
    for i in range(MAX,2*MAX):
        my[uf.root(i)] += 1
    ans = 0
    for i in range(2 * MAX):
        ans += mx[i] * my[i]
    print(ans - N)


if __name__ == '__main__':
    
    
    ABC131_F()

Solution (Python):
from collections import deque

N = int(input())
nmax = 2*10**5
nhalf = 10**5

G = [[] for i in range(nmax)]
for i in range(N):
    x,y = map(int,input().split())
    G[x-1].append(nhalf+y-1)
    G[nhalf+y-1].append(x-1)

used = [False] * nmax
ans = 0

for i in range(nhalf):
    
    if G[i] != [] and not used[i]:
        cnt_1 = 0  
        cnt_2 = 0  
        q = deque([i])
        used[i] = True 
        while len(q) > 0:
            a = q.popleft()
            if a < nhalf:
                cnt_2 += 1
            else:
                cnt_1 += 1
            Vs = G[a]
            
            for u in Vs: 
                if not used[u]:
                    q.append(u)
                    
                    used[u] = True
        ans += cnt_1*cnt_2
print(ans-N)

Solution (Python):
import sys

sys.setrecursionlimit(10**6)

N = int(input())
nmax = 100001


xys = [[[] for i in range(nmax)] for j in range(2)]

used = [[0 for i in range(nmax)] for j in range(2)]

for _ in range(N):
    x, y = map(int, input().split())
    xys[0][x].append(y)
    xys[1][y].append(x)




def dfs(i, el=0):
    
    for i in xys[el][i]:
        if not used[1-el][i]:
            used[1-el][i] = True
            dfs(i, 1-el)
            cnt[1-el] += 1

ans = 0
for i in range(nmax):
    
    if xys[0][i] != [] and used[0][i] == 0:
        used[0][i] = 1
        cnt = [1,0]
        dfs(i,0)
        ans += cnt[0]*cnt[1]
print(ans-N)

Solution (Python):
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :return:
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        
        if self._ranks[x] > self._ranks[y]:
            
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]


class WeightedUnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
            
            self._weights = [0 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}
            
            self._weights = {k: 0 for k in nodes}

    def unite(self, x, y, w):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :param w: x と y の重みの差; (重み y) - (重み x)
        :return:
        """
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return

        
        if self._ranks[rx] > self._ranks[ry]:
            
            self._parents[ry] = rx
            self._sizes[rx] += self._sizes[ry]
            
            self._weights[ry] = w + self._weights[x] - self._weights[y]
        else:
            
            self._parents[rx] = ry
            self._sizes[ry] += self._sizes[rx]
            
            self._weights[rx] = -w + self._weights[y] - self._weights[x]
            if self._ranks[rx] == self._ranks[ry]:
                self._ranks[ry] += 1

    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        root = self.find(self._parents[x])
        self._weights[x] += self._weights[self._parents[x]]
        self._parents[x] = root
        return root

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]

    def weight(self, x):
        """
        :param x:
        :return:
        """
        
        self.find(x)
        return self._weights[x]

    def diff(self, x, y):
        """
        (y の重み) - (x の重み)
        :param x:
        :param y:
        :return:
        """
        if self.find(x) == self.find(y):
            return self._weights[y] - self._weights[x]
        return float("inf")


N = int(sys.stdin.readline())
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

yx = defaultdict(lambda: set())
xy = defaultdict(lambda: set())
for x, y in zip(X, Y):
    xy[x].add(y)
    yx[y].add(x)


uf = UnionFind(size=10 ** 5 + 1)
for ys in xy.values():
    yli = list(ys)
    for y1, y2 in zip(yli[1:], yli[:-1]):
        uf.unite(y1, y2)


yx2 = defaultdict(lambda: set())
for y, xs in yx.items():
    root = uf.find(y)
    yx2[root] |= xs


ans = 0
for y, xs in yx2.items():
    ans += uf.size(y) * len(xs)

ans -= N
print(ans)