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
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    edges = defaultdict(list)
    for _ in range(N):
        x, y = LI()
        edges[x].append(-y)
        edges[-y].append(x)
    visited = defaultdict(int)
    if max(len(li) for li in edges.values()) == 2 and N >= 10 ** 4:
        m, p = 0, 0
        for k in edges.keys():
            if k < 0:
                m += 1
            else:
                p += 1
        return m * p - N
    def solve(v):
        visited[v] = 1
        ret = [v]
        for u in edges[v]:
            if not visited[u]:
                ret += solve(u)
        return ret
    ans = -N
    for node in edges:
        if not visited[node]:
            li = solve(node)
            m, p = 0, 0
            for z in li:
                if z < 0:
                    m += 1
                else:
                    p += 1
            ans += m * p
    return ans

print(main())

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

class UnionFind():
    def __init__(self, N):
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

N = int(input())
uf = UnionFind(N)
x_dict={}
y_dict={}

xy = []
for i in range(N):
    x,y = map(int,input().split())
    if x in x_dict:
        uf.unite(i,x_dict[x])
    else:
        x_dict[x]=i
    if y in y_dict:
        uf.unite(i,y_dict[y])
    else:
        y_dict[y]=i
    xy.append((x,y))
unite_dict={}
for i in range(N):
    ur = uf.find(i)
    unite_dict.setdefault(ur,[set(),set()])
    unite_dict[ur][0].add(xy[i][0])
    unite_dict[ur][1].add(xy[i][1])

p = 0
for k,v in unite_dict.items():
    p +=len(v[0])*len(v[1])
print(p-N)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx == gy != 0:
            continue
        elif gx != 0 and gy != 0:  
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        nx = sum(xy > 0 for xy in xys)
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx == gy != 0:
            continue
        elif gx != 0 and gy != 0:  
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        nx = sum(xy > 0 for xy in xys)
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != 0 and gy != 0:  
            if gx == gy:
                continue
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        nx = sum(xy > 0 for xy in xys)
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for _ in range(N):
        x, y = LI()
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != 0 and gy != 0:  
            if gx == gy:
                continue
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        nx = sum(xy > 0 for xy in xys)
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != 0 and gy != 0 and gx != gy:  
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        nx = sum(xy > 0 for xy in xys)
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != 0 and gy != 0 and gx != gy:  
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        nx = len([1 for xy in xys if xy > 0])
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != 0 and gy != 0 and gx != gy:  
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        nx = sum(1 for xy in xys if xy > 0)
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != 0 and gy != 0:  
            if gx == gy:
                continue
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        m, p = 0, 0
        for xy in xys:
            if xy < 0:
                m += 1
            else:
                p += 1
        ans += m * p
    return ans

print(main())

Solution (Python):
import numpy as np
from scipy.sparse import *
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 numpy as np
from scipy.sparse import *

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

graph = csr_matrix(([1]*N, (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 numpy as np
from scipy.sparse import *

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):



class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1]*n 

    def root(self, x): 
        while self.parent[x] != x:
            x, self.parent[x] = self.parent[x], self.parent[self.parent[x]]
        return x 
 
    def merge(self, x, y): 
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]: 
            self.size[y] += self.size[x] 
            self.parent[x] = y 
        else:
            self.size[x] += self.size[y] 
            self.parent[y] = x 
        return True
 
    def issame(self, x, y): 
        return self.root(x) == self.root(y)
        
    def size(self,x): 
        return self.size[self.root(x)]

n = int(input())
xy = [[int(i) for i in input().split()] for j in range(n)] 

UF = UnionFind(n)

xval = dict()
yval = dict()
for i,(x,y) in enumerate(xy):
    if y in yval:
        UF.merge(i,yval[y])
    else:
        yval[y] = i

    if x in xval:
        UF.merge(i,xval[x])
    else:
        xval[x] = i


xcon = dict()
ycon = dict()
for i in range(n):
    pi = UF.root(i)
    x,y = xy[i]
    if pi in xcon:
        xcon[pi].add(x)
    else:
        xcon[pi] = {x}

    if pi in ycon:
        ycon[pi].add(y)
    else:
        ycon[pi] = {y}
        

ans = -n

for key, val in xcon.items():
    ans += len(val) * len(ycon[key])




print(ans)

Solution (Python):
from collections import deque

N = int(input())

x_list = [0] * N
y_list = [0] * N

for i in range(N):
    x, y = map(int, input().split())
    x_list[i] = x + 1000000
    y_list[i] = y


G = dict()
for i in range(N):
    x = x_list[i]
    y = y_list[i]
    G[x] = dict()
    G[y] = dict()

for i in range(N):
    x = x_list[i]
    y = y_list[i]
    G[x][y] = 1
    G[y][x] = 1

x_su = list(set(x_list))
Lx = len(x_su)
x_su_ind = dict()
for i in range(Lx):
    x_su_ind[x_su[i]] = i

y_su = list(set(y_list))
Ly = len(y_su)
y_su_ind = dict()
for i in range(Ly):
    y_su_ind[y_su[i]] = i

done_x = [0]*Lx
done_y = [0]*Ly

res = 0

id_0 = 0
while True:
    while done_x[id_0] == 1:
        id_0 += 1
        if id_0 == Lx:
            break
    if id_0 == Lx:
        break
    
    cx = 1
    cy = 0
    queue = deque([x_su[id_0]])
    done_x[id_0] = 1
    while len(queue) > 0:
        p = queue.popleft()
        for q in G[p].keys():
            if q < 1000000:
                if done_y[y_su_ind[q]] == 0:
                    queue.append(q)
                    done_y[y_su_ind[q]] = 1
                    cy += 1
            else:
                if done_x[x_su_ind[q]] == 0:
                    queue.append(q)
                    done_x[x_su_ind[q]] = 1
                    cx += 1
    res += cx * cy

print(res - N)

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

def find_root(root, size, x):
    y = root[x]
    if y is None:
        root[x] = x
        size[x] = 1
        return x
    if x == y:
        return y
    z = find_root(root, size, y)
    root[x] = z
    return z


def merge(root, size, cnt, x, y):
    rx = find_root(root, size, x)
    ry = find_root(root, size, y)
    if rx == ry:
        return
    sx = size[rx]
    sy = size[ry]
    if sx > sy:
        root[ry] = rx
        size[rx] += sy
        cnt[rx] += cnt[ry]
    else:
        root[rx] = ry
        size[ry] += sx
        cnt[ry] += cnt[rx]
    return


def main():
    N = int(input())
    U = 10 ** 5
    root_x = [None] * (U + 1)
    root_y = [None] * (U + 1)
    size_x = [0] * (U + 1)
    size_y = [0] * (U + 1)
    cnt_x = [0] * (U + 1)
    cnt_y = [0] * (U + 1)
    x_to_y = [None] * (U + 1)
    y_to_x = [None] * (U + 1)

    for _ in range(N):
        x, y = map(int, input().split())
        rx = find_root(root_x, size_x, x)
        ry = find_root(root_y, size_y, y)
        cnt_x[rx] += 1
        cnt_y[ry] += 1
        if x_to_y[rx] is None:
            x_to_y[rx] = ry
        if y_to_x[ry] is None:
            y_to_x[ry] = rx
        merge(root_y, size_y, cnt_y, x_to_y[rx], ry)
        merge(root_x, size_x, cnt_x, y_to_x[ry], rx)
        x_to_y[root_x[rx]] = root_y[ry]
        y_to_x[root_y[ry]] = root_x[rx]

    ans = 0
    for x in range(1, U + 1):
        if root_x[x] is None:
            continue
        rx = find_root(root_x, size_x, x)
        if x != rx:
            continue
        y = x_to_y[x]
        ry = find_root(root_y, size_y, y)
        sx = size_x[rx]
        sy = size_y[ry]
        cnt = cnt_x[rx]
        ans += sx * sy - cnt
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    s = S()
    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            print("Bad")
            quit()
    print("Good")
    return


def B():
    n,l = LI()
    a = [i+l for i in range(n)]
    ans = sum(a)
    m = n+l-1
    for i in a[::-1]:
        if i < 0:break
        m = min(m,i)
    ans -= m
    print(ans)
    return


def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
def C():
    a,b,c,d = LI()
    g = gcd(c,d)
    l = c*d//g
    sc = b//c-(a-1)//c
    sd = b//d-(a-1)//d
    sl = b//l-(a-1)//l
    print(b-a+1-sc-sd+sl)
    return


def D():
    n = I()
    w = LIR(n)
    w.sort(key = lambda x: x[1])
    t = 0
    for a,b in w:
        if t+a > b:
            print("No")
            quit()
        t += a
    print("Yes")
    return


def E():
    n,k = LI()
    if k == 0:
        m = (n*(n-1))//2
        print(m)
        for i in range(1,n+1):
            for j in range(i+1,n+1):
                print(i,j)
    else:
        if k > ((n-1)*(n-2))//2:
            print(-1)
        else:
            ans = []
            for i in range(2,n+1):
                ans.append((1,i))
            m = ((n-1)*(n-2))//2
            for i in range(2,n+1):
                for j in range(i+1,n+1):
                    if m == k:break
                    ans.append((i,j))
                    m -= 1
                if m == k:break
            print(len(ans))
            for i,j in ans:
                print(i,j)
    return


def F():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]
    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    n = I()
    v = defaultdict(list)
    h = defaultdict(list)
    par = defaultdict(int)
    rank = defaultdict(int)
    for i in range(n):
        a,b = LI()
        v[a].append(b)
        h[b].append(a)
        par[a] = a
        rank[a] = 0
    h = h.values()
    for l in h:
        for i in range(len(l)-1):
            x = l[i]
            y = l[i+1]
            if root(x) != root(y):
                unite(x,y)
    h = defaultdict(list)
    for i in par.keys():
        par[i] = root(par[i])
        h[par[i]].append(i)
    h = h.values()
    ans = 0
    for k in h:
        f = defaultdict(lambda : 0)
        m = 0
        for i in k:
            for j in v[i]:
                if not f[j]:
                    m += 1
                    f[j] = 1
        for i in k:
            ans += m-len(v[i])
    print(ans)
    return


if __name__ == "__main__":
    F()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    s = S()
    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            print("Bad")
            quit()
    print("Good")
    return


def B():
    n,l = LI()
    a = [i+l for i in range(n)]
    ans = sum(a)
    m = n+l-1
    for i in a[::-1]:
        if i < 0:break
        m = min(m,i)
    ans -= m
    print(ans)
    return


def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
def C():
    a,b,c,d = LI()
    g = gcd(c,d)
    l = c*d//g
    sc = b//c-(a-1)//c
    sd = b//d-(a-1)//d
    sl = b//l-(a-1)//l
    print(b-a+1-sc-sd+sl)
    return


def D():
    n = I()
    w = LIR(n)
    w.sort(key = lambda x: x[1])
    t = 0
    for a,b in w:
        if t+a > b:
            print("No")
            quit()
        t += a
    print("Yes")
    return


def E():
    n,k = LI()
    if k == 0:
        m = (n*(n-1))//2
        print(m)
        for i in range(1,n+1):
            for j in range(i+1,n+1):
                print(i,j)
    else:
        if k > ((n-1)*(n-2))//2:
            print(-1)
        else:
            ans = []
            for i in range(2,n+1):
                ans.append((1,i))
            m = ((n-1)*(n-2))//2
            for i in range(2,n+1):
                for j in range(i+1,n+1):
                    if m == k:break
                    ans.append((i,j))
                    m -= 1
                if m == k:break
            print(len(ans))
            for i,j in ans:
                print(i,j)
    return


def F():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]
    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    n = I()
    v = defaultdict(list)
    h = defaultdict(list)
    par = defaultdict(int)
    rank = defaultdict(int)
    for i in range(n):
        a,b = LI()
        v[a].append(b)
        h[b].append(a)
        par[a] = a
        rank[a] = 0
    h = h.values()
    for l in h:
        for i in range(len(l)-1):
            x = l[i]
            y = l[i+1]
            if root(x) != root(y):
                unite(x,y)
    h = defaultdict(list)
    for i in par.keys():
        par[i] = root(par[i])
        h[par[i]].append(i)
    h = h.values()
    ans = 0
    for k in h:
        f = defaultdict(lambda : 0)
        m = 0
        for i in k:
            for j in v[i]:
                if not f[j]:
                    m += 1
                    f[j] = 1
        for i in k:
            ans += m-len(v[i])
    print(ans)
    return


if __name__ == "__main__":
    F()

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

def find_root(root, size, x):
    y = root[x]
    if y is None:
        root[x] = x
        size[x] = 1
        return x
    if x == y:
        return y
    z = find_root(root, size, y)
    root[x] = z
    return z


def merge(root, size, cnt, x, y):
    rx = find_root(root, size, x)
    ry = find_root(root, size, y)
    if rx == ry:
        return
    sx = size[rx]
    sy = size[ry]
    if sx > sy:
        root[ry] = rx
        size[rx] += sy
        cnt[rx] += cnt[ry]
    else:
        root[rx] = ry
        size[ry] += sx
        cnt[ry] += cnt[rx]
    return


def main():
    N = int(input())
    U = 10 ** 5
    root_x = [None] * (U + 1)
    root_y = [None] * (U + 1)
    size_x = [0] * (U + 1)
    size_y = [0] * (U + 1)
    cnt_x = [0] * (U + 1)
    cnt_y = [0] * (U + 1)
    x_to_y = [None] * (U + 1)
    y_to_x = [None] * (U + 1)

    for _ in range(N):
        x, y = map(int, input().split())
        rx = find_root(root_x, size_x, x)
        ry = find_root(root_y, size_y, y)
        cnt_x[rx] += 1
        cnt_y[ry] += 1
        if x_to_y[rx] is None:
            x_to_y[rx] = ry
        if y_to_x[ry] is None:
            y_to_x[ry] = rx
        merge(root_y, size_y, cnt_y, x_to_y[rx], ry)
        merge(root_x, size_x, cnt_x, y_to_x[ry], rx)
        x_to_y[root_x[rx]] = root_y[ry]
        y_to_x[root_y[ry]] = root_x[rx]

    ans = 0
    for x in range(1, U + 1):
        if root_x[x] is None:
            continue
        rx = find_root(root_x, size_x, x)
        if x != rx:
            continue
        y = x_to_y[x]
        ry = find_root(root_y, size_y, y)
        sx = size_x[rx]
        sy = size_y[ry]
        cnt = cnt_x[rx]
        ans += sx * sy - cnt
    print(ans)


if __name__ == "__main__":
    main()