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.



Sample input:
3
1 1
5 1
5 5


Sample output:
1

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(int(1e9))

class UnionFind():
  def __init__(self):
    self.roots = {}
    self.nums = {}

  def find_root(self, a):
    if a not in self.roots:
      self.nums[a] = 1
      return a
    else:
      self.roots[a] = self.find_root(self.roots[a])
      return self.roots[a]

  def unite(self, a, b):
    root_a = self.find_root(a)
    root_b = self.find_root(b)
    n_a = self.nums[root_a]
    n_b = self.nums[root_b]
    if root_a == root_b:
      return
    else:
      if n_a > n_b: #多い方に合流させる
        self.roots[root_b] = root_a
        self.nums[root_a] = n_a + n_b
        del self.nums[root_b]
      else:
        self.roots[root_a] = root_b
        self.nums[root_b] = n_a + n_b
        del self.nums[root_a]
      return
  
  def is_union(self, a,b):
    return self.find_root(a) == self.find_root(b)
  
  
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

uf = UnionFind()
sq = {}

X = [None] * (10**5 + 1)
Y = [None] * (10**5 + 1)

ans = 0

for i in range(N):
  (x,y) = XY[i]
  if X[x] is None and Y[y] is None:
    uf.find_root(i) # rootに加えておく、不要かも
    ans += 0
    X[x] = i
    Y[y] = i
    sq[i] = (1,1)
    
  elif Y[y] is None:
    Y[y] = X[x]
    root = uf.find_root(X[x])
    root_nx, root_ny = sq[root]
    ans += root_ny -1
    sq[root] = (root_nx+1, root_ny)
    
  elif X[x] is None:
    X[x] = Y[y]
    root = uf.find_root(Y[y])
    root_nx, root_ny = sq[root]
    ans += root_nx -1
    sq[root] = (root_nx, root_ny+1)
    
  elif X[x] == Y[y]:
    ans -= 1
    
  else: #X[x] != Y[y]
    x_root = uf.find_root(X[x])
    y_root = uf.find_root(Y[y])
    uf.unite(X[x], Y[y])
    new_root = uf.find_root(X[x])
    
    x_root_nx, x_root_ny = sq[x_root]
    y_root_nx, y_root_ny = sq[y_root]
    sq[new_root] = (x_root_nx + y_root_nx, x_root_ny + y_root_ny)
    
    ans += (x_root_nx + y_root_nx)*(x_root_ny + y_root_ny)
    ans -= x_root_nx * x_root_ny
    ans -= y_root_nx * y_root_ny
    ans -= 1
    
    # X,Yは不変
    
print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
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

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

#B
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

#C
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

#D
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

#E
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

#F
def F():
    n = I()
    v = defaultdict(list)
    h = defaultdict(list)
    for i in range(n):
        a,b = LI()
        v[a].append(b)
        h[b].append(a)
    h = h.values()
    ans = 0
    for k in h:
        f = defaultdict(int)
        for i in k:
            for j in v[i]:
                f[j] += 1
        f = f.values()
        m = max(f)
        for i in f:
            ans += m-i
    print(ans)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Wrong Answer

Solution code:
def sol():
    n=int(input())
    t=100001
    d=[0]*t
    for i in range(n):
        a,b=map(int,input().split())
        d[b]+=1
    ans=0
    for i in d:
        p=max(i-1,0)
        ans+=p*p
    print(ans)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(int(1e9))

class UnionFind():
  def __init__(self):
    self.roots = {}
    self.nums = {}

  def find_root(self, a):
    if a not in self.roots:
      self.nums[a] = 1
      return a
    else:
      self.roots[a] = self.find_root(self.roots[a])
      return self.roots[a]

  def unite(self, a, b):
    root_a = self.find_root(a)
    root_b = self.find_root(b)
    n_a = self.nums[root_a]
    n_b = self.nums[root_b]
    if root_a == root_b:
      return
    else:
      if n_a > n_b: #多い方に合流させる
        self.roots[root_b] = root_a
        self.nums[root_a] = n_a + n_b
        del self.nums[root_b]
      else:
        self.roots[root_a] = root_b
        self.nums[root_b] = n_a + n_b
        del self.nums[root_a]
      return
  
  def is_union(self, a,b):
    return self.find_root(a) == self.find_root(b)
  
  
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

uf = UnionFind()
sq = {}

X = [None] * (10**5 + 1)
Y = [None] * (10**5 + 1)

ans = 0

for i in range(N):
  (x,y) = XY[i]
  if X[x] is None and Y[y] is None:
    uf.find_root(i) # rootに加えておく、不要かも
    ans += 0
    X[x] = i
    Y[y] = i
    sq[i] = (1,1)
    
  elif Y[y] is None:
    Y[y] = X[x]
    root = uf.find_root(X[x])
    root_nx, root_ny = sq[root]
    ans += root_ny -1
    sq[root] = (root_nx+1, root_ny)
    
  elif X[x] is None:
    X[x] = Y[y]
    root = uf.find_root(Y[y])
    root_nx, root_ny = sq[root]
    ans += root_nx -1
    sq[root] = (root_nx, root_ny+1)
    
  elif X[x] == Y[y]:
    ans -= 1
    
  else: #X[x] != Y[y]
    x_root = uf.find_root(X[x])
    y_root = uf.find_root(Y[y])
    uf.unite(X[x], Y[y])
    new_root = uf.find_root(X[x])
    
    x_root_nx, x_root_ny = sq[x_root]
    y_root_nx, y_root_ny = sq[y_root]
    sq[new_root] = (x_root_nx + y_root_nx + 1, x_root_ny + y_root_ny + 1)
    
    ans += (x_root_nx + y_root_nx)*(x_root_ny + y_root_ny)
    ans -= x_root_nx * x_root_ny
    ans -= y_root_nx * y_root_ny
    ans -= 1
    
    # X,Yは不変
    
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import math


n = int(stdin.readline().rstrip())

m = []

for i in range(n):
    x, y = [int(x) for x in stdin.readline().rstrip().split()]
    m.append((x,y))

m.sort()
#print(m)

ans=0

for x,y in m:
  for x2,y2 in [(x2,y2) for x2,y2 in m if x2==x and y < y2]:
    for x3,y3 in [(x3,y3) for x3,y3 in m if y==y3]:
      if not (x3,y2) in m:
          ans +=1
    for x4,y4 in [(x4,y4) for x4,y4 in m if y2==y4]:
      if not (x4,y) in m:
          ans +=1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
x_set , y_set = set([]), set([])
for i in range(n):
    x, y = [ int(v) for v in input().split() ]
    x_set.add(x)
    y_set.add(y)

lx, ly = len(x_set), len(y_set)



print((n-lx)*(n-ly))

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N = int(input())
points = list()
ans = 0
for _ in range(N):
    points.append(list(map(int, input().split())))

for p1, p2, p3 in combinations(points, 3):
    cnt = 0
    diff_x1 = p1[0] - p2[0]
    diff_y1 = p1[1] - p2[1]
    diff_x2 = p1[0] - p3[0]
    diff_y2 = p1[1] - p3[1]
    diff_x3 = p2[0] - p3[0]
    diff_y3 = p2[1] - p3[1]
    if diff_x1 and not diff_y1 or not diff_x1 and diff_y1:
        cnt += 1
    if diff_x2 and not diff_y2 or not diff_x2 and diff_y2:
        cnt += 1
    if diff_x3 and not diff_y3 or not diff_x3 and diff_y3:
        cnt += 1
    if 2 == cnt:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = {}
Y = {}
P = [False] * N

LX = set()
LY = set()
for n in range(N):
    x, y = map(int, input().split())
    if x in X:
        l = X[x]
        P[l[0][0]] = True
        LX.add(x)
        P[n] = True
        l.append((n, x, y))
    else:
        X[x] = [(n, x, y)]

    if y in Y:
        l = Y[y]
        P[l[0][0]] = True
        LY.add(y)
        P[n] = True
        l.append((n, x, y))
    else:
        Y[y] = [(n, x, y)]


for lx in X.values():
    if len(lx) < 2:
        continue

    for n, x, y in lx:
        LY.add(y)
        ly = Y[y]
        for ny, xy, yy in ly:
            P[ny] = True
            LX.add(xy)

for ly in Y.values():
    if len(ly) < 2:
        continue

    for n, x, y in ly:
        LX.add(x)
        lx = X[x]
        for nx, xx, yx in lx:
            P[nx] = True
            LY.add(yx)

print(len(LX) * len(LY) - P.count(True))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(int(1e9))

class UnionFind():
  def __init__(self):
    self.roots = {}
    self.nums = {}

  def find_root(self, a):
    if a not in self.roots:
      self.nums[a] = 1
      return a
    else:
      self.roots[a] = self.find_root(self.roots[a])
      return self.roots[a]

  def unite(self, a, b):
    root_a = self.find_root(a)
    root_b = self.find_root(b)
    n_a = self.nums[root_a]
    n_b = self.nums[root_b]
    if root_a == root_b:
      return
    else:
      if n_a > n_b: #多い方に合流させる
        self.roots[root_b] = root_a
        self.nums[root_a] = n_a + n_b
        del self.nums[root_b]
      else:
        self.roots[root_a] = root_b
        self.nums[root_b] = n_a + n_b
        del self.nums[root_a]
      return
  
  def is_union(self, a,b):
    return self.find_root(a) == self.find_root(b)
  
  
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

uf = UnionFind()
sq = {}

X = [None] * (10**5 + 1)
Y = [None] * (10**5 + 1)

ans = 0

for i in range(N):
  (x,y) = XY[i]
  if X[x] is None and Y[y] is None:
    uf.find_root(i) # rootに加えておく、不要かも
    ans += 0
    X[x] = i
    Y[y] = i
    sq[i] = (1,1)
    
  elif Y[y] is None:
    Y[y] = X[x]
    root = uf.find_root(X[x])
    root_nx, root_ny = sq[root]
    ans += root_ny -1
    sq[root] = (root_nx+1, root_ny)
    
  elif X[x] is None:
    X[x] = Y[y]
    root = uf.find_root(Y[y])
    root_nx, root_ny = sq[root]
    ans += root_nx -1
    sq[root] = (root_nx, root_ny+1)
    
  elif X[x] == Y[y]:
    ans -= 1
    
  else: #X[x] != Y[y]
    x_root = uf.find_root(X[x])
    y_root = uf.find_root(Y[y])
    uf.unite(X[x], Y[y])
    new_root = uf.find_root(X[x])
    
    x_root_nx, x_root_ny = sq[x_root]
    y_root_nx, y_root_ny = sq[y_root]
    sq[new_root] = (x_root_nx + y_root_nx + 1, x_root_ny + y_root_ny + 1)
    
    ans += (x_root_nx + y_root_nx + 1)*(x_root_ny + y_root_ny + 1)
    ans -= x_root_nx * x_root_ny
    ans -= y_root_nx * y_root_ny
    ans -= 1
    
    # X,Yは不変
    
print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
  N = int(input())
  XY = [[int(i) for i in input().split()] for i in range(N)]
  if N < 3: return 0
  setY = set()
  XYdict = {}
  for x, y in XY:
    setY.add(y)
    if x not in XYdict:
      XYdict[x] = set([y])
    else:
      XYdict[x].add(y)

  ans = 0

  for i in XYdict:
    for j in XYdict:
      if i == j: continue
      xor = XYdict[i] ^ XYdict[j]
      ans += len(xor)
      XYdict[i] |= XYdict[j]
      XYdict[j] |= XYdict[i]

  return ans

print(solve())

Submission status: Wrong Answer

Solution code:
import collections

N = int(input())
point_y_dict = {}
x_list = []
for i in range(N):
    x, y = list(map(int, input().split()))
    x_list.append(x)
    if y in point_y_dict.keys():
        point_y_dict[y].append(x)
    else:
        point_y_dict[y] = [x]

c = collections.Counter(x_list)
x_num = c.most_common()
x_mult = []
for x_n in x_num:
    if x_n[1] > 1:
        x_mult.append(x_n[0])

y_use = 0
x_use = set([])
point_num = 0
for y in point_y_dict.keys():
    if len(set(point_y_dict[y]) & set(x_mult)) > 0:
        y_use += 1
        x_use = x_use | set(point_y_dict[y])
        point_num += len(point_y_dict[y])

print(y_use * len(x_use) - point_num)

Submission status: Wrong Answer

Solution code:
N = int(input())
points = []
for i in range(N):
    points.append([int(i) for i in input().split()])
  
result = 0
for p in points:
    a = len([1 for i in points if i[0] == p[0]]) - 1
    b = len([1 for i in points if i[1] == p[1]]) - 1
    result += a*b
    
print(result)

Submission status: Wrong Answer

Solution code:
import sys
# input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N = int(input())
K = 10**5+1
P = [i for i in range(K)]

def par(a):
    if P[a] == a:
        return a
    t = par(P[a])
    P[a] = t
    return t
def cb(a, b):
    pa = par(a)
    pb = par(b)
    if pa != pb:
        P[pb] = pa

X = [[] for _ in range(10**5+1)]
Y = [[] for _ in range(10**5+1)]
for _ in range(N):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    Y[y-1].append(x-1)
for i in range(len(Y)):
    for j in range(len(Y[i])-1):
        cb(Y[i][j], Y[i][j+1])

M = [[] for _ in range(K)]
for i in range(K):
    M[P[i]].append(i)
ans = -N
for i in range(K):
    S = []
    for j in M[i]:
        for k in X[j]:
            S.append(k)
    S = list(set(S))
    ans += len(S)*len(M[i])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
P=[]
for i in range(N):
  x,y = list(map(int, input().strip().split(' ')))
  P+=[[x,y]]
P1=sorted(P,key=lambda x:(x[0],x[1]))
P2=sorted(P,key=lambda x:(x[1],x[0]))
#print(P,P1,P2)
num=0
for i in range(N):
  for j in range(i,N):
    if P[i][0]==P[j][0]:continue
    if P[i][1]==P[j][1]:continue
    if [P[i][0],P[j][1]] in P:num+=1
    if [P[i][1],P[j][0]] in P:num+=1
print(num)

Submission status: Wrong Answer

Solution code:
n = int(input())
dot = {}
dotset = set()
for i in range(n):
    x, y = map(int, input().split())
    dot[i] = (x, y)
    dotset.add((x, y))

v = set()

cnt = 0
for i, f in dot.items():
    a, b = f
    for j, g in dot.items():
        if i == j: continue
        c, d = g
        if a == c or b == d: continue
        f1 = (a, d) in dotset
        f2 = (c, b) in dotset
        if f1 and not f2:
            cnt += 1
            dotset.add((c, b))
        if not f1 and f2:
            cnt += 1
            dotset.add((a, d))
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
x, y = (
    zip(*(map(int, input().split()) for _ in range(N))) if N else
    ((), ())
)


class UnionFindTree:
    def __init__(self, n):
        self.p = [i for i in range(n + 1)]
        self.r = [1 for _ in range(n + 1)]

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

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.r[px] < self.r[py]:
                self.p[px] = py
                self.r[py] += self.r[px]
            else:
                self.p[py] = px
                self.r[px] += self.r[py]

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


uft = UnionFindTree(10**5)
X = [[] for _ in range(10**5 + 1)]
for a, b in zip(x, y):
    X[a].append(b)
Y = [[] for j in range(10**5 + 1)]
for a, b in zip(x, y):
    Y[b].append(a)
SX = set(x)
SY = set(y)
for j in SY:
    for i in Y[j]:
        uft.union(Y[j][0], i)

X2 = [[] for _ in range(10**5 + 1)]
for i in SX:
    X2[uft.find(i)].append(i)
ans = 0
for i in SX:
    if len(X2[i]) == 1:
        ans += 1
for i in SX:
    S = set()
    if len(X2[i]) >= 2:
        for i2 in X2[i]:
            for j in X[i2]:
                S.add(j)
        ans += len(X2[i]) * len(S)
ans -= N

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
Points = [list(map(int, input().split())) for i in range(N)]

X_dict = {i: [] for i in range(1, 10 ** 5 + 1)}
Y_dict = {i: [] for i in range(1, 10 ** 5 + 1)}
for i, (x, y) in enumerate(Points):
    X_dict[x].append((y, i))
    Y_dict[y].append((x, i))


ans = 0
Visited = [False] * N
for i, (x, y) in enumerate(Points):
    if Visited[i]:
        continue

    stack = [('x', x), ('y', y)]
    cnt = 1
    x_set, y_set = {x}, {y}
    Visited[i] = True
    while stack:
        s, v = stack.pop()
        if s == 'x':
            for yd, j in Y_dict[v]:
                if Visited[j]:
                    continue
                else:
                    cnt += 1
                    y_set.add(yd)
                    stack.append(('y', yd))
                    Visited[j] = True
        else:
            for xd, j in X_dict[v]:
                if Visited[j]:
                    continue
                else:
                    cnt += 1
                    x_set.add(xd)
                    stack.append(('x', xd))
                    Visited[j] = True

    ans += len(x_set) * len(y_set) - cnt

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

x_list = []
x_cnt = 0
y_list = []
y_cnt = 0

for i in range(N):
    X,Y= map(int,input().split())
    if X not in x_list:
        x_list.append(X)
    else:
        x_cnt += 1
    if Y not in y_list:
        y_list.append(Y)
    else:
        y_cnt += 1
ans = (x_cnt+1)*(y_cnt+1)-(x_cnt+y_cnt+1)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
tmp_x = []
tmp_y = []
x_list = []
x2y_dic = {}
y_list = []
y2x_dic = {}
for p in xy:
    if p[0] in tmp_x:
        x_list.append(p[0])
    if p[1] in tmp_y:
        y_list.append(p[1])
    tmp_x.append(p[0])
    tmp_y.append(p[1])
    if p[0] not in x2y_dic:
        x2y_dic[p[0]] = []
    x2y_dic[p[0]].append(p[1])
    if p[1] not in y2x_dic:
        y2x_dic[p[1]] = []
    y2x_dic[p[1]].append(p[0])
cnt = []
ccc = 0
x_list = list(set(x_list))
y_list = list(set(y_list))
for x in x_list:
    for y in y_list:
        if [x,y] in xy:
            for xx in x2y_dic[x]:
                for yy in y2x_dic[y]:
                    if [xx,yy] not in xy and [xx,yy] not in cnt:
                        cnt.append([xx,yy])
                        ccc+=1
print(ccc)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
tmp_x = []
tmp_y = []
x_list = []
x2y_dic = {}
y_list = []
y2x_dic = {}
for p in xy:
    if p[0] in tmp_x:
        x_list.append(p[0])
    if p[1] in tmp_y:
        y_list.append(p[1])
    tmp_x.append(p[0])
    tmp_y.append(p[1])
    if p[0] not in x2y_dic:
        x2y_dic[p[0]] = []
    x2y_dic[p[0]].append(p[1])
    if p[1] not in y2x_dic:
        y2x_dic[p[1]] = []
    y2x_dic[p[1]].append(p[0])
cnt = 0
x_list = list(set(x_list))
y_list = list(set(y_list))
for x in x_list:
    for y in y_list:
        if [x,y] in xy:
            for xx in x2y_dic[x]:
                for yy in y2x_dic[y]:
                    if [xx,yy] not in xy:
                        cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
dot = {}
dotset = set()
for i in range(n):
    x, y = map(int, input().split())
    dot[i] = (x, y)
    dotset.add((x, y))

v = set()
dx = sorted(dot.items(), key=lambda x: x[1][0])
dy = sorted(dot.items(), key=lambda x: x[1][1])
cnt = 0
for i, f in dx:
    a, b = f
    for j, g in dy:
        if i == j: continue
        c, d = g
        if a == c or b == d: continue
        f1 = (a, d) in dotset
        f2 = (c, b) in dotset
        if f1 and not f2:
            cnt += 1
            dotset.add((c, b))
        if not f1 and f2:
            cnt += 1
            dotset.add((a, d))
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = []
for i in range(N):
    xy.append(list(map(int, input().split())))
ans = 0
if N < 3:
    print(ans)
else:
    for i in range(N-1):
        for j in range(i+1, N):
            if xy[i][0] == xy[j][0]:
                for k in range(i+1, N):
                    if j != k and xy[i][1] == xy[k][1]:
                        ans += 1
                    if j != k and xy[j][1] == xy[k][1]:
                        ans += 1
                    
print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
  N = int(input())
  XY = [[int(i) for i in input().split()] for i in range(N)]
  if N < 3: return 0
  setX = set()
  setY = set()
  XYdict = {}
  for x, y in XY:
    setX.add(x)
    setY.add(y)
  return len(setX) * len(setY) - N

print(solve())

Submission status: Wrong Answer

Solution code:
n = int(input())
E = [[int(i) for i in input().split()] for j in range(n)]

X = [set() for i in range(10 ** 5 + 1)]
Y = [set() for i in range(10 ** 5 + 1)]

for x, y in E:
    X[x].add(y)
    Y[y].add(x)

ans = 0

for x in X:
    if len(x) < 2:
        continue
    for a in x:
        for b in Y[a]:
            if len(x) - len(X[b]) > 0:
                ans += len(x) - len(X[b])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N = int(input())
K = 10**5+1
# N = 10
P = [i for i in range(K)]

def par(a):
    if P[a] == a:
        return a
    t = par(P[a])
    P[a] = t
    return t
def cb(a, b):
    P[par(b)] = par(a)

if True:
    X = [[] for _ in range(10**5+1)]
    Y = [[] for _ in range(10**5+1)]
    for _ in range(N):
        x, y = map(int, input().split())
        X[x-1].append(y-1)
        Y[y-1].append(x-1)
else:
    X = [[0, 1, 2, 3, 4], [0], [0], [0], [0], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
    X = [[0], [], [], [], [0, 4], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
    X = [[0, 1, 2, 3], [0], [0, 4], [0], [0], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
    Y = [[0, 1, 2, 3, 4], [0], [0], [0], [2], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
    
    X = [[0, 1, 2, 3], [0], [0, 4], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
    Y = [[0, 1, 2], [0], [0], [0], [2], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]

# print(X[:20])
# print(Y[:20])
for i in range(len(Y)):
    for j in range(len(Y[i])-1):
        # print(Y[i][j], Y[i][j+1])
        cb(Y[i][j], Y[i][j+1])

# print(P)
M = [[] for _ in range(K)]
for i in range(K):
    M[P[i]].append(i)
# print("M =", M)
ans = -N
for i in range(K):
    S = []
    for j in M[i]:
        for k in X[j]:
            S.append(k)
    # print("S1 =", S)
    S = list(set(S))
    # print("S2 =", S)
    ans += len(S)*len(M[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter

n = int(input())

xs = set()
ys = set()
points = set()

for _ in range(n):
    x, y = map(int, input().split())
    points.add((x, y))

cnt_x = Counter([x for x, y in points])
cnt_y = Counter([y for x, y in points])

cx = [x for x, c in cnt_x.items() if c >= 2]
cy = [y for y, c in cnt_y.items() if c >= 2]

grid_x = set()
grid_y = set()

for x, y in points:
    if x in cx or y in cy:
        grid_x.add(x)
        grid_y.add(y)

cnt = 0
for x, y in points:
    if x in grid_x and y in grid_y:
        cnt += 1

print(len(grid_x) * len(grid_y) - cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
tmp_x = []
tmp_y = []
x_list = []
y_list = []
for p in xy:
    if p[0] in tmp_x:
        x_list.append(p[0])
    if p[1] in tmp_y:
        y_list.append(p[1])
    tmp_x.append(p[0])
    tmp_y.append(p[1])
cnt = 0
x_list = Counter(x_list).most_common()
y_list = Counter(y_list).most_common()
for x, cnt_x in x_list:
    for y, cnt_y in y_list:
        if [x,y] in xy:
            cnt+=cnt_x*cnt_y
            
print(cnt)

Submission status: Wrong Answer

Solution code:
N=int(input())
from collections import defaultdict
X=dict()
Y=dict()
P=[]
root=[-1]*N
def find(i):
    global root
    if root[i]>=0:
        root[i]=find(root[i])
        return root[i]
    return i
for i in range(N):
    x,y=map(int,input().split())
    P+=[(x,y)]
    if x not in X.keys():
        rx=i
        X[x]=i
    else:
        rx=find(X[x])
        X[x]=rx
    if y not in Y.keys():
        ry=i
        Y[y]=i
    else:
        ry=find(Y[y])
        Y[y]=ry
    if rx==ry:
        if i!=rx:
            root[i]=rx
        continue
    elif root[rx]<=root[ry]:
        root[rx]+=root[ry]
        root[ry]=rx
    else:
        root[ry]+=root[rx]
        root[rx]=ry
cntx=defaultdict(set)
cnty=defaultdict(set)
RP=set()
ans=0
for i in range(N):
    x,y=P[i]
    r=find(i)
    cntx[r]|={x}
    cnty[r]|={y}
    RP|={r}
for k in RP:
    ans+=len(cntx[k])*len(cnty[k])
print(ans-N)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[]
B=[]
for i in range(N):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
AS=set(A)
BS=set(B)
if N>=3:
    print(len(AS)*len(BS)-N)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N = int(input())
K = 10**5+1
# N = 10
P = [i for i in range(K)]

def par(a):
    if P[a] == a:
        return a
    t = par(P[a])
    P[a] = t
    return t
def cb(a, b):
    P[P[b]] = P[a]

if True:
    X = [[] for _ in range(10**5+1)]
    Y = [[] for _ in range(10**5+1)]
    for _ in range(N):
        x, y = map(int, input().split())
        X[x-1].append(y-1)
        Y[y-1].append(x-1)
else:
    X = [[0, 1, 2, 3, 4], [0], [0], [0], [0], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
    X = [[0], [], [], [], [0, 4], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
    X = [[0, 1, 2, 3], [0], [0, 4], [0], [0], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
    Y = [[0, 1, 2, 3, 4], [0], [0], [0], [2], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
    
    X = [[0, 1, 2, 3], [0], [0, 4], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
    Y = [[0, 1, 2], [0], [0], [0], [2], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]

# print(X[:20])
# print(Y[:20])
for i in range(len(Y)):
    for j in range(len(Y[i])-1):
        # print(Y[i][j], Y[i][j+1])
        cb(Y[i][j], Y[i][j+1])

# print(P)
M = [[] for _ in range(K)]
for i in range(K):
    M[P[i]].append(i)
# print("M =", M)
ans = -N
for i in range(K):
    S = []
    for j in M[i]:
        for k in X[j]:
            S.append(k)
    # print("S1 =", S)
    S = list(set(S))
    # print("S2 =", S)
    ans += len(S)*len(M[i])
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
from collections import defaultdict
X=dict()
Y=dict()
P=[]
root=[-1]*N
def find(i):
    global root
    if root[i]>=0:
        root[i]=find(root[i])
        return root[i]
    return i
for i in range(N):
    x,y=map(int,input().split())
    P+=[(x,y)]
    if x not in X.keys():
        rx=i
        X[x]=i
    else:
        rx=find(X[x])
        X[x]=rx
    if y not in Y.keys():
        ry=i
        Y[y]=i
    else:
        ry=find(Y[y])
        Y[y]=ry
    if rx==ry:
        continue
    elif root[rx]<=root[ry]:
        root[rx]+=root[ry]
        root[ry]=rx
    else:
        root[ry]+=root[rx]
        root[rx]=ry
cntx=defaultdict(set)
cnty=defaultdict(set)
RP=set()
ans=0
for i in range(N):
    x,y=P[i]
    r=find(i)
    cntx[r]|={x}
    cnty[r]|={y}
    RP|={r}
for k in RP:
    ans+=len(cntx[k])*len(cnty[k])
print(ans-N)

Submission status: Wrong Answer

Solution code:
N=int(input())
P=[tuple(map(int,input().split())) for i in range(N)]
Dx=dict()
Dy=dict()
for i in range(N):
    x,y=P[i]
    if x in Dx:
        Dx[x]+=1
    else:
        Dx[x]=1
    if y in Dy:
        Dy[y]+=1
    else:
        Dy[y]=1
ans=0
for i in range(N):
    x,y=P[i]
    ans+=(Dx[x]-1)*(Dy[y]-1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(2*10**6)
class UF():
    def __init__(self, num):
        self.par = [-1]*num
        self.size = [1]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
                self.size[rx] += self.size[ry] 
            elif self.par[rx] > self.par[ry]:
                self.par[rx] = ry
                self.size[ry] += self.size[rx]
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
                self.size[rx] += self.size[ry]
        return



N = int(input())

XY = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
X, Y = list(map(list, zip(*XY)))
G = UF(N)
checked = [False]*N

Xc = defaultdict(list)
Yc = defaultdict(list)
for i in range(N):
    Xc[X[i]].append(i)
    Yc[Y[i]].append(i)

for v in Xc.values():
    if len(v) == 1:
        continue
    vx = v[0]
    for x in v[1:]:
        G.union(vx, x)

for v in Yc.values():
    if len(v) == 1:
        continue
    vy = v[0]
    for y in v[1:]:
        G.union(vy, y)

ans = -N

for i in range(N):
    ri = G.find(i)
    if checked[ri]:
        continue
    ans += len(Xc[X[ri]])*len(Yc[Y[ri]])
    checked[ri] = True

print(ans)