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):
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'
    
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase

read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()









show_flg=False
show_flg=True

ans=0


n=I()
g=defaultdict(list)
a=set()

for i in range(n):
    s,t=LI()
    g[-s].append(t)
    g[t].append(-s)
    a.add(-s)
    a.add(t)

cn=[]
v={i:0 for i in a}
for i in a:
    if v[i]:
        continue
    x,y=0,0
    
    v[i]=1
    q=[i]
    while q:
        c=q.pop()
        if c<0:
            x+=1
        else:
            y+=1
        for nb in g[c]:
            if v[nb]==0:
                v[nb]=1
                q.append(nb)
    cn+=(x,y),

ans=sum(i*j for i,j in cn)-n
print(ans)

Solution (Python):
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'
    
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase

read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()









show_flg=False
show_flg=True

ans=0

n=I()
g=defaultdict(list)
a=set()

for i in range(n):
    s,t=LI()
    g[-s].append(t)
    g[t].append(-s)
    a.add(-s)
    a.add(t)

cn=[]
v={i:0 for i in a}
for i in a:
    if v[i]:
        continue
    x,y=0,0
    
    if i<0:
        x+=1
    else:
        y+=1
    
    v[i]=1
    q=[i]
    while q:
        c=q.pop()
        for nb in g[c]:
            if v[nb]==0:
                v[nb]=1
                q.append(nb)
                if nb<0:
                    x+=1
                else:
                    y+=1
    cn+=(x,y),

ans=sum(i*j for i,j in cn)-n
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
M = 10**5

n = int(input())
G = [[] for _ in range(2*M+1)]
for _ in range(n):
  x, y = map(int, input().split())
  G[x].append(y+M)
  G[y+M].append(x)
seen = [False]*(2*M+1)
def dfs(v):
  stack = [v]
  seen[v] = True
  cnt_x, cnt_y = 0, 0
  while stack:
    v = stack.pop()
    if v <= M:
      cnt_x += 1
    else:
      cnt_y += 1
    for nv in G[v]:
      if seen[nv]:
        continue
      seen[nv] = True
      stack.append(nv)
  return cnt_x*cnt_y
ans = 0
for i in range(2*M+1):
  if not seen[i]:
    ans += dfs(i)
ans -= n
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
M = 10**5

n = int(input())
G = [[] for _ in range(2*M+1)]
for _ in range(n):
  x, y = map(int, input().split())
  G[x].append(y+M)
  G[y+M].append(x)
seen = [False]*(2*M+1)
def dfs(v):
  stack = [v]
  seen[v] = True
  cnt_x, cnt_y = 0, 0
  while stack:
    v = stack.pop()
    if v <= M:
      cnt_x += 1
    else:
      cnt_y += 1
    for nv in G[v]:
      if seen[nv]:
        continue
      seen[nv] = True
      stack.append(nv)
  return cnt_x*cnt_y
ans = 0
for i in range(2*M+1):
  if not seen[i]:
    ans += dfs(i)
ans -= n
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        重いかも！　　members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        重いかも！　all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        def find(self, x):
            
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.parents[x] > self.parents[y]:
                x, y = y, x

            self.parents[x] += self.parents[y]
            self.parents[y] = x

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

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

        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
        
    

    """
    解説放送のように，グラフを考える．
    X座標を表す点を10**5個
    Y座標を表す点を10**5個用意．
    座標を点，点をグラフの辺として表す
    """

    N=I()
    M=10**5
    XY=[0]*(2*M)
    uf=UnionFind(2*M)
    for i in range(N):
        x,y=MI()
        x-=1
        y-=1
        y+=M
        XY[x]+=1
        XY[y]+=1
        uf.union(x,y)
    
    
    from collections import defaultdict
    ddx = defaultdict(int)
    ddy = defaultdict(int)
    dde = defaultdict(int)
    
    for i in range(2*M):
        root=uf.find(i)
        if i<M:
            ddx[root]+=1
        else:
            ddy[root]+=1
        dde[root]+=XY[i]
        
    ans=0
    
    for k,v in dde.items():
        temp=ddx[k]*ddy[k]-v//2
        ans+=temp
        
    print(ans)
    
    
    

main()

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N = ri()
to = defaultdict(list)
V = 100005
X = []
for i in range(N):
	x, y = rl()
	X.append(x)
	y += V
	to[x].append(y)
	to[y].append(x)

visited = set()
nx, ny = 0, 0
def dfs(n):
	global nx, ny
	if n in visited: return
	visited.add(n)
	if n < V:
		nx += 1
	else:
		ny += 1
	for m in to[n]:
		dfs(m)

ans = 0
for x in X:
	if x in visited: continue
	nx, ny = 0, 0
	dfs(x)
	ans += nx*ny
print(ans-N)

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter




input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N = ri()
to = defaultdict(list)
V = 100005
X = []
for i in range(N):
	x, y = rl()
	X.append(x)
	y += V
	to[x].append(y)
	to[y].append(x)

ans = 0
visited = {}
for x in X:
	if x in visited: continue
	nx, ny = 0, 0
	queue = deque()
	queue.append(x)
	visited[x] = 1
	while queue:
		n = queue.pop()
		if n < V:
			nx += 1
		else:
			ny += 1
		for m in to[n]:
			if m in visited:
				continue
			visited[m] = 1
			queue.append(m)
	ans += nx*ny
print(ans-N)

Solution (Python):
N = int(input())

X = [[] for _ in range(10**5)]
Y = [[] for _ in range(10**5)]

P = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

for i in range(N):
    x, y = P[i]
    X[x].append(y)
    Y[y].append(x)

x_used = [0 for _ in range(10**5)]
y_used = [0 for _ in range(10**5)]
res = 0

for i in range(10**5):
    if x_used[i]:
        continue
    stack = [(0, i)]
    x_cnt = 1
    x_used[i] = 1
    y_cnt = 0
    edge = 0
    while stack:
        axis, node = stack.pop()
        if axis == 0:
            for adj in X[node]:
                edge += 1
                if y_used[adj]:
                    continue
                y_cnt += 1
                y_used[adj] = 1
                stack.append((1, adj))
        else:
            for adj in Y[node]:
                if x_used[adj]:
                    continue
                x_cnt += 1
                x_used[adj] = 1
                stack.append((0, adj))
    res += x_cnt * y_cnt - edge

print(res)

Solution (Python):
N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

M = 10**5
uf = UnionFind(2*M)
for x,y in XY:
    a,b = x-1,y-1+M
    if uf.is_same(a,b): continue
    uf.unite(a,b)
for i in range(2*M):
    uf.root(i)

rt = []
for i in range(2*M):
    rt.append(uf.root(i))
from collections import Counter
xr = Counter(rt[:M])
yr = Counter(rt[M:])

ans = 0
for k,v in xr.items():
    ans += yr[k] * v
ans -= N
print(ans)

Solution (Python):
from collections import defaultdict
def solve(points):
    N = len(points)
    X = defaultdict(list)
    Y = defaultdict(list)

    for i,(x,y) in enumerate(points):
        X[x].append(i)
        Y[y].append(i)
    
    res = 0
    visited = [False]*N
    for p0 in range(N):
        if visited[p0]:
            continue
        stack = [p0]
        visited[p0] = True
        xx = set()
        yy = set()
        while stack:
            p = stack.pop()
            x,y = points[p]
            xx.add(x)
            yy.add(y)

            for q in X[x]:
                if not visited[q]:
                    visited[q] = True
                    stack.append(q)
            for q in Y[y]:
                if not visited[q]:
                    visited[q] = True
                    stack.append(q)
        res += len(xx)*len(yy)
    return res-N




if __name__ == '__main__':
    N = int(input())
    points = [tuple(map(int,input().split())) for _ in range(N)]
    print(solve(points))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

n = int(input())
edges = [[] for i in range(2*10**5)]
for i in range(n):
    xi, yi = map(int, input().split())
    xi -= 1
    yi = yi - 1 + 10**5
    edges[xi].append(yi)
    edges[yi].append(xi)

already = set([])
def dfs(x, y, node):
    if node in already:
        return x, y
    if node < 10**5:
        x += 1
    else:
        y += 1
    already.add(node)
    for next_node in edges[node]:
        x, y = dfs(x, y, next_node)
    return x, y

num = 0
for i in range(10**5):
    x, y = dfs(0, 0, i)
    num += x * y
print(num-n)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
xy=[list(map(int,input().split())) for i in range(n)]

dic={}
for i in range(n):
    x,y=xy[i]
    if (0,x) in dic:
        dic[(0,x)].append(y)
    else:
        dic[(0,x)]=[y]
    x,y=y,x
    if (1,x) in dic:
        dic[(1,x)].append(y)
    else:
        dic[(1,x)]=[y]


lst=[[0]*(10**5+1) for i in range(2)]

ans=0
for x,y in xy:
    if lst[0][x]==1:
        continue
    lst[0][x]=1
    d=deque([(0,x)])
    xcnt,ycnt=0,0
    cnt=0
    while d:
        
        now=d.popleft()
        if now[0]==0:
            xcnt+=1
        else:
            ycnt+=1
        for j in dic[now]:
            cnt+=1
            if lst[1-now[0]][j]==0:
                lst[1-now[0]][j]=1
                d.append((1-now[0],j))
    
    ans+=xcnt*ycnt-cnt//2
print(ans)

Solution (Python):
from collections import deque
N = int(input())
V = set()
E = {}

for _ in range(N):
  x,y = map(int, input().split())
  y += 100010
  V.add(x)
  V.add(y)
  if x not in E:
    E[x] = [y]
  else:
    E[x].append(y)
  if y not in E:
    E[y] = [x]
  else:
    E[y].append(x)




visited = [ False ] * 200020
willSearch = [ False ] * 200020
Q = deque()
ans = 0
for v in V:
  if visited[v]:
    continue

  Q.append(v)
  xcount, ycount = 0,0
  edge_count = 0
  while len(Q) > 0:
    now = Q.pop()
    visited[now] = True

    if now > 100005:
      ycount += 1
    else:
      xcount += 1
      
    for nxt in E[now]:
      edge_count += 1
      if visited[nxt] or willSearch[nxt]:
        continue
      

      willSearch[nxt] = True

      Q.append(nxt)
  
  ans += xcount * ycount
  ans -= edge_count // 2
  
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

def dfs(G, F, crr, pre, ret, st):
    F[crr] = False
    if crr < 10**5:
        ret[0] += 1
    else:
        ret[1] += 1
    for nxt in G[crr]:
        if nxt == pre:
            continue
        p, q = crr, nxt
        if q < p:
            p, q = q, p
        if not (p, q) in st:
            st.add((p, q))
            ret[2] += 1
        if F[nxt]:
            dfs(G, F, nxt, crr, ret, st)

def main():
    n = int(input())
    G = [[] for _ in range(2 * 10**5)]
    for _ in range(n):
        x, y = map(int, input().split())
        x, y = x-1, y-1 + 10**5
        G[x].append(y)
        G[y].append(x)
    F = [True]*(2* 10**5)
    ans = 0
    st = set()
    for i in range(2 * 10**5):
        if F[i] and len(G[i]) > 0:
            tmp = [0]*3
            dfs(G, F, i, -1, tmp, st)
            ans += tmp[0] * tmp[1] - tmp[2]
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n + 1) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N = int(input())
U = UnionFind(2*10**5)
for i in range(N):
    x, y = map(int, input().split())
    U.union(x, y+10**5)
ans = 0
Roots = U.roots()
D = {x: [] for x in Roots}
for i in range(2*10**5+1):
    D[U.find(i)].append(i)
for x in Roots:
    ss = D[x]
    sx = 0
    sy = 0
    for c in ss:
        if c <= 10**5:
            sx += 1
        else:
            sy += 1
    ans += sx*sy
ans -= N
print(ans)

Solution (Python):

from collections import defaultdict


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n + 1) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N = int(input())
U = UnionFind(2*10**5)
for i in range(N):
    x, y = map(int, input().split())
    U.union(x, y+10**5)
ans = 0
Roots = U.roots()
D = {x: [] for x in Roots}
for i in range(2*10**5+1):
    D[U.find(i)].append(i)
for x in Roots:
    ss = D[x]
    sx = 0
    sy = 0
    for c in ss:
        if c <= 10**5:
            sx += 1
        else:
            sy += 1
    ans += sx*sy
ans -= N
print(ans)

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
n = int(input())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
unionfind = UnionFind(n)
x_d = defaultdict(set)
y_d = defaultdict(set)
for i in range(n):
    x_d[data[i][0]].add(i)
    y_d[data[i][1]].add(i)

for i in range(n):
    x, y = data[i]
    if len(x_d[x]) > 1 and len(y_d[y]) > 1:
        for j in x_d[x]:
            unionfind.union(i, j)
        for j in y_d[y]:
            unionfind.union(i, j)

point = [[] for i in range(n)]
for i in range(n):
    if unionfind.size(i) <= 2:
        continue
    else:
        point[unionfind.find(i)].append(i)
ans = 0
for i in range(n):
    if len(point[i]) > 2 :
        x_s = set()
        y_s = set()
        for j in point[i]:
            x, y = data[j]
            x_s.add(x)
            y_s.add(y)
        ans += len(x_s) * len(y_s) - len(point[i])
print(ans)

Solution (Python):
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    
    
    def bfs(V,used,s=0):
        W = {}
        W[s] = 1
        que = deque([s])
        while(que):
            now = que.pop()
            used[now] = True
            ne = W[now]*(-1)
            for v in V[now]:
                if v not in W:
                    W[v] = ne
                    que.append(v)
                elif W[v]!=ne:
                    return False
        return W,used
    y_shift = 10**5 + 1
    N = I()
    V = defaultdict(set)
    for _ in range(N):
        x, y = LI()
        y += y_shift
        V[x].add(y)
        V[y].add(x)

    ans = 0
    used = defaultdict(lambda:False)
    for i in V.keys():
        if used[i]:
            continue
        W,used = bfs(V,used,i)
        x = 0
        for w in W.values():
            if w==1:
                x += 1
        y = len(W)-x
        
        ans += x*y
    ans = max(0,ans-N)
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    MAXS = 100005
    N = int(input())
    X = [set() for _ in range(MAXS)]
    Y = [set() for _ in range(MAXS)]
    for _ in range(N):
        x,y = map(int,input().split())
        X[x].add(y)
        Y[y].add(x)
    
    used_x = [0] * MAXS
    used_y = [0] * MAXS
    ans = -N
    for i in range(MAXS):
        if used_x[i]:
            continue
        used_x[i] = 1
        if not X[i]:
            continue
        max_height = set(X[i])
        max_width = {i}
        stack = [(i,0)]
        while stack:
            v,typ = stack.pop()
            if typ == 0:
                for y in X[v]:
                    if used_y[y]:
                        continue
                    used_y[y] = 1
                    if Y[y]:
                        max_width |= Y[y]
                        stack.append((y,1))
            else:
                for x in Y[v]:
                    if used_x[x]:
                        continue
                    used_x[x] = 1
                    if X[x]:
                        max_height |= X[x]
                        stack.append((x,0))
        ans += len(max_width) * len(max_height)
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):

import sys
from itertools import product
sys.setrecursionlimit(10**8)


INF = float("inf")


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def compress(X, Y):
    dx = list(sorted(set(X)))
    dx_inv = {x: i for i, x in enumerate(dx)}
    dy = list(sorted(set(Y)))
    dy_inv = {y: i for i, y in enumerate(dy)}
    return (dx, dy), (dx_inv, dy_inv)


def main():
    N = int(input())
    X = [0]*N
    Y = [0]*N
    for i in range(N):
        X[i], Y[i] = map(int, input().split())

    (decx, decy), (encx, ency) = compress(X, Y)

    H = len(decx)
    uf = UnionFind(len(decx) + len(decy))

    for i in range(N):
        x, y = encx[X[i]], ency[Y[i]]+H
        
        uf.union(x, y)

    dx = {}
    for i in range(len(decx)):
        key = uf.find(i)
        if key not in dx:
            dx[key] = 1
        else:
            dx[key] += 1
    dy = {}
    for i in range(H, H+len(decy)):
        key = uf.find(i)
        if key not in dy:
            dy[key] = 1
        else:
            dy[key] += 1
    
    
    ans = 0
    for key in dx:
        if key in dy:
            ans += dy[key]*dx[key]
    print(ans-N)
    return


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
D = 100000
d = {i:[] for i in range(1, 2*D+1)}
cd = set()
used = [0]*(2*D+1)
ans = 0

for _ in range(N):
    x, y = map(int, input().split())
    y += D
    cd.add(x)
    d[x].append(y)
    d[y].append(x)

for x in cd:
    if used[x]:continue
    q = [x]
    used[x] = 1
    cx, sx = 0, 0

    while q:
        a = q.pop()
        if a<=D:
            cx += 1
        sx += 1
        for b in d[a]:
            if used[b]:continue
            used[b] = 1
            q.append(b)
    ans += cx*(sx-cx)

print(ans-N)

Solution (Python):
from collections import defaultdict

N = int(input())
d = defaultdict(list)
cd = set()
D = 100000
used = [0]*(2*D+1)
ans = 0

for _ in range(N):
    x, y = map(int, input().split())
    y += D
    cd.add(x)
    d[x].append(y)
    d[y].append(x)

for x in cd:
    if used[x]:continue
    q = [x]
    used[x] = 1
    cx, sx = 0, 0

    while q:
        a = q.pop()
        if a<=D:
            cx += 1
        sx += 1
        for b in d[a]:
            if used[b]:continue
            used[b] = 1
            q.append(b)
    ans += cx*(sx-cx)

print(ans-N)