Problem:
 Score : 1100 points    Problem Statement Snuke got positive integers s_1,...,s_N from his mother, as a birthday present. There may be duplicate elements.  He will circle some of these N integers. Since he dislikes cubic numbers, he wants to ensure that if both s_i and s_j (i ≠ j) are circled, the product s_is_j is not cubic. For example, when s_1=1,s_2=1,s_3=2,s_4=4 , it is not possible to circle both s_1 and s_2 at the same time. It is not possible to circle both s_3 and s_4 at the same time, either.  Find the maximum number of integers that Snuke can circle.      Constraints  1 ≦ N ≦ 10^5  1 ≦ s_i ≦ 10^{10}  All input values are integers.         Input The input is given from Standard Input in the following format:  N  s_1 : s_N       Output Print the maximum number of integers that Snuke can circle.        Sample Input 1 8
1
2
3
4
5
6
7
8      Sample Output 1 6  Snuke can circle 1,2,3,5,6,7 .       Sample Input 2 6
2
4
8
16
32
64      Sample Output 2 3       Sample Input 3 10
1
10
100
1000000007
10000000000
1000000009
999999999
999
999
999      Sample Output 3 9

Solution (Python):
import sys
from subprocess import Popen, PIPE
from itertools import groupby
from collections import Counter

def main():
    sys.stdin.readline()
    S = sys.stdin.read().split()
    T = []
    inv_dict = {}
    Factors = Popen(["factor"] + S, stdout=PIPE).communicate()[0].split(b"\n")
    for factors in Factors[:-1]:
        factors = map(int, factors.split()[1:])
        t = 1
        t_inv = 1
        for f, group in groupby(factors):
            n = len(list(group)) % 3
            if n == 1:
                t *= f
            elif n == 2:
                t_inv *= f
        t, t_inv = t * t_inv * t_inv, t * t * t_inv
        T.append(t)
        inv_dict[t] = t_inv

    counter_T = Counter(T)
    ans = 0
    for t, t_cnt in counter_T.items():
        if t == 1:
            ans += 1
            continue
        t_inv = inv_dict[t]
        t_inv_cnt = counter_T[t_inv]
        if t_cnt > t_inv_cnt or (t_cnt == t_inv_cnt and t > t_inv):
            ans += t_cnt
    print(ans)

main()

Solution (Python):
import sys
from collections import Counter

def make_prime_checker(n):
    
    is_prime = [False, True, False, False, False, True] * (n//6+1)
    del is_prime[n+1:]
    is_prime[1:4] = False, True, True
    for i in range(5, int(n**0.5)+1):
        if is_prime[i]:
            is_prime[i*i::i] = [False] * (n//i-i+1)
    return is_prime

def main():
    Primes = [p for p, is_p in enumerate(make_prime_checker(2200)) if is_p]
    def decomp(n):
        res1 = res2 = 1
        for p in Primes:
            cnt = 0
            while n % p == 0:
                n //= p
                cnt += 1
            cnt %= 3
            if cnt == 1:
                res1 *= p
            elif cnt == 2:
                res2 *= p
        if int(n**0.5)**2 == n:
            res2 *= int(n**0.5)
        else:
            res1 *= n
        return res1 * res2 * res2, res1 * res1 * res2

    N, *S = map(int, sys.stdin.buffer.read().split())
    T = []
    inv_dict = {}
    for s in S:
        t, t_inv = decomp(s)
        T.append(t)
        inv_dict[t] = t_inv

    counter_T = Counter(T)
    ans = 0
    for t, t_cnt in counter_T.items():
        if t == 1:
            ans += 1
            continue
        t_inv = inv_dict[t]
        t_inv_cnt = counter_T[t_inv]
        if t_cnt > t_inv_cnt or (t_cnt == t_inv_cnt and t > t_inv):
            ans += t_cnt
    print(ans)

main()

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


def make_prime_numbers(n):
    """n以下の素数を列挙したリストを出力する
    計算量: O(NloglogN)
    入出力例: 30 -> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    """
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(2 * i, n + 1, i):
            is_prime[j] = False
    prime_numbers = [i for i in range(n + 1) if is_prime[i]]
    return prime_numbers


n = int(input())
s = [int(input()) for i in range(n)]


primes = make_prime_numbers(int((10 ** 10) ** (1 / 3) + 20))
pow2 = set([i ** 2 for i in range(10 ** 5 + 10)])
to_anti = {}


for i in range(n):
    anti = 1
    tmp_s = s[i]
    for div in primes:
        cnt = 0
        while tmp_s % div == 0:
            tmp_s //= div
            cnt += 1
        mod_cnt = cnt % 3
        cnt = cnt - mod_cnt
        s[i] //= (div ** cnt)
        anti *= div ** ((3 - mod_cnt) % 3)
    if tmp_s in pow2:
        to_anti[s[i]] = anti * int(tmp_s ** 0.5)
    else:
        to_anti[s[i]] = anti * (tmp_s ** 2)


cnts = {}
for key in s:
    if key not in cnts:
        cnts[key] = 0
    cnts[key] += 1



ans = 0
used = set([])
for key in cnts:
    if key == 1:
        ans += 1
        continue
    if key in used:
        continue
    anti_key = to_anti[key]
    used.add(anti_key)
    if anti_key in cnts:
        ans += max(cnts[anti_key], cnts[key])
    else:
        ans += cnts[key]

print(ans)

Solution (Python):
def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

prime=get_sieve_of_eratosthenes_new(2160)

def ind(b,n):
    res=0
    while n%b==0:
        res+=1
        n//=b
    return res

import sys

input=sys.stdin.readline

N=int(input())
dic={}
inverse={}
for i in range(N):
    s=int(input())
    news=1
    invs=1
    for p in prime:
        a=ind(p,s)
        s//=p**a
        news*=p**(a%3)
        invs*=p**((-a)%3)
    if s==1 or int(s**0.5)**2!=s:
        news*=s
        invs*=s**2
        if news not in dic:
            dic[news]=0
            inverse[news]=0
        dic[news]+=1
        inverse[news]=invs
    else:
        news*=s
        invs*=int(s**0.5)
        if news not in dic:
            dic[news]=0
            inverse[news]=0
        dic[news]+=1
        inverse[news]=invs

one=0
double=0
for i in dic:
    if i!=1:
        if inverse[i] in dic:
            double+=max(dic[i],dic[inverse[i]])
        else:
            one+=dic[i]

double//=2
ans=one+double
if 1 in dic:
    ans+=1
print(ans)

Solution (Python):
from collections import defaultdict
import sys
input = sys.stdin.readline
nmax = 10**5+10
eratos = [0 for i in range(nmax+1)]
prime = []
cnt = 2
while True:
  while cnt <= nmax and eratos[cnt]:
    cnt += 1
  if cnt > nmax:
    break
  eratos[cnt] = 1
  prime.append(cnt)
  for i in range(cnt**2,nmax+1,cnt):
    eratos[i] = 1
cbls = []
sqst = set()
for i in prime:
  if i**3 <= 10**10:
    cbls.append(i**3)
  else:
    sqst.add(i**2)
n = int(input())
a = [int(input()) for i in range(n)]
dc = defaultdict(int)
for i in a:
  for p in cbls:
    while i%p == 0:
      i //= p
  dc[i] += 1
ans = n
for i,v in dc.items():
  if i == 1:
    ans -= v-1
    continue
  if v == 0:
    continue
  x = 1
  for p in prime:
    if p**3 > 10**10:
      break
    if i%(p*p) == 0:
      x *= p
      i //= p*p
    elif i%p == 0:
      x *= p**2
      i //= p
  if i in sqst:
    x *= int(i**0.5+0.5)
    i //= i
  if i != 1:
    continue
  if x in dc:
    ans -= min(dc[x],v)
    dc[x] = 0
print(ans)

Solution (Python):
from collections import defaultdict

def prime_sieve(start, end):
    assert end > 1
    is_prime = [True for i in range(end)]
    is_prime[0], is_prime[1] = False, False
    primes = list()
    for i in range(2,end):
        if is_prime[i]:
            if i >= start:  
                primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes

def prime_factorize(n,primes):
  res = []
  for i in primes:
    tmp = 0
    while not (n%i):
      n //= i
      tmp += 1
    res.append(tmp%3)
  res.append(n)
  return tuple(res)


n = int(input())
s = [int(input()) for i in range(n)]
primes = prime_sieve(1,315)
factorized = defaultdict(int)
square = dict()
for i in range(1,100001):
  square[i**2] = i
cubic = set([i**3 for i in range(1,4000)])
mid_primes = prime_sieve(315,5500)
rev_mid_primes = dict()
for i in mid_primes:
  for j in mid_primes:
    if i == j:
      continue
    rev_mid_primes[i**2*j] = j**2*i
    
    
for i in s:
  t = prime_factorize(i,primes)
  factorized[t] += 1
ans = n
f = factorized.items()
for k,v in f:
  rem = k[-1]
  another = [(3-i) % 3 for i in k[:-1]]
  if rem in cubic:
    another.append(1)
  elif rem in square:
    another.append(square[rem])
  elif rem in rev_mid_primes:
    another.append(rev_mid_primes[rem])
  else:
    another.append(rem**2)
  another = tuple(another)
  if k == another:
    ans -= factorized[k] - 1
    continue
  if another in factorized:
    if factorized[k] <= factorized[another]:
      ans -= factorized[k]
      factorized[k] = 0
    else:
      ans -= factorized[another]
      factorized[another] = 0
print(ans)

Solution (Python):
import sys
from collections import defaultdict


def eratosthenes_generator():
    yield 2
    n = 3
    h = {}
    while True:
        m = n
        if n in h:
            b = h[n]
            m += 2 * b
            while m in h:
                m += 2 * b
            h[m] = b
            del h[n]
        else:
            m += 2 * n
            while m in h:
                m += 2 * n
            h[m] = n
            yield n
        n += 2


gen = eratosthenes_generator()
p = 0
primes = []
for p in gen:
    if p > 2154:
        break
    primes.append(p)

prime_pairs = {1: 1, p: p * p, p * p: p}
for p in gen:
    if p > 100000:
        break
    p2 = p * p
    prime_pairs[p] = p2
    prime_pairs[p2] = p

n, *sss = map(int, sys.stdin.buffer.read().split())
normalized = defaultdict(int)
over_pairs = {}
frac_pairs = {}
ans = 0
for s in sss:
    
    frac = 1  
    pair = 1  
    for p in primes:
        if s < p:
            break
        x = 0
        d, m = divmod(s, p)
        while m == 0:
            x += 1
            s = d
            d, m = divmod(s, p)
        x %= 3
        if x == 1:
            frac *= p
            pair *= p ** 2
        elif x == 2:
            frac *= p ** 2
            pair *= p
    if s > 2154 and s not in prime_pairs:
        ans += 1
        continue
    frac_pairs[frac] = pair
    normalized[s, frac] += 1

if (1, 1) in normalized:
    ans += 1
    del normalized[1, 1]

tmp = 0
for (s, frac), cnt in normalized.items():
    pair = (prime_pairs[s], frac_pairs[frac])
    if pair not in normalized:
        tmp += cnt * 2
    else:
        tmp += max(cnt, normalized[pair])
ans += tmp // 2

print(ans)

Solution (Python):
def examA():
    S = SI()
    if "W" in S and not "E" in S:
        print("No")
    elif "E" in S and not "W" in S:
        print("No")
    elif "N" in S and not "S" in S:
        print("No")
    elif "S" in S and not "N" in S:
        print("No")
    else:
        print("Yes")
    return

def examB():
    N = I()
    A = [I()for _ in range(N)]
    ans = 0
    for i in range(N-1):
        ans += A[i]//2
        if A[i]%2 and A[i+1]>=1:
            ans += 1
            A[i+1] -= 1
    ans += A[N-1]//2
    print(ans)
    return

def examC():
    N = I()
    A = [I()for _ in range(N)]
    if N==1:
        print(0)
        return
    odd = set()
    for i in range(N):
        if i&1==0:
            odd.add(A[i])
    A.sort()
    ans = 0
    for i in range((N+1)//2):
        if A[i*2] in odd:
            continue
        ans += 1
    print(ans)
    return

def examD():
    def factorization_(a):
        rep = [[]for _ in range(2)]
        pair = []
        for i in range(2,int(10**(3.4))+2):
            cur = 0
            while a%i==0:
                cur += 1
                a //= i
            if cur>0:
                cur %= 3
                if cur==0:
                    continue
                rep[0].append((i,cur))
                pair.append((i,3-cur))
        if not rep[0]:
            rep[0].append((0,0))
            pair.append((0,0))
        rep[1] = a
        rep[0] = tuple(rep[0])

        rep = tuple(rep)
        pair = tuple(pair)
        return rep, pair

    def square(a):
        rep = set()
        for i in range(int(10**(3.3)),a+1):
            rep.add(i**2)
        return rep

    N = I()
    S = [I()for _ in range(N)]
    group = defaultdict(int)
    P = defaultdict(tuple)
    for s in S:
        g,p = factorization_(s)
        group[g] += 1
        P[g[0]] = p
    
    
    
    sq = square(int(10**(5))+1)
    ans = 0
    for key,c in group.items():
        rep, rest = key
        if rest in sq:
            pair = int(pow((rest+1),0.5))
        else:
            pair = rest**2
        if rep==((0,0),) and pair==1:
            ans += 1
        else:
            if (P[rep],pair) in group:
                if c < group[(P[rep], pair)]:
                    ans += group[(P[rep], pair)]
                else:
                    ans += c
                group[(P[rep], pair)] = 0
            else:
                ans += c
            group[key] = 0
        
    print(ans)
    return

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

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

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,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 = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examD()

"""

"""

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

def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1<<32 else [2, 3, 5, 7, 11, 13, 17] if n < 1<<48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8 + 1
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r-k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x-ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n//g): return n//g
def primeFactor(N):
    i = 2
    ret = {}
    n = N
    mrFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i%2
        if i == 101 and n >= 2**20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    mrFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if mrFlg > 0: ret = {x: ret[x] for x in sorted(ret)}
    return ret

N = int(input())
ans = 0
D = {}
for _ in range(N):
    pf = primeFactor(int(input()))
    a, b = 1, 1
    for p in pf:
        a *= p ** (pf[p] % 3)
        b *= p ** (-pf[p] % 3)
    if a not in D: D[a] = 0
    if a == b:
        if D[a] == 0: ans += 1
    else:
        if b not in D: D[b] = 0
        if D[b] <= D[a]: ans += 1
    D[a] += 1

print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import Counter
LIMIT = 2200
M = LIMIT**2
prime = [0]*M
for i in range(2, M):
    if prime[i]:
        continue
    for j in range(i, M, i):
        if not prime[j]:
            prime[j] = i


def prsh(N):
    prime = [2]
    for L in range(3,N):
        for p in prime:
            if not L % p:
                break
            if p > L**(1/2):
                prime.append(L)
                break
    return prime

PRIME = prsh(LIMIT)
SP = set(p for p in range(1, M) if prime[p] == p)
SP2 = Counter({p**2: p for p in SP})
MAXS = 10**10
N = int(readline())

L = []

match = Counter()
table = Counter()
for i in range(N):
    s = int(readline())
    ctr = 1
    res = 1
    for p in PRIME:
        if s == 1:
            break
        cnt = 0
        while s%p == 0:
            s //= p
            cnt += 1
        if cnt % 3:
            res *= p**(3 - cnt%3)
            ctr *= p**(cnt%3)
        if res > MAXS:
            res = 0    
    if s != 1:
        ctr *= s
        if s in SP:
            res *= s**2
        elif SP2[s]:
            res *= SP2[s]
        else:
            res = 0
    match[ctr] = res
    table[ctr] += 1

ans = 0
seen = set()
for k, v in table.copy().items():
    if k == 1:
        ans += min(v, 1)
        continue
    if k in seen:
        continue
    ans += max(v, table[match[k]])
    seen.add(match[k])
    seen.add(k)
print(ans)

Solution (Python):
"""
Rを立法数とする
a * R と a**2 * R a**1 * R → a**2*R a**1*R a**2*R
3つはなれてるとあかん！！　でも取り除かれてるはずだよな…
→Rを取り除いて後はDP

どうやって立法数を取り除く？
10**3.3まで試し割り？→5secだから間に合うかなぁ


Rを取り除く→10**3.333333以下の素数の3乗で割れるか確かめる

対になるsの導出：
素因数分解→10**5まで試し割(割れて10**5以下になったらdivlis方式に変える)
→巨大素数ばっかりだと死ぬ
2乗して新たに生まれたRを取り除けばok！！！！
→範囲は？10**6.6666以下か？(やばくね？)

sと対になるsでは片方しか取れない(dicで管理するかぁ)
sと対sの中で小さい方に合わせてdicで管理かなぁ
"""
def Sieve(n): 

    ret = []
    divlis = [-1] * (n+1) 
    
    flag = [True] * (n+1)
    flag[0] = False
    flag[1] = False

    ind = 2
    while ind <= n:

        if flag[ind]:
            ret.append(ind)

            ind2 = ind ** 2

            while ind2 <= n:
                flag[ind2] = False
                divlis[ind2] = ind
                ind2 += ind

        ind += 1

    return ret,divlis


N = int(input())
dic = {}

ret,divlis = Sieve(10**5)
ret2 = []
for i in ret:
    ret2.append(i**2)
div3 = 0

for loop in range(N):

    s = int(input())
    ndic = {}

    for i in ret:

        if i**3 > 10**10:
            break

        while s % i == 0:
            if i not in ndic:
                ndic[i] = 1
            else:
                ndic[i] += 1
            s //= i

    if s in ret2:
        ndic[int(s**0.5)] = 2
    else:
        ndic[s] = 1
    
    S = 1
    T = 1
    
    for i in ndic:
        S *= i ** (ndic[i] % 3)
        T *= i ** ((-1 * ndic[i]) % 3)

    

    if S == T:
        div3 += 1
    elif S < T:
        if S not in dic:
            dic[S] = [1,0]
        else:
            dic[S][0] += 1
    else:
        if T not in dic:
            dic[T] = [0,1]
        else:
            dic[T][1] += 1

ans = min(1,div3)

for i in dic:
    ans += max(dic[i])

print (ans)

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

def primeFactor(N):
    i = 2
    ret = {}
    n = N
    mrFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i%2
        if i == 101 and n >= 2**20:
            def findFactorRho(N):
                def gcd(a, b):
                    while b: a, b = b, a % b
                    return a
                def f(x, c):
                    return (x * x + c) % N
                for c in range(1, 99):
                    X, d, j = [2], 1, 0
                    while d == 1:
                        j += 1
                        X.append(f(X[-1], c))
                        X.append(f(X[-1], c))
                        d = gcd(abs(X[2*j]-X[j]), N)
                    if d != N:
                        if isPrimeMR(d):
                            return d
                        elif isPrimeMR(N//d): return N//d
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    mrFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if mrFlg > 0: ret = {x: ret[x] for x in sorted(ret)}
    return ret

def isPrimeMR(n):
    if n == 2:
        return True
    if n == 1 or n & 1 == 0:
        return False
    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    
    L = [2, 7, 61] if n < 1<<32 else [2, 13, 23, 1662803] if n < 1<<40 else [2, 3, 5, 7, 11, 13, 17] if n < 1<<48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    for a in L:
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1
        if y != n - 1 and t & 1 == 0:
            return False
    return True

N = int(input())
ans = 0
D = {}
for _ in range(N):
    pf = primeFactor(int(input()))
    a, b = 1, 1
    for p in pf:
        a *= p ** (pf[p] % 3)
        b *= p ** (-pf[p] % 3)
    if a not in D: D[a] = 0
    if a == b:
        if D[a] == 0: ans += 1
    else:
        if b not in D: D[b] = 0
        if D[b] <= D[a]: ans += 1
    D[a] += 1

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
from collections import Counter

N = int(input())

S = np.array(sys.stdin.readlines(), dtype=np.int64)

U = int(10 ** 3.4)
is_prime = np.zeros(U+1, dtype=np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(3,U+1,2):
    if p*p > U:
        break
    if is_prime[p]:
        is_prime[p*p::2*p] = 0

primes = is_prime.nonzero()[0]


for p in primes:
    tr = p*p*p
    while True:
        bl = (S % tr == 0)
        if bl.any():
            S[bl] //= tr
        else:
            break

square_part = np.ones_like(S)
free_part = S.copy() 
for p in primes:
    sq = p*p
    bl = (S % sq) == 0
    free_part[bl] //= sq
    square_part[bl] *= p

opposite = free_part * free_part * square_part

x_to_y = dict(zip(S,opposite))

counter = Counter(S)
answer = 0
for x,cx in counter.items():
    if x == 1:
        answer += 1
        continue
    y = x_to_y[x]
    if x > y:
        
        answer += cx
        continue
    cy = counter[y]
    answer -= cy
    answer += max(cx,cy)

print(answer)