You are given a tree (an undirected connected acyclic graph) consisting of $n$ vertices and $n - 1$ edges. A number is written on each edge, each number is either $0$ (let's call such edges $0$-edges) or $1$ (those are $1$-edges).

Let's call an ordered pair of vertices $(x, y)$ ($x \ne y$) valid if, while traversing the simple path from $x$ to $y$, we never go through a $0$-edge after going through a $1$-edge. Your task is to calculate the number of valid pairs in the tree.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 200000$) — the number of vertices in the tree.

Then $n - 1$ lines follow, each denoting an edge of the tree. Each edge is represented by three integers $x_i$, $y_i$ and $c_i$ ($1 \le x_i, y_i \le n$, $0 \le c_i \le 1$, $x_i \ne y_i$) — the vertices connected by this edge and the number written on it, respectively.

It is guaranteed that the given edges form a tree.


-----Output-----

Print one integer — the number of valid pairs of vertices.


-----Example-----
Input
7
2 1 1
3 2 0
4 2 1
5 2 0
6 7 1
7 2 1

Output
34



-----Note-----

The picture corresponding to the first example:

[Image]

Difficulty: interview

Starter code:

Solutions:
class UnionFind:
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.rank = [1 for i in range(N)]
        self.rank[0] = 0
    def union(self, x, y):
        if not self.is_same_set(x, y):
            par_x = self.find_par(x)
            par_y = self.find_par(y)

            if self.rank[par_x] > self.rank[par_y]:
                self.rank[par_x] += self.rank[par_y]
                self.rank[par_y] = 0
                self.par[par_y] = par_x
            else:
                self.rank[par_y] += self.rank[par_x]
                self.rank[par_x] = 0
                self.par[par_x] = par_y

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

    def is_same_set(self, x, y):
        return self.find_par(x) == self.find_par(y)

    def size(self, x):
        return self.rank[self.find_par(x)]
# 2 unionfind, para 0 e para 1 formando 2 florestas
# lista de adj
# verificar todos os componentes existentes e adicionar na resposta n * (n-1)

n = int(input())

adj = [[] for i in range(n+1)]

uf0 = UnionFind(n+1)
uf1 = UnionFind(n+1)

for i in range(n-1):
    x, y, c = list(map(int, input().split()))

    if c == 0:
        uf0.union(x, y)
    else:
        uf1.union(x, y)
    adj[x].append(y)
    adj[y].append(x)
for i in range(n+1):
    uf0.find_par(i)
    uf1.find_par(i)

resp = 0

for i in set(uf0.par):
    resp += uf0.rank[i] * (uf0.rank[i] - 1)
for i in set(uf1.par):
    resp += uf1.rank[i] * (uf1.rank[i] - 1)

# pra cada componente do 0-uf verificar se existe esse vertice na 1-uf e ele for conectado com alguém, se sim, multiplicar (n-1)*(m-1) sendo n o componente da 0-uf e m o componente da 1-f e adicionar na resposta

for i in range(len(uf0.par)):
    if uf0.rank[uf0.find_par(i)] > 1:
        if uf1.rank[uf1.find_par(i)] > 1:
            resp += (uf0.rank[uf0.find_par(i)] - 1) * (uf1.rank[uf1.find_par(i)] - 1)
print(resp)


class UnionFind:
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.rank = [1 for i in range(N)]
        self.rank[0] = 0
    def union(self, x, y):
        if not self.is_same_set(x, y):
            par_x = self.find_par(x)
            par_y = self.find_par(y)

            if self.rank[par_x] > self.rank[par_y]:
                self.rank[par_x] += self.rank[par_y]
                self.rank[par_y] = 0
                self.par[par_y] = par_x
            else:
                self.rank[par_y] += self.rank[par_x]
                self.rank[par_x] = 0
                self.par[par_x] = par_y

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

    def is_same_set(self, x, y):
        return self.find_par(x) == self.find_par(y)

    def size(self, x):
        return self.rank[self.find_par(x)]
# 2 unionfind, para 0 e para 1 formando 2 florestas
# lista de adj
# verificar todos os componentes existentes e adicionar na resposta n * (n-1)

n = int(input())

adj = [[] for i in range(n+1)]

uf0 = UnionFind(n+1)
uf1 = UnionFind(n+1)

for i in range(n-1):
    x, y, c = list(map(int, input().split()))

    if c == 0:
        uf0.union(x, y)
    else:
        uf1.union(x, y)
    adj[x].append(y)
    adj[y].append(x)

    uf0.find_par(x)
    uf1.find_par(y)

resp = 0

resp += sum([uf0.rank[i] * (uf0.rank[i] - 1) for i in set(uf0.par)])
resp += sum([uf1.rank[i] * (uf1.rank[i] - 1) for i in set(uf1.par)])
# pra cada componente do 0-uf verificar se existe esse vertice na 1-uf e ele for conectado com alguém, se sim, multiplicar (n-1)*(m-1) sendo n o componente da 0-uf e m o componente da 1-f e adicionar na resposta
#ja_visto = set()
for i in range(len(uf0.par)):
    if uf0.rank[uf0.find_par(i)] > 1: #and not uf0.find_par(i) in ja_visto:
        #ja_visto.add(uf0.find_par(i))
        if uf1.rank[uf1.find_par(i)] > 1:
            resp += (uf0.rank[uf0.find_par(i)] - 1) * (uf1.rank[uf1.find_par(i)] - 1)
print(resp)


from collections import deque

def bfs(source, graph, mark, num, fcount):
	visited = [source]
	q = deque()
	mark[source] = True
	q.append(source)
	while q:
		u = q.popleft()
		for v, c in g[u]:
			if c == num and not mark[v]:
				mark[v] = True
				visited.append(v)
				q.append(v)
	if len(visited) > 1:
		for u in visited:
			fcount[u] = len(visited)

n = int(input())
edges = [tuple(map(int, input().split())) for _ in range(0, n - 1)]
g = [[] for _ in range(0, n)]
cnt = [[0 for _ in range(0, n)] for _ in range(0, 2)]
for u, v, c in edges:
	g[u - 1].append((v - 1, c))
	g[v - 1].append((u - 1, c))

res = 0
for link in range(0, 2):
	mark = [False] * n
	for u in range(0, n):
		if not mark[u]:
			bfs(u, g, mark, link, cnt[link])
			res += cnt[link][u] * (cnt[link][u] - 1)

for i in range(0, n):
	if cnt[0][i] > 0 and cnt[1][i] > 1:
		res += (cnt[0][i] - 1) * (cnt[1][i] - 1)

print(int(res))

class Deque:
	def __init__(self):
		self.buff = [0] * 400000
		self.l = 0
		self.r = 0
	def append(self, x):
		self.buff[self.r] = x
		self.r = self.r + 1
	def popleft(self):
		old_left = self.l
		self.l = self.l + 1
		return self.buff[old_left]
	def __bool__(self):
		return self.l != self.r

q = Deque()

def bfs(source, graph, mark, num, fcount):
	visited = [source]
	mark[source] = True
	q.append(source)
	while q:
		u = q.popleft()
		for v, c in g[u]:
			if c == num and not mark[v]:
				mark[v] = True
				visited.append(v)
				q.append(v)
	if len(visited) > 1:
		for u in visited:
			fcount[u] = len(visited)

n = int(input())
edges = [tuple(map(int, input().split())) for _ in range(0, n - 1)]
g = [[] for _ in range(0, n)]
cnt = [[0 for _ in range(0, n)] for _ in range(0, 2)]
for u, v, c in edges:
	g[u - 1].append((v - 1, c))
	g[v - 1].append((u - 1, c))

res = 0
for link in range(0, 2):
	mark = [False] * n
	for u in range(0, n):
		if not mark[u]:
			bfs(u, g, mark, link, cnt[link])
			res += cnt[link][u] * (cnt[link][u] - 1)

for i in range(0, n):
	if cnt[0][i] > 0 and cnt[1][i] > 1:
		res += (cnt[0][i] - 1) * (cnt[1][i] - 1)

print(int(res))

from collections import defaultdict

def colour(a, graph, cur, i):
    top = set()
    top.add(i)
    while len(top):
        x = top.pop()
        a[x] = cur
        for y in graph[x]:
            if a[y] == 0:
                top.add(y)

def colour_graph(a, graph, n):
    cur = 0
    for i in range(1, n + 1):
        if a[i] or i not in graph:
            continue
        else:
            cur += 1
            colour(a, graph, cur, i)

def count(col):
    ans = 0
    for el in col:
        if col[el] > 1:
            ans += col[el]*(col[el] - 1)
    return ans

n = int(input())


graph0 = defaultdict(set)
graph1 = defaultdict(set)


vertex0 = set()

a0 = [0]*(n + 1)  
a1 = [0]*(n + 1)

for i in range(n - 1):
    x, y, c = list(map(int, input().split()))
    if c == 0:
        graph0[x].add(y)
        graph0[y].add(x)
        vertex0.add(x)
        vertex0.add(y)
    else:
        graph1[x].add(y)
        graph1[y].add(x)


colour_graph(a0, graph0, n)
colour_graph(a1, graph1, n)

answer = 0
col0 = defaultdict(int)
col1 = defaultdict(int)

for i in range(n + 1):
    if a0[i]:
        col0[a0[i]] += 1
    if a1[i]:
        col1[a1[i]] += 1

answer += count(col0) + count(col1)

col = defaultdict(int)
for v in vertex0:
    col[a1[v]] += col0[a0[v]] - 1
for el in col:
    if el:
        answer += col[el]*(col1[el] - 1)
        
print(answer)


class dsu:
	def __init__(self,n):
		self.arr = [i for i in range(n)]
		self.size = [1 for i in range(n)]
		self.s = n
	def find(self,i):
		while(i!=self.arr[i]):
			i = self.arr[i]
		return i
		if(self.arr[i]!=i):
			self.arr[i] = self.find(self.arr[i])
		return self.arr[i]
	def union(self,i,j):
		fa = self.find(i)
		fb = self.find(j)
		if(fa == fb):
			return
		s1 = self.size[fa]
		s2 = self.size[fb]
		if(s1<s2):
			self.arr[fa] = fb
			self.size[fb] += self.size[fa]
		else:
			self.arr[fb] = fa
			self.size[fa] += self.size[fb]
n = int(input())
zero = dsu(n)
one = dsu(n)
for i in range(n-1):
	a = [int(i) for i in input().split(' ')]
	x = a[0]-1
	y = a[1]-1
	c = a[2]
	if(c==0):
		zero.union(x,y)
	else:
		one.union(x,y)
count = 0
for i in range(n):
	if(zero.arr[i] == i):
		count+=zero.size[i]*(zero.size[i]-1)
	if(one.arr[i] == i):
		count+=one.size[i]*(one.size[i]-1)
	count += (zero.size[zero.find(i)]-1)*(one.size[one.find(i)]-1)
print(count)

import sys

class Disjoint:
    def __init__(self, n):
        self.n = n
        self.size = [1] * self.n
        self.parent = [i for i in range(self.n)]
    
    def root(self, node):
        self.parent[node] = node if self.parent[node] == node else self.root(self.parent[node])
        return self.parent[node]
    
    def join(self, a, b):
        a = self.root(a)
        b = self.root(b)
        if a == b:
            return False
        if self.size[a] > self.size[b]:
            a, b = b, a
            
        self.size[b] += self.size[a]
        self.parent[a] = b
        return True
    
    

inp = [int(x) for x in sys.stdin.read().split()]
n = inp[0]

white = Disjoint(n)
black = Disjoint(n)

inp_idx = 1
for i in range(n - 1):
    x, y, c = inp[inp_idx], inp[inp_idx + 1], inp[inp_idx + 2]
    x -= 1
    y -= 1
    inp_idx += 3
    
    if c == 0:
        white.join(x, y)
    else:
        black.join(x, y)
    
ans = 0
for i in range(n):
    rootW = white.root(i)
    rootB = black.root(i)
    ans += white.size[rootW] - 1
    ans += black.size[rootB] - 1
    
    ans += (white.size[rootW] - 1) * (black.size[rootB] - 1)
    
print(ans)


class UnionFind():

    def __init__(self, n):
        self.n = n

        self.root = [-1]*(n+1)

        self.rnk = [0]*(n+1)


    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:

            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self, x, y):

        x = self.Find_Root(x)
        y = self.Find_Root(y)

        if(x == y):
            return 

        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y

            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)


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

import sys
input = sys.stdin.readline

N = int(input())
uni0 = UnionFind(N)
uni1 = UnionFind(N)
for _ in range(N-1):
    a, b, c = map(int, input().split())
    if c == 0:
        uni0.Unite(a-1, b-1)
    else:
        uni1.Unite(a-1, b-1)

g0 = {}
g1 = {}
for i in range(N):
    if uni0.Count(i) != 1:
        r = uni0.Find_Root(i)
        if not r in g0.keys():
            g0[r] = [i]
        else:
            g0[r].append(i)
    if uni1.Count(i) != 1:
        r = uni1.Find_Root(i)
        if not r in g1.keys():
            g1[r] = [i]
        else:
            g1[r].append(i)

ans = 0
for v_list in g1.values():
    c = 0
    for n in v_list:
        if uni0.Count(n) == 1:
            c += 1
    l = len(v_list)
    ans += c*(l-1)

for v_list in g0.values():
    c = 0
    for n in v_list:
        if uni1.Count(n) != 1:
            r = uni1.Find_Root(n)
            c += len(g1[r])-1
    c += len(v_list)-1
    ans += len(v_list)*c

print(ans)

import sys
input = sys.stdin.readline


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

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

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1
        
    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def get_size(self, x):
        return -self.parent[self.root(x)]
    
    def get_cnt(self):
        return self.cnt


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

uf0 = UnionFind(n)
uf1 = UnionFind(n)
tree0 = [[] for i in range(n)]
tree1 = [[] for i in range(n)]
for i in range(n - 1):
    a, b, cost = info[i]
    a -= 1
    b -= 1
    if cost == 0:
        tree0[a].append(b)
        tree0[b].append(a)
        uf0.merge(a, b)
    else:
        tree1[a].append(b)
        tree1[b].append(a)
        uf1.merge(a, b)

ans0 = [0] * n
ans1 = [0] * n
for i in range(n):
    ans0[i] = uf0.get_size(i) - 1
    ans1[i] = uf1.get_size(i) - 1

ans = 0
for i in range(n):
    ans += ans0[i]
    ans += ans1[i]
    ans += ans0[i] * ans1[i]
print(ans)

import sys
input = sys.stdin.readline
n = int(input())
abd = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0]*(n+1)
if n == 2:
  print(2)
  return
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
  deg[a] += 1
  deg[b] += 1
dp = [[0]*3 for i in range(n+1)]
stack = []
root = 0
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif not root:
    root = i
    deg[root] += 1
while stack:
  x = stack.pop()
  if dp[x][0] == dp[x][1] == 0:
    for y,d in graph[x]:
      dp[y][d] += 1
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
  else:
    for y,d in graph[x]:
      if deg[y] > 1:
        dp[y][d] += dp[x][d]+1
        if d == 1:
          dp[y][2] += dp[x][0]+dp[x][2]
        deg[y] -= 1
        if deg[y] == 1:
          stack.append(y)
stack = [root]
deg[root] -= 1
while stack:
  x = stack.pop()
  for y,d in graph[x]:
    if deg[y] == 1:
      deg[y] -= 1
      dp[y][d] += dp[x][d]-dp[y][d]
      if d == 1:
        dp[y][2] += dp[x][2]+dp[x][0]-dp[y][0]-dp[y][2]
      stack.append(y)
ans = 0
for i,j,k in dp:
  ans += i+j+k
print(ans)

def addEdge(arr: [], x, y):
    x, y = getRoot(arr, x), getRoot(arr, y)
    if arr[x] <= arr[y]:
        arr[x] += arr[y]
        arr[y] = x
    else:
        arr[y] += arr[x]
        arr[x] = y


def getRoot(arr: [], id):
    while arr[id] > 0:
        id = arr[id]
    return id


def solve(zeroArr: [], oneArr: []):
    Ans = 0
    for i in range(1, len(zeroArr)):
        if zeroArr[i] < 0:
            Ans += zeroArr[i] * (-1) * (zeroArr[i] * (-1) - 1)
        if oneArr[i] < 0:
            Ans += oneArr[i] * (-1) * (oneArr[i] * (-1) - 1)
        if (zeroArr[i] != -1 and oneArr[i] != -1):
            one, zero = getRoot(oneArr, i), getRoot(zeroArr, i)
            Ans += (oneArr[one] * (-1) - 1) * (zeroArr[zero] * (-1) - 1)
    return Ans

n = int(input())
zeroArr, oneArr = [-1] * (n + 1), [-1] * (n + 1)
while n > 1:
    a, b, w = [int(x) for x in input().split()]
    if w == 0:
        addEdge(zeroArr, a, b)
    else:
        addEdge(oneArr, a, b)
    n -= 1
print(solve(zeroArr, oneArr))


mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

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

        def find_root(self, x):
            while self.root[x] >= 0:
                x = self.root[x]
            return x

        def unite(self, x, y):
            x = self.find_root(x)
            y = self.find_root(y)
            if x == y:
                return
            elif self.rnk[x] > self.rnk[y]:
                self.root[x] += self.root[y]
                self.root[y] = x
            else:
                self.root[y] += self.root[x]
                self.root[x] = y
                if self.rnk[x] == self.rnk[y]:
                    self.rnk[y] += 1

        def isSameGroup(self, x, y):
            return self.find_root(x) == self.find_root(y)

        def size(self, x):
            return -self.root[self.find_root(x)]

    N = int(input())
    adj = [[] for _ in range(N+1)]
    UF0 = UnionFind(N+1)
    UF1 = UnionFind(N+1)
    for _ in range(N-1):
        a, b, c = list(map(int, input().split()))
        adj[a].append((b, c))
        adj[b].append((a, c))
        if c == 0:
            UF0.unite(a, b)
        else:
            UF1.unite(a, b)

    ans = 0
    roots = set()
    for v in range(1, N+1):
        r = UF1.find_root(v)
        if r not in roots:
            roots.add(r)
            s = -UF1.root[r]
            ans += s * (s-1)
    #print(ans)

    roots = set()
    for v in range(1, N+1):
        r = UF0.find_root(v)
        if r not in roots:
            roots.add(r)
            s = -UF0.root[r]
            ans += s * (s-1)
    #print(ans)

    for v in range(1, N+1):
        W = 0
        B = 0
        flg0 = 0
        flg1 = 0
        for u, c in adj[v]:
            if flg0 and flg1:
                break
            if c == 0:
                if flg0:
                    continue
                W += UF0.size(u) - 1
                flg0 = 1
            else:
                if flg1:
                    continue
                B += UF1.size(u) - 1
                flg1 = 1
        ans += W * B
    print(ans)


def __starting_point():
    main()

__starting_point()

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2*10**5)
I = lambda : list(map(int,input().split()))

n,=I()
r=[[1 for i in range(n)],[1 for i in range(n)]]
p=[[i for i in range(n)],[i for i in range(n)]]
def find(x,c):
	if x!=p[c][x]:
		p[c][x]=find(p[c][x],c)
	return p[c][x]

def union(a,b,c):
	x=find(a,c)
	y=find(b,c)
	mm=min(x,y)
	if x!=y:
		p[c][y]=p[c][x]=mm
		r[c][mm]+=r[c][max(x,y)]
an=0
for i in range(n-1):
	a,b,c=I()
	union(a-1,b-1,c)
vis=[0]*n
cc=[]
for i in range(n):
	s0=r[0][i]
	s1=r[1][i]
	if p[0][i]==i:
		an+=(s0-1)*s0
	if p[1][i]==i:
		an+=(s1-1)*s1
	an+=(r[1][find(i,1)]-1)*(r[0][find(i,0)]-1)
print(an)

import sys;sys.setrecursionlimit(10**9)
class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
    self.siz=n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
    self.siz-=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]
  def size(self):
    return self.siz

n=int(input())
ouf=UnionFind(n)
zuf=UnionFind(n)
for _ in range(n-1):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  if c==0:
    zuf.unite(a,b)
  else:
    ouf.unite(a,b)
ans=0
for i in range(n):
  m=zuf.count(i)
  if zuf.find_root(i)==i:ans+=m*(m-1)
  mm=ouf.count(i)
  if ouf.find_root(i)==i:ans+=mm*(mm-1)
  ans+=(m-1)*(mm-1)
print(ans)

class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

import sys

input=sys.stdin.readline
n=int(input())
uf0=UnionFindVerSize(n)
uf1=UnionFindVerSize(n)
for i in range(n-1):
    x,y,c=map(int,input().split())
    if c==0:
        uf0.unite(x-1,y-1)
    else:
        uf1.unite(x-1,y-1)

data=[0]*n
cnt=[0]*n
for i in range(n):
    root=uf1.find_root(i)
    data[root]+=uf0.get_size(i)
    cnt[root]+=1

ans=sum(data[i]*cnt[i] for i in range(n))
print(ans-n)