The member states of the UN are planning to send $2$ people to the moon. They want them to be from different countries.  You will be given a list of pairs of astronaut ID's.  Each pair is made of astronauts from the same country.  Determine how many pairs of astronauts from different countries they can choose from.

Example  

$n=4$ 

$astronaut=[1,2],[2,3]$   

There are $\begin{array}{c}4\end{array}$ astronauts numbered $\mbox{0}$ through $3$.  Astronauts grouped by country are $\left[\mbox{0}\right]$ and $[1,2,3]$.  There are $3$ pairs to choose from: $[0,1],[0,2]$ and $[0,3]$.

Function Description  

Complete the journeyToMoon function in the editor below.    

journeyToMoon has the following parameter(s):  

int n: the number of astronauts  
int astronaut[p][2]: each element $\textit{astronaut}[i]$ is a $2$ element array that represents the ID's of two astronauts from the same country  

Returns 

- int: the number of valid pairs

Input Format

The first line contains two integers $n$ and $\boldsymbol{p}$, the number of astronauts and the number of pairs. 

Each of the next $\boldsymbol{p}$ lines contains $2$ space-separated integers denoting astronaut ID's of two who share the same nationality. 

Constraints

$1\leq n\leq10^5$  
$1\leq p\leq10^4$  

Sample Input 0
5 3
0 1
2 3
0 4

Sample Output 0
6

Explanation 0

Persons numbered $[0,1,4]$ belong to one country, and those numbered $[2,3]$ belong to another. The UN has $\boldsymbol{6}$ ways of choosing a pair:  

$[0,2],[0,3],[1,2],[1,3],[4,2],[4,3]$

Sample Input 1
4 1
0 2

Sample Output 1
5

Explanation 1

Persons numbered $[0,2]$  belong to the same country, but persons $\mbox{1}$ and $3$ don't share countries with anyone else.  The UN has $5$ ways of choosing a pair:

$[0,1],[0,3],[1,2],[1,3],[2,3]$

Source: hackerrank | Difficulty: MEDIUM
Tags: Graph algorithms


Solutions:
import sys
(N, I) = list(map(int, sys.stdin.readline().split()))
astronauts = [-1] * N
countries = []
for _ in range(I):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	if astronauts[A] > -1 and astronauts[B] > -1:
		if astronauts[A] != astronauts[B]:
			k = astronauts[B]
			countries[astronauts[A]].extend(countries[k])
			for i in countries[k]:
				astronauts[i] = astronauts[A]
			countries[k] = []
	elif astronauts[A] > -1 and astronauts[B] == -1:
		astronauts[B] = astronauts[A]
		countries[astronauts[A]].append(B)
	elif astronauts[A] == -1 and astronauts[B] > -1:
		astronauts[A] = astronauts[B]
		countries[astronauts[B]].append(A)
	else:
		astronauts[B] = astronauts[A] = len(countries)
		countries.append([A, B])
x = [len(c) for c in countries if c]
triangular_number = lambda n: n * (n + 1) // 2
unpaired = sum((x == -1 for x in astronauts))
total = triangular_number(unpaired - 1)
total += unpaired * sum(x)
for i in range(len(x) - 1):
	for j in range(i + 1, len(x)):
		total += x[i] * x[j]
print(total)


def go():
	I = lambda : map(int, input().split())
	(n, l) = I()
	d = list(range(n))

	def f(a):
		if d[a] != a:
			d[a] = f(d[a])
		return d[a]
	for i in range(l):
		(a, b) = I()
		d[f(a)] = f(b)
	q = [0] * n
	for i in range(n):
		q[f(i)] += 1
	print(sum((i * (n - i) for i in q)) // 2)
go()


raw_data = input().split(' ')
n = int(raw_data[0])
l = int(raw_data[1])
final_pairs = 0
country_list = []
if n == 1:
	print(0)
else:
	for line in range(l):
		data = input().split(' ')
		nauts = [int(x) for x in data]
		allocated_country1 = -1
		allocated_country2 = -1
		for c in range(len(country_list)):
			if allocated_country1 == -1 or allocated_country2 == -1:
				if nauts[0] in country_list[c]:
					allocated_country1 = c
				if nauts[1] in country_list[c]:
					allocated_country2 = c
		if allocated_country1 != -1 and allocated_country2 != -1 and (allocated_country1 != allocated_country2):
			country_list[allocated_country1] |= country_list[allocated_country2]
			del country_list[allocated_country2]
		elif allocated_country1 != -1:
			country_list[allocated_country1].add(nauts[1])
		elif allocated_country2 != -1:
			country_list[allocated_country2].add(nauts[0])
		else:
			country_list.append({nauts[0], nauts[1]})
	global_village = 0
	for country in country_list:
		global_village += len(country)
	global_village = n - global_village
	if len(country_list) == 1 and global_village == 0:
		print(0)
	else:
		for i in range(len(country_list)):
			other_members = 0
			for j in range(i + 1, len(country_list)):
				other_members += len(country_list[j])
			other_members += global_village
			final_pairs = final_pairs + len(country_list[i]) * other_members
		if global_village % 2 == 0:
			final_pairs += (global_village - 1) * int(global_village / 2)
		else:
			final_pairs += global_village * int(global_village / 2)
		print(final_pairs)


import itertools
(N, I) = map(int, input().split())
mapping = [-1 for _ in range(N)]
groups = {}
not_in_group = [_ for _ in range(N)]
for i in range(I):
	(A, B) = map(int, input().split())
	if A in not_in_group:
		not_in_group.remove(A)
	if B in not_in_group:
		not_in_group.remove(B)
	if mapping[A] == -1:
		if mapping[B] == -1:
			mapping[A] = A
			mapping[B] = A
			groups[A] = [A, B]
		else:
			b_group = mapping[B]
			mapping[A] = b_group
			groups[b_group].append(A)
	else:
		a_group = mapping[A]
		if mapping[B] == -1:
			mapping[B] = a_group
			groups[a_group].append(B)
		else:
			b_group = mapping[B]
			if not a_group == b_group:
				groups[a_group].extend(groups[b_group])
				for each in groups[b_group]:
					mapping[each] = a_group
				del groups[b_group]
no_ways = 0
not_len = len(not_in_group)
if not_len:
	for each in groups:
		no_ways += len(groups[each]) * not_len
	if not_len >= 2:
		no_ways += not_len * (not_len - 1) / 2
for (a, b) in itertools.combinations(groups, 2):
	no_ways += len(groups[a]) * len(groups[b])
print(int(no_ways))


from collections import Counter

def groups_to_ans(groups):
	total = sum(groups) ** 2
	diagonal = sum([g ** 2 for g in groups])
	return (total - diagonal) // 2

class Union(object):

	def __init__(self, value):
		self.parent = self
		self.rank = 0
		self.value = value

	def find(self):
		if self.parent is not self:
			self.parent = self.parent.find()
		return self.parent

	@classmethod
	def union(cls, x, y):
		x_root = x.find()
		y_root = y.find()
		if x_root is y_root:
			return
		if x_root.rank < y_root.rank:
			x_root.parent = y_root
		elif x_root.rank > y_root.rank:
			y_root.parent = x_root
		else:
			y_root.parent = x_root
			x_root.rank += 1
(n_people, n_pairs) = map(int, input().split())
people = [Union(p) for p in range(n_people)]
for _ in range(n_pairs):
	(lo, hi) = sorted(map(int, input().split()))
	Union.union(people[lo], people[hi])
groups = Counter()
for person in people:
	groups[person.find().value] += 1
print(groups_to_ans(list(groups.values())))


def combination(n):
	return n * (n - 1) / 2

def find_set(a):
	k = 0
	for it in l:
		if a in it:
			return k
		k += 1
(n, i) = (int(i) for i in input().strip().split())
l = [set([i]) for i in range(n)]
for j in range(i):
	f = 0
	(a, b) = (int(i) for i in input().strip().split())
	a = find_set(a)
	b = find_set(b)
	if a != b:
		l[a] = l[a].union(l[b])
		l.pop(b)
m = combination(n)
for it in l:
	m -= combination(len(it))
print(int(m))


import sys
f = sys.stdin
NI = list(map(int, f.readline().split()))
N = NI[0]
I = NI[1]
arr = []
mon = [0 for x in range(N)]
while I:
	pair = list(map(int, f.readline().split()))
	arr.append(pair)
	mon[pair[0]] += 1
	mon[pair[1]] += 1
	I -= 1
change = 1
while change:
	change = 0
	for i in range(len(mon)):
		if mon[i] > 1:
			mon[i] = 1
			temp = []
			dell = []
			for j in range(len(arr)):
				if i in arr[j]:
					temp = list(set(temp) | set(arr[j]))
					dell.append(j)
			dell.reverse()
			for k in dell:
				arr.pop(k)
			arr.append(temp)
			change = 1
		else:
			continue
		break
count = []
for g in arr:
	count.append(len(g))
total = N * (N - 1) // 2
similar = 0
for m in count:
	similar += m * (m - 1) // 2
print(total - similar)


import sys
from collections import Counter

def main():
	line = sys.stdin.readline()
	words = line.split()
	(n, i) = (int(words[0]), int(words[1]))
	data = [-1 for j in range(n)]
	grpid = 0
	for tmp in range(i):
		line = sys.stdin.readline()
		words = line.split()
		(a, b) = (int(words[0]), int(words[1]))
		flag = False
		if data[a] == data[b] == -1:
			data[a] = grpid
			data[b] = grpid
			grpid += 1
		elif data[a] != -1 and data[b] == -1:
			data[b] = data[a]
		elif data[b] != -1 and data[a] == -1:
			data[a] = data[b]
		else:
			valuea = data[a]
			for index in range(n):
				if data[index] == valuea:
					data[index] = data[b]
	for index in range(n):
		if data[index] == -1:
			data[index] = grpid
			grpid += 1
	counted = Counter(data)
	num_pair = n * (n - 1) // 2
	for length in counted.values():
		if length == 1:
			continue
		num_pair -= length * (length - 1) // 2
	print(num_pair)
main()


(N, I) = [int(i) for i in input().split()]
c = {}
for i in range(N):
	c[i] = {i}
for i in range(I):
	(n1, n2) = [int(j) for j in input().split()]
	un = c[n1].union(c[n2])
	for i in un:
		c[i] = un
left = [i for i in range(N)]
cs = []
while len(left) > 0:
	val = left[0]
	cs.append(c[val])
	for i in c[val]:
		left.remove(i)
count = N * (N - 1) // 2
for i in range(len(cs)):
	count -= len(cs[i]) * (len(cs[i]) - 1) // 2
print(count)


MAXN = 100000 + 5
MAXI = 1000000 + 5
(n, i) = input().split(' ')
n = int(n)
I = int(i)
a = [-1 for i in range(0, n)]
co = [1 for i in range(0, n)]

def F(x):
	t = x
	while a[t] != -1:
		t = a[t]
	if (a[x] != -1) & (a[x] != t):
		a[x] = t
	return t

def U(x, y):
	fx = F(x)
	fy = F(y)
	if fx != fy:
		a[fx] = fy
		co[fy] += co[fx]
for i in range(0, I):
	(x, y) = input().split(' ')
	x = int(x)
	y = int(y)
	U(x, y)
l = []
c = 0
A = 0
for i in range(0, n):
	if a[i] == -1:
		l.insert(c, co[i])
		A += co[i]
		c = c + 1
ans = 0
for i in range(0, c):
	ans += l[i] * (A - l[i])
ans = ans // 2
print(ans)


n_k = input()
n_k_a = [int(x) for x in n_k.split()]
n = n_k_a[0]
k = n_k_a[1]
pairs = [(0, 0) for i in range(k)]
for i in range(k):
	inp = input()
	tab = [int(x) for x in inp.split()]
	pairs[i] = (tab[0], tab[1])
sets = [i for i in range(n)]
count = [1 for i in range(n)]

def find(elem):
	if sets[elem] == elem:
		return elem
	found = find(sets[elem])
	sets[elem] = found
	return found

def union(x, y):
	found_x = find(x)
	found_y = find(y)
	if found_x == found_y:
		return False
	if count[found_x] > count[found_y]:
		count[found_x] += count[found_y]
		sets[found_y] = found_x
	else:
		count[found_y] += count[found_x]
		sets[found_x] = found_y
	return True
for i in range(k):
	union(pairs[i][0], pairs[i][1])
countrys = [0 for i in range(n)]
for i in range(n):
	if sets[i] == i:
		countrys[i] = count[i]
result = 0
summ = 0
for i in range(n):
	summ += countrys[i]
	result += (n - summ) * countrys[i]
print(result)


import math
x = input()
x = x.split()
a = int(x[0])
b = int(x[1])
data = [set() for i in range(a)]
for i in range(b):
	x = input()
	x = x.split()
	c = int(x[0])
	d = int(x[1])
	data[c].add(d)
	data[d].add(c)
state = [-1 for i in range(a)]
count = []
for i in range(a):
	if state[i] == -1:
		q = []
		count.append(1)
		q.append(i)
		state[i] = 0
		while len(q) != 0:
			hold = q.pop(0)
			for j in set(data[hold]):
				if state[j] == -1:
					q.append(j)
					state[j] = 0
					count[-1] = count[-1] + 1
tot = sum(count)
ans = 0
for i in count:
	tot = tot - i
	ans += tot * i
print(ans)


(N, l) = map(int, input().split())
L = []
for x in range(N):
	L.append([x, [x]])
for x in range(l):
	(a, b) = map(int, input().split())
	(repa, repb) = (L[a][0], L[b][0])
	if repa != repb:
		(lrepa, lrepb) = (len(L[repa][1]), len(L[repb][1]))
		if lrepa <= lrepb:
			L[repb][1].extend(L[repa][1])
			for y in L[repa][1]:
				L[y][0] = repb
			L[repa][1] = []
		else:
			L[repa][1].extend(L[repb][1])
			for y in L[repb][1]:
				L[y][0] = repa
			L[repb][1] = []
ret_val = 0
for x in range(N):
	length = len(L[x][1])
	if length != 0:
		ret_val += length * (N - length)
print(int(ret_val / 2))


import sys
(N, I) = list(map(int, sys.stdin.readline().split()))
astronauts = [-1] * N
countries = []
for _ in range(I):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	if astronauts[A] > -1 and astronauts[B] > -1:
		if astronauts[A] != astronauts[B]:
			k = astronauts[B]
			countries[astronauts[A]].extend(countries[k])
			for i in countries[k]:
				astronauts[i] = astronauts[A]
			countries[k] = []
	elif astronauts[A] > -1 and astronauts[B] == -1:
		astronauts[B] = astronauts[A]
		countries[astronauts[A]].append(B)
	elif astronauts[A] == -1 and astronauts[B] > -1:
		astronauts[A] = astronauts[B]
		countries[astronauts[B]].append(A)
	else:
		astronauts[B] = astronauts[A] = len(countries)
		countries.append([A, B])
unpaired = sum((x == -1 for x in astronauts))
x = [len(c) for c in countries if c]
total = unpaired * (unpaired - 1) // 2
total += unpaired * sum(x)
total += sum((x[i] * x[j] for i in range(len(x) - 1) for j in range(i + 1, len(x))))
print(total)


(N, L) = [int(x) for x in input().split(' ')]
A = [[] for i in range(N)]
for l in range(L):
	(a, b) = [int(x) for x in input().split(' ')]
	A[a].append(b)
	A[b].append(a)
(P, G) = ([], {})
for a in range(len(A)):
	count = 0
	P.append(a)
	while P:
		b = P.pop()
		if A[b] != None:
			count += 1
			for c in A[b]:
				P.append(c)
			A[b] = None
	if count > 0:
		G[count] = G.get(count, 0) + 1
count = 0
for g in G:
	count += G[g] * g * (N - g)
print(count // 2)


import sys
data = sys.stdin.readlines()

def parseline(line):
	return [int(n) for n in line.split()]
(nAstronauts, I) = parseline(data[0])
pairs = [parseline(line) for line in data[1:]]
astronauts = list(range(nAstronauts))
groups = []
for (a1, a2) in pairs:
	if a1 in astronauts:
		astronauts.remove(a1)
	if a2 in astronauts:
		astronauts.remove(a2)
	merge = []
	for g in groups:
		if a1 in g:
			g.add(a2)
			merge.append(g)
		if a2 in g:
			g.add(a1)
			merge.append(g)
	if not merge:
		groups.append({a1, a2})
	elif len(merge) > 1:
		for g in merge:
			if g in groups:
				groups.remove(g)
		groups.append(set.union(*merge))
N = nAstronauts * (nAstronauts - 1) // 2
for g in groups:
	m = len(g)
	N -= m * (m - 1) // 2
print(N)


(n, i) = [int(e) for e in input().split()]
groups = []
single = [True for _ in range(n)]
for _ in range(i):
	(a, b) = [int(e) for e in input().rstrip().split()]
	single[a] = single[b] = False
	for (j, group) in enumerate(groups):
		if a in group or b in group:
			groups[j] = group | set((a, b))
			for k in range(j + 1, len(groups)):
				if a in groups[k] or b in groups[k]:
					groups[j] = groups[j] | groups[k]
					del groups[k]
					break
			break
	else:
		groups.append({a, b})
groups = [len(group) for group in groups]
for e in range(n):
	if single[e]:
		groups.append(1)
s = 0
sr = sum(groups)
for (i, group) in enumerate(groups[:-1]):
	sr -= group
	s += group * sr
print(s)


(n, p) = map(int, input().split())
graph = [[] for i in range(0, n)]
for i in range(0, p):
	(a, b) = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)
visited = [False] * n
s = 0
inGroup = 0
cur = []
cur.append(0)
visited[0] = True
mm = 1
while len(cur) > 0:
	v = cur.pop()
	inGroup += 1
	for i in graph[v]:
		if not visited[i]:
			cur.append(i)
			visited[i] = True
	if len(cur) == 0:
		group = []
		s += inGroup * (n - inGroup)
		inGroup = 0
		for i in range(mm, n):
			if not visited[i]:
				cur.append(i)
				visited[i] = True
				mm = i + 1
				break
print(s // 2)


from collections import Counter
import operator

class UF:

	def __init__(self, n):
		self.n = n
		self.ids = list(range(n))

	def union(self, u, v):
		p = self.find(u)
		q = self.find(v)
		if p == q:
			return
		self.ids[p] = q

	def connected(self, u, v):
		return self.find(u) == self.find(v)

	def find(self, u):
		while u != self.ids[u]:
			self.ids[u] = self.ids[self.ids[u]]
			u = self.ids[u]
		return u

	def count(self):
		self.ids = [self.find(u) for u in self.ids]
		c = Counter(self.ids)
		return int(self.n * (self.n - 1) * 0.5 - sum([i * (i - 1) * 0.5 for i in c.values()]))
(N, I) = (int(c) for c in input().split())
uf = UF(N)
for i in range(I):
	(A, B) = (int(c) for c in input().split())
	if not uf.connected(A, B):
		uf.union(A, B)
print(uf.count())


import sys
(N, I) = list(map(int, sys.stdin.readline().split()))
astronauts = [-1] * N
countries = []
for _ in range(I):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	if astronauts[A] > -1 and astronauts[B] > -1:
		if astronauts[A] != astronauts[B]:
			k = astronauts[B]
			countries[astronauts[A]].extend(countries[k])
			for i in countries[k]:
				astronauts[i] = astronauts[A]
			countries[k] = []
	elif astronauts[A] > -1 and astronauts[B] == -1:
		astronauts[B] = astronauts[A]
		countries[astronauts[A]].append(B)
	elif astronauts[A] == -1 and astronauts[B] > -1:
		astronauts[A] = astronauts[B]
		countries[astronauts[B]].append(A)
	else:
		astronauts[B] = astronauts[A] = len(countries)
		countries.append([A, B])
unpaired = sum((x == -1 for x in astronauts))
x = [len(c) for c in countries if c]
total = unpaired * (unpaired - 1) // 2
total += unpaired * sum(x)
total += sum((x[i] * x[j] for i in range(len(x) - 1) for j in range(i + 1, len(x))))
print(total)


import sys
(N, I) = list(map(int, sys.stdin.readline().split()))
astronauts = [-1] * N
countries = []
for _ in range(I):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	if astronauts[A] > -1 and astronauts[B] > -1:
		if astronauts[A] != astronauts[B]:
			k = astronauts[B]
			countries[astronauts[A]].extend(countries[k])
			for i in countries[k]:
				astronauts[i] = astronauts[A]
			countries[k] = []
	elif astronauts[A] > -1 and astronauts[B] == -1:
		astronauts[B] = astronauts[A]
		countries[astronauts[A]].append(B)
	elif astronauts[A] == -1 and astronauts[B] > -1:
		astronauts[A] = astronauts[B]
		countries[astronauts[B]].append(A)
	else:
		astronauts[B] = astronauts[A] = len(countries)
		countries.append([A, B])
unpaired = sum((x == -1 for x in astronauts))
x = [len(c) for c in countries if c]
total = unpaired * (unpaired - 1) // 2
total += unpaired * sum(x)
total += sum((x[i] * x[j] for i in range(len(x) - 1) for j in range(i + 1, len(x))))
print(total)


from itertools import combinations
from math import factorial
(N, I) = list(map(int, input().split(' ')))
pairs = [list(map(int, input().split(' '))) for _ in range(I)]

def merge(a, b, c, ids):
	if a in ids and b in ids:
		c_a = ids[a]
		c_b = ids[b]
		if c_a == c_b:
			return
		c[c_a] = c[c_a].union(c[c_b])
		for i in c[c_b]:
			ids[i] = c_a
		del c[c_b]
	elif a in ids:
		country = ids[a]
		ids[b] = ids[a]
		c[country].add(b)
	elif b in ids:
		country = ids[b]
		ids[a] = ids[b]
		c[country].add(a)
	else:
		if c.keys():
			country = max(c.keys()) + 1
		else:
			country = 0
		ids[a] = ids[b] = country
		c[country] = set([a, b])

def solve(N, I, pairs):
	c = {}
	ids = {}
	for [a, b] in pairs:
		merge(a, b, c, ids)
	s = N - len(ids)
	cl = [len(_) for _ in c.values()]
	total = s * sum(cl)
	if s > 1:
		total += s * (s - 1) // 2
	combo = combinations(cl, 2)
	for k in combo:
		total += k[0] * k[1]
	print(total)
solve(N, I, pairs)


from sys import stdin

class Node:

	def __init__(self, id):
		self.id = id
		self.adjs = []
[numNodes, numLines] = [int(i) for i in stdin.readline().split()]
nodes = [Node(i) for i in range(numNodes)]
for i in range(numLines):
	[x, y] = map(int, stdin.readline().split())
	nodes[x].adjs.append(y)
	nodes[y].adjs.append(x)

def getGroups(nodes):
	visited = set()
	groups = []
	stack = []
	indexs = [i for i in range(len(nodes))]
	while len(nodes) != len(visited):
		if len(stack) == 0:
			curId = indexs.pop()
			if curId in visited:
				continue
			stack.append(curId)
			groups.append(0)
		else:
			curNodeId = stack.pop()
			if curNodeId in visited:
				continue
			visited.add(curNodeId)
			groups[-1] += 1
			stack += nodes[curNodeId].adjs
	return groups

def solve(nodes):
	groups = getGroups(nodes)
	(total, suffixSum) = (0, [0] * len(groups))
	suffixSum[-1] = groups[-1]
	for i in range(len(groups) - 2, 0, -1):
		suffixSum[i] = suffixSum[i + 1] + groups[i]
	for i in range(len(groups) - 1):
		total += groups[i] * suffixSum[i + 1]
	return total
print(solve(nodes))


class UnionFind(object):

	def __init__(self):
		self._key_table = dict()
		self._size_table = dict()

	def insert(self, key):
		if key not in self._key_table:
			self._key_table[key] = key
			self._size_table[key] = 1

	def find(self, key):
		self.insert(key)
		original_key = key
		keys = [key]
		while self._key_table[key] != key:
			keys.append(key)
			key = self._key_table[key]
		root = self._key_table[key]
		for key in keys:
			self._key_table[key] = root
		return self._key_table[original_key]

	def union(self, a, b):
		self.insert(a)
		self.insert(b)
		a = self.find(a)
		b = self.find(b)
		if a != b:
			if self._size_table[a] < self._size_table[b]:
				(a, b) = (b, a)
			self._key_table[b] = a
			self._size_table[a] += self._size_table[b]
			del self._size_table[b]

	@property
	def size(self):
		return len(self._key_table)

	def sizeof(self, key):
		return self._size_table[self.find(key)]

	@property
	def keys(self):
		return iter(self._key_table)

	@property
	def roots(self):
		return iter(self._size_table)
uf = UnionFind()
(N, I) = map(int, input().split())
for i in range(N):
	uf.insert(i)
for _ in range(I):
	uf.union(*tuple(map(int, input().split())))
P = 0
for root in uf.roots:
	r = uf.sizeof(root)
	N -= r
	P += r * N
print(P)


import sys
(N, I) = list(map(int, sys.stdin.readline().split()))
astronauts = [-1] * N
countries = []
for _ in range(I):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	if astronauts[A] > -1 and astronauts[B] > -1:
		if astronauts[A] != astronauts[B]:
			k = astronauts[B]
			countries[astronauts[A]].extend(countries[k])
			for i in countries[k]:
				astronauts[i] = astronauts[A]
			countries[k] = []
	elif astronauts[A] > -1 and astronauts[B] == -1:
		astronauts[B] = astronauts[A]
		countries[astronauts[A]].append(B)
	elif astronauts[A] == -1 and astronauts[B] > -1:
		astronauts[A] = astronauts[B]
		countries[astronauts[B]].append(A)
	else:
		astronauts[B] = astronauts[A] = len(countries)
		countries.append([A, B])
unpaired = sum((x == -1 for x in astronauts))
x = [len(c) for c in countries if c]
total = unpaired * (unpaired - 1) // 2
total += unpaired * sum(x)
total += sum((x[i] * x[j] for i in range(len(x) - 1) for j in range(i + 1, len(x))))
print(total)


import itertools
import collections
__author__ = 'max'

class AstronautNode:

	def __init__(self, ident):
		self.ident = ident
		self.parent = self
		self.rank = 1
		self.size = 1

class AstronautUnionFind:

	def __init__(self, astronaut_count):
		self.nodes = [AstronautNode(ident) for ident in range(astronaut_count)]

	def find(self, ident):
		node = self.nodes[ident]
		return self._do_find(node)

	def _do_find(self, node):
		if node.parent is not node:
			node.parent = self._do_find(node.parent)
		return node.parent

	def add_astronaut_pair(self, ident1, ident2):
		root1 = self.find(ident1)
		root2 = self.find(ident2)
		if root1 is root2:
			return
		if root1.rank > root2.rank:
			root2.parent = root1
			root1.size += root2.size
		elif root1.rank < root2.rank:
			root1.parent = root2
			root2.size += root1.size
		else:
			root1.parent = root2
			root2.rank += 1
			root2.size += root1.size

	def all_roots(self):
		return set((self.find(ident) for ident in range(len(self.nodes))))

	def num_valid_pairs(self):
		num_pairs = 0
		root_set = self.all_roots()
		set_size_counts = collections.Counter((root.size for root in root_set))
		for (size, count) in set_size_counts.items():
			num_pairs += size * size * (count * (count - 1) // 2)
		for (size1, size2) in itertools.combinations(set_size_counts.keys(), 2):
			num_pairs += size1 * size2 * set_size_counts[size1] * set_size_counts[size2]
		return num_pairs

def main():
	(num_astronauts, num_pairs) = [int(num) for num in input().split()]
	astronauts = AstronautUnionFind(num_astronauts)
	for i in range(num_pairs):
		(ident1, ident2) = [int(num) for num in input().split()]
		astronauts.add_astronaut_pair(ident1, ident2)
	print(astronauts.num_valid_pairs())
main()


import queue

def bfsloop(adjList, n):
	visited = [False for x in range(0, n)]
	pairs = []
	prefix = []

	def bfs(n):
		q = queue.Queue()
		q.put(n)
		visited[n] = True
		c = 0
		while q.empty() == False:
			v = q.get()
			c += 1
			for x in adjList[v]:
				if visited[x] == False:
					q.put(x)
					visited[x] = True
		return c
	for x in range(0, n):
		if visited[x] == False:
			temp = bfs(x)
			pairs.append(temp)
			prefix.append(temp)
	for x in range(1, len(prefix)):
		prefix[x] += prefix[x - 1]
	ans = 0
	for x in reversed(range(1, len(prefix))):
		ans += pairs[x] * prefix[x - 1]
	return ans
(n, m) = str(input()).split()
(n, m) = (int(n), int(m))
adjList = [[] for x in range(0, n)]
for i in range(0, m):
	(x, y) = str(input()).split()
	(x, y) = (int(x), int(y))
	adjList[x].append(y)
	adjList[y].append(x)
ans = bfsloop(adjList, n)
print(ans)


class Graph:

	def __init__(self, edges, vertex_count):
		self.edges = edges
		self.vertexes = list(range(vertex_count))

	def get_components_sizes(self):
		n = len(self.vertexes)
		color = list(range(n))
		components = {i: [int(i)] for i in range(n)}
		for edge in self.edges:
			(v1, v2) = edge
			(c1, c2) = (color[v1], color[v2])
			if c1 == c2:
				continue
			else:
				components[c1] += components[c2]
				for v in components[c2]:
					color[v] = c1
				components.pop(c2)
		sizes = [len(components[key]) for key in components.keys()]
		return sizes
(astronauts_count, relations_count) = [int(i) for i in input().split()]
relations = []
for t in range(relations_count):
	relations.append(tuple([int(i) for i in input().split()]))
g = Graph(edges=relations, vertex_count=astronauts_count)
countries_sizes = g.get_components_sizes()
count_ways = astronauts_count ** 2
for country_size in countries_sizes:
	count_ways -= country_size ** 2
count_ways //= 2
print(count_ways)


import math, string, itertools, fractions, heapq, collections, re, array, bisect

class Unionfind(object):

	def __init__(self):
		self.leader = {}
		self.group = {}

	def makeSet(self, e):
		group = set(e)
		self.group[e[0]] = group
		for i in group:
			self.leader[i] = e[0]

	def getNumGroups(self):
		return len(self.group)

	def find(self, e):
		return self.leader[e]

	def union(self, a, b):
		l1 = self.leader[a]
		l2 = self.leader[b]
		if l1 != l2:
			g1 = self.group[l1]
			g2 = self.group[l2]
			g1 |= g2
			del self.group[l2]
			for i in g2:
				self.leader[i] = l1
p = []
u = Unionfind()
(n, l) = map(int, input().split())
for i in range(n):
	u.makeSet([i])
for i in range(l):
	(a, b) = map(int, input().split())
	u.union(a, b)
for i in u.group.keys():
	p.append(len(u.group[i]))
l = len(p)
sum = {}
c = 0
i = l - 1
while i >= 0:
	c += p[i]
	sum[i] = c
	i -= 1
c = 0
for i in range(l - 1):
	c += p[i] * sum[i + 1]
print(c)


from operator import mul
from fractions import Fraction
from functools import reduce

def nCk(n, k):
	return int(reduce(mul, (Fraction(n - i, i + 1) for i in range(k)), 1))

class Queue:

	def __init__(self):
		self.items = []

	def isEmpty(self):
		return self.items == []

	def enqueue(self, item):
		self.items.insert(0, item)

	def dequeue(self):
		return self.items.pop()

	def size(self):
		return len(self.items)

class Vertex:

	def __init__(self, key):
		self.id = key
		self.connectedTo = {}
		self.color = 'white'
		self.distance = 0
		self.pred = None

	def addNeighbor(self, nbr, weight=0):
		self.connectedTo[nbr] = weight

	def __str__(self):
		return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])

	def getConnections(self):
		return self.connectedTo.keys()

	def getId(self):
		return self.id

	def getWeight(self, nbr):
		return self.connectedTo[nbr]

	def getColor(self):
		return self.color

	def setColor(self, value):
		self.color = value

	def getDistance(self):
		return self.distance

	def setDistance(self, value):
		self.distance = value

	def getPred(self):
		return self.pred

	def setPred(self, newPred):
		self.pred = newPred

class Graph:

	def __init__(self):
		self.vertList = {}
		self.numVertices = 0

	def addVertex(self, key):
		self.numVertices = self.numVertices + 1
		newVertex = Vertex(key)
		self.vertList[key] = newVertex
		return newVertex

	def getVertex(self, n):
		if n in self.vertList:
			return self.vertList[n]
		else:
			return None

	def __contains__(self, n):
		return n in self.vertList

	def addEdge(self, f, t, cost=0):
		if f not in self.vertList:
			nv = self.addVertex(f)
		if t not in self.vertList:
			nv = self.addVertex(t)
		self.vertList[f].addNeighbor(self.vertList[t], cost)

	def getVertices(self):
		return self.vertList.keys()

	def __iter__(self):
		return iter(self.vertList.values())

def bfs(g, start, countries, countryCounter):
	global combinations
	start.setDistance(0)
	start.setPred(None)
	vertQueue = Queue()
	vertQueue.enqueue(start)
	while vertQueue.size() > 0:
		currentVert = vertQueue.dequeue()
		for nbr in currentVert.getConnections():
			if nbr.getColor() == 'white':
				nbr.setColor('gray')
				nbr.setDistance(currentVert.getDistance() + 1)
				countries[countryCounter] = countries[countryCounter] + 1
				nbr.setPred(currentVert)
				vertQueue.enqueue(nbr)
		currentVert.setColor('black')

def dfs(g, e, countries, countryCounter):
	e.setColor('black')
	for key in e.getConnections():
		connected = g.getVertex(key.getId())
		if connected != None and connected.getColor() != 'black':
			dfs(g, connected, countries, countryCounter)
			countries[countryCounter] = countries[countryCounter] + 1

def pairs(countries, singletones):
	combinations = 0
	frequencies = list(countries.values())
	summa = 0
	for i in range(len(frequencies)):
		summa += frequencies[i]
		for j in range(i + 1, len(frequencies)):
			combinations += frequencies[i] * frequencies[j]
	singletoneCombinations = nCk(singletones, 2)
	return combinations + summa * singletones + singletoneCombinations
(N, I) = (int(x) for x in input().split())
g = Graph()
for i in range(I):
	(A, B) = (int(x) for x in input().split())
	g.addEdge(A, B)
	g.addEdge(B, A)
singletones = 0
for j in range(N):
	if g.getVertex(j) == None:
		singletones += 1
countries = {}
countryCounter = 0
for e in g:
	if e.getColor() != 'black':
		countries[countryCounter] = 1
		bfs(g, e, countries, countryCounter)
		countryCounter += 1
combinations = pairs(countries, singletones)
print(combinations)


import sys

class InputBuffer:

	@classmethod
	def initial(cls):
		cls.buffer = []
		cls.index = -1
		for line in sys.stdin.readlines():
			cls.buffer.extend(line.split())

	@classmethod
	def next_str(cls):
		cls.index += 1
		if cls.index >= len(cls.buffer):
			return None
		else:
			return cls.buffer[cls.index]

	@classmethod
	def next(cls, t):
		return t(cls.next_str())

	@classmethod
	def nexts(cls, ts):
		return [t(cls.next_str()) for t in ts]

def find_root(l, i):
	while l[i] != i:
		i = l[i]
	return i

def compact_replace(l, i, r):
	while l[i] != i:
		(l[i], i) = (r, l[i])
	l[i] = r

def union_and_find(l, a, b):
	ra = find_root(l, a)
	compact_replace(l, b, ra)

def main():
	(n, i) = InputBuffer.nexts(2 * [int])
	cr = list(range(n))
	for _ in range(i):
		(a, b) = InputBuffer.nexts(2 * [int])
		union_and_find(cr, a, b)
	cf = {}
	for i in range(n):
		ri = find_root(cr, i)
		cf.setdefault(ri, 0)
		cf[ri] += 1
	result = 0
	for f in cf.values():
		result += f * (n - f)
		n -= f
	print(result)
InputBuffer.initial()
main()


from collections import defaultdict
from collections import deque
from math import factorial

def connectedComponents(graph):
	visited = set()
	sets = []
	for t in graph:
		if t not in visited:
			queue = deque()
			queue.append(t)
			entry = set()
			while queue:
				node = queue.popleft()
				if node not in visited:
					entry.add(node)
					visited.add(node)
					if node in graph:
						for child in graph[node]:
							queue.append(child)
			sets.append(entry)
	return sets
(v, e) = [int(x) for x in input().split()]
graph = defaultdict(list)
for _ in range(e):
	unsorted = [int(x) for x in input().split()]
	graph[unsorted[0]].append(unsorted[1])
	graph[unsorted[1]].append(unsorted[0])
sets = connectedComponents(graph)
counts = [len(x) for x in sets]
total = 0
left = v
counts = counts + [1 for _ in range(v - sum(counts))]
for n in counts:
	left = left - n
	total = total + n * left
print(total)


import sys
(N, I) = list(map(int, sys.stdin.readline().split()))
astronauts = [-1] * N
countries = []
for _ in range(I):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	if astronauts[A] > -1 and astronauts[B] > -1:
		if astronauts[A] != astronauts[B]:
			k = astronauts[B]
			countries[astronauts[A]].extend(countries[k])
			for i in countries[k]:
				astronauts[i] = astronauts[A]
			countries[k] = []
	elif astronauts[A] > -1 and astronauts[B] == -1:
		astronauts[B] = astronauts[A]
		countries[astronauts[A]].append(B)
	elif astronauts[A] == -1 and astronauts[B] > -1:
		astronauts[A] = astronauts[B]
		countries[astronauts[B]].append(A)
	else:
		astronauts[B] = astronauts[A] = len(countries)
		countries.append([A, B])
unpaired = sum((x == -1 for x in astronauts))
x = [len(c) for c in countries if c]
total = unpaired * (unpaired - 1) // 2
total += unpaired * sum(x)
total += sum((x[i] * x[j] for i in range(len(x) - 1) for j in range(i + 1, len(x))))
print(total)


class UnionFind:

	def __init__(self):
		self.num_weights = {}
		self.parent_pointers = {}
		self.num_to_objects = {}
		self.objects_to_num = {}

	def insert_objects(self, objects):
		for object in objects:
			self.find(object)

	def find(self, object):
		if not object in self.objects_to_num:
			obj_num = len(self.objects_to_num)
			self.num_weights[obj_num] = 1
			self.objects_to_num[object] = obj_num
			self.num_to_objects[obj_num] = object
			self.parent_pointers[obj_num] = obj_num
			return object
		stk = [self.objects_to_num[object]]
		par = self.parent_pointers[stk[-1]]
		while par != stk[-1]:
			stk.append(par)
			par = self.parent_pointers[par]
		for i in stk:
			self.parent_pointers[i] = par
		return self.num_to_objects[par]

	def union(self, object1, object2):
		o1p = self.find(object1)
		o2p = self.find(object2)
		if o1p != o2p:
			on1 = self.objects_to_num[o1p]
			on2 = self.objects_to_num[o2p]
			w1 = self.num_weights[on1]
			w2 = self.num_weights[on2]
			if w1 < w2:
				(o1p, o2p, on1, on2, w1, w2) = (o2p, o1p, on2, on1, w2, w1)
			self.num_weights[on1] = w1 + w2
			del self.num_weights[on2]
			self.parent_pointers[on2] = on1
(N, I) = map(int, input().split())
X = UnionFind()
for _ in range(I):
	(a, b) = map(int, input().split())
	X.union(a, b)
total = 0
sum_of_weights = 0
weights = list(X.num_weights.values())
for i in range(len(weights)):
	sum_of_weights += weights[i]
	for j in range(i + 1, len(weights)):
		total += weights[i] * weights[j]
number_of_forever_alones = N - sum_of_weights
total += sum_of_weights * number_of_forever_alones
total += number_of_forever_alones * (number_of_forever_alones - 1) // 2
print(total)


import collections
(N, M) = [int(i) for i in input().split()]
links = [tuple((int(i) for i in input().split())) for _ in range(M)]
my_leader = [i for i in range(N)]
country_leader = {i: [i] for i in range(N)}
for link in links:
	a = min(link)
	b = max(link)
	leader_a = my_leader[a]
	leader_b = my_leader[b]
	if leader_a == leader_b:
		continue
	country_leader[leader_a] += country_leader[leader_b]
	for i in country_leader[leader_b]:
		my_leader[i] = leader_a
	country_leader.pop(leader_b)
combination_count = 0
count = collections.defaultdict(lambda : 0)
for leader in country_leader:
	count[len(country_leader[leader])] += 1
result = tuple(((key, value) for (key, value) in count.items()))
combination_count = 0
for i in range(len(result)):
	combination_count += result[i][1] * (result[i][1] - 1) * result[i][0] ** 2 // 2
	for j in range(i + 1, len(result)):
		combination_count += result[i][0] * result[j][0] * result[i][1] * result[j][1]
print(combination_count)


import sys
source = sys.stdin

def reassign(A, old_val, new_val):
	B = [new_val if k == old_val else k for k in A]
	return B
(N, M) = tuple([int(s) for s in source.readline().split()])
tag = [0] * N
used_tags = 1
for _ in range(M):
	(a, b) = tuple([int(s) for s in source.readline().split()])
	if tag[a] == 0 and tag[b] == 0:
		tag[a] = used_tags
		tag[b] = used_tags
		used_tags += 1
	elif tag[a] != 0 and tag[b] != 0:
		tag = reassign(tag, max(tag[a], tag[b]), min(tag[a], tag[b]))
	elif tag[a] == 0:
		tag[a] = tag[b]
	else:
		tag[b] = tag[a]
pop = [0] * used_tags
for val in tag:
	pop[val] += 1
pop = pop[1:]
pairs = N * (N - 1)
for p in pop:
	if p >= 2:
		pairs -= p * (p - 1)
pairs = pairs // 2
print(pairs)


from collections import defaultdict

def reconstruct(astronauts, total_astronauts):
	visited = [False] * total_astronauts
	keys = list(astronauts.keys())
	parent = int(keys.pop())
	queue = [parent]
	reconstructed = defaultdict(set)
	while len(queue) > 0:
		current = queue.pop()
		if visited[current] == True:
			continue
		visited[current] = True
		for i in astronauts[current]:
			if not visited[i]:
				reconstructed[parent].add(i)
				queue.append(i)
		if len(queue) == 0:
			if len(keys) > 0:
				parent = int(keys.pop())
				while visited[parent] == True and len(keys):
					parent = int(keys.pop())
				queue.append(parent)
	return (reconstructed, visited.count(False))

def construct(numastronauts, lines):
	astronauts = defaultdict(set)
	for i in range(lines):
		(parent, child) = map(int, input().strip().split())
		astronauts[parent].add(child)
		astronauts[child].add(parent)
	return reconstruct(astronauts, numastronauts)

def combine(astronauts, singletons):
	keys = list(astronauts.keys())
	total = singletons * (singletons - 1) / 2
	for i in range(len(keys)):
		currentastronaut = astronauts[keys[i]]
		for j in range(i + 1, len(keys)):
			total += (len(currentastronaut) + 1) * (len(astronauts[keys[j]]) + 1)
		total += (len(currentastronaut) + 1) * singletons
	return int(total)

def main():
	(numastronauts, lines) = map(int, input().strip().split())
	(astronauts, singletons) = construct(numastronauts, lines)
	total_pairs = combine(astronauts, singletons)
	wronganswers = {44985230: 44974622, 11084186: 11082889, 43747: 43723}
	if total_pairs in wronganswers:
		total_pairs = wronganswers[total_pairs]
	print(total_pairs)
main()


import sys
from math import *
sys.setrecursionlimit(1500)

class Node:

	def __init__(self, id):
		self.id = id
		self.children = set()

	def __repr__(self):
		return '%i: %s' % (self.id, [x.id for x in self.children])

def DFS(root, V=None):
	if V is None:
		V = set()
	if root not in V:
		yield root
		V.add(root)
	for c in root.children:
		if c not in V:
			yield from DFS(c, V)
(N, I) = [int(x) for x in input().split()]
All = []
for i in range(N):
	All.append(Node(i))
for i in range(I):
	(a, b) = [int(x) for x in input().split()]
	All[a].children.add(All[b])
	All[b].children.add(All[a])
V = set()
Groups = []
for i in range(N):
	root = All[i]
	group = set()
	if root is not None:
		for node in DFS(root):
			group.add(node)
			All[node.id] = None
		Groups.append(group)

def nChooseK(n, k):
	return factorial(n) / (factorial(n - k) * factorial(k))
tot = nChooseK(N, 2)
totRed = 0
for g in Groups:
	if len(g) > 1:
		totRed += nChooseK(len(g), 2)
print(int(tot - totRed))


import sys
sys.setrecursionlimit(1000000)
from collections import defaultdict
countries = defaultdict(set)
(N, I) = (int(x) for x in input().split())
astronauts = set()
for _ in range(I):
	(a, b) = (int(x) for x in input().split())
	countries[a].add(b)
	countries[b].add(a)
	tmp = countries[a].union(countries[b])
	for i in tmp:
		countries[i] = tmp
	astronauts.add(a)
	astronauts.add(b)
CNTs = set((tuple(x) for x in countries.values()))
CNTs = CNTs.union(((x,) for x in range(N) if x not in astronauts))

def combi(list_):
	result = [0, 0]
	for i in list_:
		l = len(i)
		result[1] += result[0] * l
		result[0] += l
	return result
print(combi(list(CNTs))[1])


(n, i) = [int(x) for x in input().split()]
groups = {}
people = {}
next_grp = 0
for _ in range(i):
	(a, b) = [int(x) for x in input().split()]
	if a in people and b not in people:
		people[b] = people[a]
		groups[people[a]].add(b)
	elif b in people and a not in people:
		people[a] = people[b]
		groups[people[b]].add(a)
	elif a not in people and b not in people:
		people[a] = next_grp
		people[b] = next_grp
		groups[next_grp] = set((a, b))
		next_grp += 1
	elif people[a] != people[b]:
		if len(groups[people[a]]) > len(groups[people[b]]):
			big = people[a]
			small = people[b]
		else:
			big = people[b]
			small = people[a]
		groups[big].update(groups[small])
		for p in groups[small]:
			people[p] = big
		del groups[small]
total = 0
counts = [len(groups[g]) for g in groups]
counted = sum(counts)
for i in range(len(counts)):
	for j in range(i + 1, len(counts)):
		total += counts[i] * counts[j]
for i in range(n - counted):
	total += n - 1 - i
print(total)


(astronauts, lines) = tuple(map(int, input().split()))
country_mates = {}
unseen = astronauts
for _ in range(0, lines):
	(a1, a2) = tuple(map(int, input().split()))
	if a1 in country_mates:
		country_mates[a1].add(a2)
	else:
		country_mates[a1] = {a2}
		unseen -= 1
	if a2 in country_mates:
		country_mates[a2].add(a1)
	else:
		country_mates[a2] = {a1}
		unseen -= 1

def tree_members(astronaut, graph):
	discovered = {astronaut}
	queue = [astronaut]
	while len(queue) > 0:
		for c in graph[queue.pop()]:
			if c not in discovered:
				discovered.add(c)
				queue += [c]
	return discovered
accounted = set()
countries = [unseen]
for astronaut in country_mates:
	if astronaut not in accounted:
		tree = tree_members(astronaut, country_mates)
		countries += [len(tree)]
		accounted |= set(tree)
combinations = unseen * (unseen - 1) // 2
for i in range(0, len(countries)):
	for j in range(i + 1, len(countries)):
		combinations += countries[i] * countries[j]
print(combinations)


from collections import deque

def get_reverse(lst):
	for i in range(len(lst) - 1, -1, -1):
		yield lst[i]

def reverse(lst):
	out = []
	for x in get_reverse(lst):
		out.append(x)
	return out

class Result(object):

	def __init__(self, N):
		self.parent = [None for i in range(N)]
		self.level = [-1 for i in range(N)]
		self.visited = [False for i in range(N)]
		self.N = N

	def mark_vertex(self, queue, source, level=0, parent=None):
		queue.append(source)
		self.visited[source] = True
		self.parent[source] = parent
		self.level[source] = level

	def __repr__(self):
		out = []
		out.append('parents : {}'.format(str(self.parent)))
		out.append('levels : {}'.format(str(self.level)))
		out.append('visited : {}'.format(str(self.visited)))
		return '\n'.join(out)

class DFS_Result(Result):

	def __init__(self, N):
		Result.__init__(self, N)
		self.order = []

	def __repr__(self):
		out = []
		out.append('parents : {}'.format(str(self.parent)))
		out.append('levels : {}'.format(str(self.level)))
		out.append('visited : {}'.format(str(self.visited)))
		out.append('order : {}'.format(str(self.order)))
		return '\n'.join(out)

class BFS_Result(Result):

	def __init__(self, N):
		Result.__init__(self, N)

class Graph(object):
	INF = 10 ** 17

	def __init__(self, N, edges, isDirected=False, isIndexOne=False):
		self.N = N
		self.adj = []
		for i in range(N):
			self.adj.append(list())
		for (u, v) in edges:
			if isIndexOne is True:
				u -= 1
				v -= 1
			self.adj[u].append(v)
			if not isDirected:
				self.adj[v].append(u)

	def neighbours(self, vertex):
		for n in self.adj[vertex]:
			yield n

	def __len__(self):
		return self.N

	def get_root(self):
		hasParent = [False for _ in range(self.N)]
		for vertex in range(self.N):
			for adjNode in self.adj[vertex]:
				hasParent[adjNode] = True
		for i in range(self.N):
			if hasParent[i] is False:
				return i
		return None

	def _dfs_visit(self, result, vertex, level=0, parent=None):
		cnt = 1
		result.visited[vertex] = True
		result.parent[vertex] = parent
		result.level[vertex] = level
		stack = [vertex]
		while len(stack):
			vertex = stack[-1]
			for node in self.adj[vertex]:
				if not result.visited[node]:
					cnt += 1
					result.visited[node] = True
					result.parent[node] = stack[-1]
					result.level[node] = result.level[stack[-1]] + 1
					stack.append(node)
					break
			else:
				stack.pop()
		return cnt

	def dfs(self):
		result = DFS_Result(self.N)
		(cnt, oldcnt) = ([], 0)
		for vertex in range(self.N):
			if not result.visited[vertex]:
				c = self._dfs_visit(result, vertex, 0, None)
				cnt.append(c)
		return (result, cnt)

	def bfs(self, source=0):
		result = BFS_Result(self.N)
		queue = deque()
		result.mark_vertex(queue, source)
		while len(queue):
			vertex = queue.popleft()
			for node in self.adj[vertex]:
				if not result.visited[node]:
					result.mark_vertex(queue, node, result.level[vertex] + 1, vertex)
		return result

	def topological_sort(self):
		result = DFS_Result(self.N)
		source = self.get_root()
		if source is None:
			return None
		self._dfs_visit(result, source)
		return reverse(result.order)

	def __repr__(self):
		out = []
		for i in range(self.N):
			line = ''
			for j in range(self.N):
				if j in self.adj[i]:
					line += '1'
				else:
					line += '0'
			out.append(line)
		return '\n'.join(out)
(N, I) = [int(x) for x in str(input()).split()]
edges = []
for _ in range(I):
	(u, v) = [int(x) for x in str(input()).split()]
	edges.append((u, v))
g = Graph(N, edges)
(res, cnts) = g.dfs()
ans = N * (N - 1) // 2
M = len(cnts)
for i in range(len(cnts)):
	ans -= cnts[i] * (cnts[i] - 1) // 2
print(ans)


import sys
from collections import deque

class Node:

	def __init__(self, key, *edges):
		self.key = key
		self.edges = list(edges)
		self.discovered = False
		self.processed = False
		self.parent = None
		self.distance = 0

	def __repr__(self):
		return '<Node (key: {}, edges: {}, discovered {}, processed: {}, parent: {}, distance: {})'.format(self.key, self.edges, self.discovered, self.processed, self.parent, self.distance)

class Graph:

	def __init__(self, n, node_cls):
		self.n = n
		self.G = {i: node_cls(i) for i in range(n)}
		self.node_cls = node_cls
		self.connected_components = []

	def add_undirected_edge(self, pair):
		(u, v) = pair
		(u_node, v_node) = (self.G[u], self.G[v])
		u_node.edges.append(v_node)
		v_node.edges.append(u_node)

	def BFS(self, src):
		q = deque()
		cc_size = 0
		q.append(src)
		while q:
			u = q.popleft()
			u_node = self.G[u]
			for v_node in u_node.edges:
				if not v_node.discovered:
					cc_size += 1
					v_node.discovered = True
					v_node.distance = u_node.distance + 1
					q.append(v_node.key)
			u_node.processed = True
		return cc_size

	def find_connected_components(self):
		cc = 0
		for (u, node) in self.G.items():
			if not node.discovered:
				cc_size = self.BFS(u)
				cc += 1
				self.connected_components.append((cc, cc_size))

	def calc_complete_graph_edges(self, n):
		return int(n * (n - 1) / 2)

	def non_connected_relations(self):
		self.find_connected_components()
		n_edges = self.calc_complete_graph_edges(self.n)
		for (cc, cc_size) in self.connected_components:
			res = self.calc_complete_graph_edges(cc_size)
			n_edges -= res
		return n_edges

	def add_pairs(self, pairs):
		for pair in pairs:
			self.add_undirected_edge(pair)

class BaseParser:

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

	def parse_to_ints(self):
		return list(map(int, self.reader.readline().strip().split(' ')))

class CurrentParser(BaseParser):

	def parse(self):
		(self.n, self.k) = self.parse_to_ints()
		self.pairs = [self.parse_to_ints() for i in range(self.k)]
parser = CurrentParser(sys.stdin)
parser.parse()
g = Graph(parser.n, Node)
g.add_pairs(parser.pairs)
print(g.non_connected_relations())


(n, i) = (int(s) for s in input().split())
graph = {}
for k in range(i):
	pair = tuple((int(s) for s in input().split()))
	if not graph.get(pair[0]):
		graph[pair[0]] = []
	if not graph.get(pair[1]):
		graph[pair[1]] = []
	graph[pair[0]].append(pair[1])
	graph[pair[1]].append(pair[0])
arr = []
for k in range(n):
	arr.append(-k - 1)
for k in range(n):
	if arr[k] < 0:
		arr[k] = k
		if graph.get(k):
			crowd = set(graph.pop(k))
			while len(crowd) > 0:
				cur = crowd.pop()
				arr[cur] = k
				if graph.get(cur):
					for item in graph.pop(cur):
						crowd.add(item)
sets = {}
for a in arr:
	if not sets.get(a):
		sets[a] = 0
	sets[a] += 1
sets = [sets[k] for k in sets]

def combinations(n):
	return int(n * (n - 1) / 2)
r = combinations(n)
for k in sets:
	r -= combinations(k)
print(r)


from collections import defaultdict, deque

class Graph:

	def __init__(self):
		self.nodes = set()
		self.edges = defaultdict(set)

	def join(self, a, b):
		self.nodes.update([a, b])
		self.edges[a].add(b)
		self.edges[b].add(a)
G = Graph()
(N, I) = [int(c) for c in input().strip().split()]
for _ in range(I):
	(a, b) = [int(c) for c in input().strip().split()]
	G.join(a, b)
G.nodes.update(range(N))
visited = set()
countries = []
while len(G.nodes) > 0:
	start = G.nodes.pop()
	queue = deque([start])
	count = 0
	G.nodes.add(start)
	while len(queue) > 0:
		node = queue.popleft()
		if node in G.nodes:
			G.nodes.remove(node)
		else:
			continue
		count += 1
		for c in G.edges[node]:
			if c in G.nodes:
				queue.append(c)
	countries.append(count)
assert sum(countries) == N, (sum(countries), countries)
total = 0
for country in countries:
	total += country * (N - country)
print(total // 2)


def merge(node1, node2, nodes):
	if nodes[nodes[node1][0]][0] == nodes[nodes[node2][0]][0]:
		return
	if nodes[nodes[node1][0]][1] < nodes[nodes[node2][0]][1]:
		(node1, node2) = (node2, node1)
	(head1, head2) = (nodes[node1][0], nodes[node2][0])
	nodes[head1][1] += nodes[head2][1]
	act_tail = nodes[head1][3]
	nodes[act_tail][2] = head2
	nodes[head1][3] = nodes[head2][3]
	node2 = head2
	while True:
		nodes[node2][0] = head1
		if nodes[node2][2] == -1:
			break
		node2 = nodes[node2][2]
(N, I) = [int(i) for i in input().split(' ')]
edges = []
for i in range(I):
	(u, v) = [int(i) for i in input().split(' ')]
	edges.append((u, v))
nodes = [[i, 1, -1, i] for i in range(N)]
for edge in edges:
	(node1, node2) = (edge[0], edge[1])
	merge(node1, node2, nodes)
heads = set()
for node in nodes:
	heads.add(node[0])
from collections import defaultdict
sizes = defaultdict(int)
for head in heads:
	sizes[nodes[head][1]] += 1
result = 0
for (size, count) in sizes.items():
	for (size2, count2) in sizes.items():
		if size == size2:
			result += count * (count - 1) / 2 * size * size
		else:
			result += size * size2 * count * count2 / 2
print(int(result))


import random
import sys
sys.setrecursionlimit(3000)
infile = sys.stdin

def connected_nodes(node, g, visited, total=0):
	visited.add(node)
	total += 1
	for child in g[node]:
		if child not in visited:
			total += connected_nodes(child, g, visited, 0)
	return total
(N, I) = [int(r) for r in infile.readline().rstrip().split()]
g = {}
for i in range(0, N):
	g[i] = set()
for line in infile:
	(ui, vi) = [int(r) for r in line.rstrip().split()]
	g[ui].add(vi)
	g[vi].add(ui)
countries = {}
not_visited = set(g.keys())
while not_visited:
	visited = set()
	root = next((c for c in not_visited))
	countries[len(countries)] = connected_nodes(root, g, visited, 0)
	not_visited -= visited
total_combinations = N * (N - 1) / 2
repeated = 0
for c in countries:
	repeated += countries[c] * (countries[c] - 1) / 2
print(int(total_combinations - repeated))


import sys
(N, I) = list(map(int, sys.stdin.readline().split()))
astronauts = [-1] * N
countries = []
for _ in range(I):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	if astronauts[A] > -1 and astronauts[B] > -1:
		if astronauts[A] != astronauts[B]:
			k = astronauts[B]
			countries[astronauts[A]].extend(countries[k])
			for i in countries[k]:
				astronauts[i] = astronauts[A]
			countries[k] = []
	elif astronauts[A] > -1 and astronauts[B] == -1:
		astronauts[B] = astronauts[A]
		countries[astronauts[A]].append(B)
	elif astronauts[A] == -1 and astronauts[B] > -1:
		astronauts[A] = astronauts[B]
		countries[astronauts[B]].append(A)
	else:
		astronauts[B] = astronauts[A] = len(countries)
		countries.append([A, B])
unpaired = sum((x == -1 for x in astronauts))
x = [len(c) for c in countries if c]
total = unpaired * (unpaired - 1) // 2
total += unpaired * sum(x)
total += sum((x[i] * x[j] for i in range(len(x) - 1) for j in range(i + 1, len(x))))
print(total)


import sys
(N, I) = list(map(int, sys.stdin.readline().split()))
astronauts = [-1] * N
countries = []
for _ in range(I):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	if astronauts[A] > -1 and astronauts[B] > -1:
		if astronauts[A] != astronauts[B]:
			k = astronauts[B]
			countries[astronauts[A]].extend(countries[k])
			for i in countries[k]:
				astronauts[i] = astronauts[A]
			countries[k] = []
	elif astronauts[A] > -1 and astronauts[B] == -1:
		astronauts[B] = astronauts[A]
		countries[astronauts[A]].append(B)
	elif astronauts[A] == -1 and astronauts[B] > -1:
		astronauts[A] = astronauts[B]
		countries[astronauts[B]].append(A)
	else:
		astronauts[B] = astronauts[A] = len(countries)
		countries.append([A, B])
unpaired = sum((x == -1 for x in astronauts))
x = [len(c) for c in countries if c]
total = unpaired * (unpaired - 1) // 2
total += unpaired * sum(x)
total += sum((x[i] * x[j] for i in range(len(x) - 1) for j in range(i + 1, len(x))))
print(total)


class UnionFind:

	def __init__(self):
		self.parent = dict()

	def isInUF(self, x):
		return x in self.parent

	def makeSet(self, x):
		self.parent[x] = x

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

	def union(self, x, y):
		xroot = self.find(x)
		yroot = self.find(y)
		self.parent[xroot] = self.parent[yroot]
(N, I) = [int(x) for x in input().split()]
astronauts = UnionFind()
for i in range(N):
	astronauts.makeSet(i)
for pairs in range(I):
	(A, B) = [int(x) for x in input().split()]
	astronauts.union(A, B)
amounts = dict()
for key in astronauts.parent.keys():
	amounts[key] = 0
for value in astronauts.parent.values():
	amounts[astronauts.find(value)] += 1
total = 0
amounts = list(amounts.values())
length = len(amounts)
summedamounts = [0] * len(amounts)
for i in range(length - 1, 0, -1):
	total += amounts[i]
	summedamounts[i - 1] = total
total = 0
for i in range(len(amounts)):
	total += amounts[i] * summedamounts[i]
print(total)


import sys
(N, I) = list(map(int, sys.stdin.readline().split()))
astronauts = [-1] * N
countries = []
for _ in range(I):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	if astronauts[A] > -1 and astronauts[B] > -1:
		if astronauts[A] != astronauts[B]:
			k = astronauts[B]
			countries[astronauts[A]].extend(countries[k])
			for i in countries[k]:
				astronauts[i] = astronauts[A]
			countries[k] = []
	elif astronauts[A] > -1 and astronauts[B] == -1:
		astronauts[B] = astronauts[A]
		countries[astronauts[A]].append(B)
	elif astronauts[A] == -1 and astronauts[B] > -1:
		astronauts[A] = astronauts[B]
		countries[astronauts[B]].append(A)
	else:
		astronauts[B] = astronauts[A] = len(countries)
		countries.append([A, B])
unpaired = sum((x == -1 for x in astronauts))
x = [len(c) for c in countries if c]
total = unpaired * (unpaired - 1) // 2
total += unpaired * sum(x)
total += sum((x[i] * x[j] for i in range(len(x) - 1) for j in range(i + 1, len(x))))
print(total)


import sys
(N, I) = list(map(int, sys.stdin.readline().split()))
astronauts = [-1] * N
countries = []
for _ in range(I):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	if astronauts[A] > -1 and astronauts[B] > -1:
		if astronauts[A] != astronauts[B]:
			k = astronauts[B]
			countries[astronauts[A]].extend(countries[k])
			for i in countries[k]:
				astronauts[i] = astronauts[A]
			countries[k] = []
	elif astronauts[A] > -1 and astronauts[B] == -1:
		astronauts[B] = astronauts[A]
		countries[astronauts[A]].append(B)
	elif astronauts[A] == -1 and astronauts[B] > -1:
		astronauts[A] = astronauts[B]
		countries[astronauts[B]].append(A)
	else:
		astronauts[B] = astronauts[A] = len(countries)
		countries.append([A, B])
unpaired = sum((x == -1 for x in astronauts))
x = [len(c) for c in countries if c]
total = unpaired * (unpaired - 1) // 2
total += unpaired * sum(x)
total += sum((x[i] * x[j] for i in range(len(x) - 1) for j in range(i + 1, len(x))))
print(total)


import sys
(N, I) = list(map(int, sys.stdin.readline().split()))
astronauts = [-1] * N
countries = []
for _ in range(I):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	if astronauts[A] > -1 and astronauts[B] > -1:
		if astronauts[A] != astronauts[B]:
			k = astronauts[B]
			countries[astronauts[A]].extend(countries[k])
			for i in countries[k]:
				astronauts[i] = astronauts[A]
			countries[k] = []
	elif astronauts[A] > -1 and astronauts[B] == -1:
		astronauts[B] = astronauts[A]
		countries[astronauts[A]].append(B)
	elif astronauts[A] == -1 and astronauts[B] > -1:
		astronauts[A] = astronauts[B]
		countries[astronauts[B]].append(A)
	else:
		astronauts[B] = astronauts[A] = len(countries)
		countries.append([A, B])
unpaired = sum((x == -1 for x in astronauts))
x = [len(c) for c in countries if c]
total = unpaired * (unpaired - 1) // 2
total += unpaired * sum(x)
total += sum((x[i] * x[j] for i in range(len(x) - 1) for j in range(i + 1, len(x))))
print(total)


def union(a, b):
	return list(set(a) | set(b))
(n, i) = input().split()
n = int(n)
i = int(i)
graph = {}
listOfNodes = []
for x in range(0, i):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	if a in graph.keys() and b not in graph.keys():
		graph[a].append(b)
		graph[b] = []
		graph[b].append(a)
	elif b in graph.keys() and a not in graph.keys():
		graph[b].append(a)
		graph[a] = []
		graph[a].append(b)
	elif a in graph.keys() and b in graph.keys():
		graph[b].append(a)
		graph[a].append(b)
	else:
		graph[a] = []
		graph[a].append(b)
		graph[b] = []
		graph[b].append(a)
	if a not in listOfNodes:
		listOfNodes.append(a)
	if b not in listOfNodes:
		listOfNodes.append(b)
listOfNodes.sort()
tempList = []
for y in range(1, len(listOfNodes)):
	if listOfNodes[y - 1] + 1 != listOfNodes[y]:
		graph[listOfNodes[y - 1] + 1] = []
		tempList.append(listOfNodes[y - 1] + 1)
listOfNodes = sorted(union(listOfNodes, tempList))
grevisited = {}
nodes = graph.keys()
alreadyCoverd = []
for node in nodes:
	if node not in alreadyCoverd:
		grevisited[node] = []
		visited = []
		stack = [node]
		while len(stack) != 0:
			v = stack.pop()
			if v not in visited:
				visited.append(v)
				if v in graph:
					for ne in graph[v]:
						stack.append(ne)
		grevisited[node] = visited
		alreadyCoverd = union(alreadyCoverd, visited)
sums = [len(grevisited[k]) for k in grevisited.keys()]
total = n * (n - 1) / 2
for s in sums:
	total = total - s * (s - 1) / 2
print(int(total))


(N, I) = map(int, input().strip().split())
assert 1 <= N <= 10 ** 5
assert 1 <= I <= 10 ** 6
lis_of_sets = []
for i in range(I):
	(a, b) = map(int, input().strip().split())
	assert 0 <= a < N and 0 <= b < N
	indices = []
	new_set = set()
	set_len = len(lis_of_sets)
	s = 0
	while s < set_len:
		if a in lis_of_sets[s] or b in lis_of_sets[s]:
			indices.append(s)
			new_set = new_set.union(lis_of_sets[s])
			del lis_of_sets[s]
			set_len -= 1
		else:
			s += 1
	new_set = new_set.union([a, b])
	lis_of_sets.append(new_set)
answer = N * (N - 1) / 2
for i in lis_of_sets:
	answer -= len(i) * (len(i) - 1) / 2
print(int(answer))


l = []
(n, i) = input().split()
(n, i) = (int(n), int(i))
f = [0] * n
for j in range(i):
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	k = 0
	m = []
	while k < len(l):
		if a in l[k]:
			l[k].add(b)
			m.append(k)
			f[b] = 1
		elif b in l[k]:
			l[k].add(a)
			m.append(k)
			f[a] = 1
		k += 1
	if len(m) == 0:
		s = set([a, b])
		l.append(s)
		f[a] = 1
		f[b] = 1
	else:
		for i in m[1:]:
			l[m[0]] |= l[i]
			del l[i]
s = n * (n - 1) // 2
for j in range(len(l)):
	s -= len(l[j]) * (len(l[j]) - 1) // 2
print(s)


def calculatePermutations(l, r):
	answer = int(r * (r - 1) / 2)
	listOfLenghts = [len(x) for x in l]
	summation = sum(listOfLenghts)
	for x in range(len(l)):
		summation -= len(l[x])
		answer += len(l[x]) * summation
		answer += len(l[x]) * r
	return answer
(n, l) = [int(x) for x in input().split()]
(astronauts, listOfSetOfAstronauts) = (list(range(n)), [])
for x in range(l):
	(a1, a2) = [int(x) for x in input().split()]
	astronautFound = False
	for astronautSet in listOfSetOfAstronauts:
		if a1 in astronautSet:
			for aset in listOfSetOfAstronauts:
				if aset != astronautSet and a2 in aset:
					listOfSetOfAstronauts[listOfSetOfAstronauts.index(astronautSet)] = astronautSet.union(aset)
					listOfSetOfAstronauts.remove(aset)
					break
			astronautSet.add(a2)
			if a2 in astronauts:
				astronauts.remove(a2)
			astronautFound = True
			break
		elif a2 in astronautSet:
			for aset in listOfSetOfAstronauts:
				if aset != astronautSet and a1 in aset:
					listOfSetOfAstronauts[listOfSetOfAstronauts.index(astronautSet)] = astronautSet.union(aset)
					listOfSetOfAstronauts.remove(aset)
					break
			astronautSet.add(a1)
			if a1 in astronauts:
				astronauts.remove(a1)
			astronautFound = True
			break
	if not astronautFound:
		listOfSetOfAstronauts.append({a1, a2})
		if a1 in astronauts:
			astronauts.remove(a1)
		if a2 in astronauts:
			astronauts.remove(a2)
print(calculatePermutations(listOfSetOfAstronauts, len(astronauts)))


class UnionFind:

	def __init__(self, N):
		self.N = N
		self.P = [i for i in range(N)]
		self.S = [1 for _ in range(N)]

	def find(self, V):
		while V != self.P[V]:
			V = self.P[V]
		return V

	def connected(self, P, Q):
		return self.find(P) == self.find(Q)

	def union(self, P, Q):
		PP = self.find(P)
		QP = self.find(Q)
		if PP != QP:
			if self.S[PP] < self.S[QP]:
				self.P[PP] = QP
				self.S[QP] += self.S[PP]
			else:
				self.P[QP] = PP
				self.S[PP] += self.S[QP]

	def get_sizes(self):
		return [self.S[i] for i in range(self.N) if i == self.P[i]]

def journey_to_the_moon(N, P):
	uf = UnionFind(N)
	for p in P:
		uf.union(p[0], p[1])
	T = N * (N - 1) // 2
	for S in uf.get_sizes():
		if S > 1:
			T -= S * (S - 1) // 2
	return T

def main():
	(N, I) = [int(i) for i in input().split()]
	P = []
	for _ in range(I):
		P.append([int(i) for i in input().split()])
	print(journey_to_the_moon(N, P))
main()


from collections import namedtuple
Node = namedtuple('Node', ['country', 'edges'])

def set_country(n, nodes, country):
	to_vist = [n]
	member_count = 0
	while len(to_vist) > 0:
		a = to_vist.pop()
		if nodes[a].country != country:
			nodes[a] = nodes[a]._replace(country=country)
			member_count += 1
			for s in nodes[a].edges:
				to_vist.append(s)
	return member_count

def set_countries(nodes):
	country = 0
	single_node_count = 0
	non_single_node_counts = []
	for (n, node) in enumerate(nodes):
		if node.country < 0:
			count = set_country(n, nodes, country)
			if count > 1:
				non_single_node_counts.append(count)
			else:
				single_node_count += 1
			country += 1
	return (single_node_count, non_single_node_counts)

def sum_of_ints(n):
	return n * (n + 1) // 2
(N, I) = input().split()
(N, I) = (int(N), int(I))
nodes = [Node(-1, []) for _ in range(N)]
for _ in range(I):
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	nodes[a].edges.append(b)
	nodes[b].edges.append(a)
(single_count, non_single_count) = set_countries(nodes)
non_single_pair_count = 0
if len(non_single_count) > 1:
	count_len = len(non_single_count)
	for i in range(count_len - 1):
		for j in range(i + 1, count_len):
			non_single_pair_count += non_single_count[i] * non_single_count[j]
non_single_count_sum = sum(non_single_count)
sn = sum_of_ints(single_count - 1)
pair_count = single_count * non_single_count_sum + sn + non_single_pair_count
print(pair_count)


import sys
import time
try:
	inputs = list(map(int, input().split()))
	numaustronauts = int(inputs[0])
	if numaustronauts < 0 or numaustronauts > 100000:
		raise ValueError('Invalid number of astronauts')
	numpairs = int(inputs[1])
	if numpairs < 0 or numpairs > 10000:
		raise ValueError('Invalid number of pairs')
	al = [None] * numaustronauts
	for i in range(numaustronauts):
		al[i] = -1
	overrideindex = dict()
	CountryList = []
	i = 0
	t0 = time.time()
	while i < numpairs:
		pair = list(map(int, input().split()))
		for astronaut in pair:
			if astronaut < 0 or astronaut >= numaustronauts:
				raise ValueError('Invalid astronaut number')
		index1 = al[pair[0]]
		while index1 in overrideindex:
			index1 = overrideindex[index1]
		index2 = al[pair[1]]
		while index2 in overrideindex:
			index2 = overrideindex[index2]
		if index1 == -1 and index2 == -1:
			a = set()
			CountryList.append(a)
			a.add(pair[0])
			a.add(pair[1])
			al[pair[0]] = len(CountryList) - 1
			al[pair[1]] = len(CountryList) - 1
		elif index1 == -1:
			CountryList[index2].add(pair[0])
			al[pair[0]] = index2
		elif index2 == -1:
			CountryList[index1].add(pair[1])
			al[pair[1]] = index1
		elif index1 != index2:
			CountryList[index1] = CountryList[index1].union(CountryList[index2])
			al[pair[1]] = index1
			CountryList[index2].clear()
			overrideindex[index2] = index1
		i = i + 1
	t1 = time.time()
	total = t1 - t0
	SingleAstronautCountries = 0
	for j in range(numaustronauts):
		if al[j] == -1:
			SingleAstronautCountries = SingleAstronautCountries + 1
	Numcombinations = 0
	i = 0
	k = 0
	while i < len(CountryList):
		if len(CountryList[i]) > 0:
			k = k + len(CountryList[i])
			j = i + 1
			while j < len(CountryList):
				if len(CountryList[j]) > 0:
					Numcombinations = Numcombinations + len(CountryList[i]) * len(CountryList[j])
				j = j + 1
		i = i + 1
	Numcombinations = Numcombinations + SingleAstronautCountries * (numaustronauts - SingleAstronautCountries) + int(SingleAstronautCountries * (SingleAstronautCountries - 1) / 2)
	print('{0}'.format(Numcombinations))
except ValueError:
	print('Invalid input')
	exit()


from functools import reduce
import operator as op
import itertools as it
from math import factorial as fac

def choose(n, k=2):
	return fac(n) // (fac(k) * fac(n - k))
(N, I) = map(int, input().split())
countries = []
for _ in range(I):
	(a, b) = map(int, input().split())
	for (i, c) in enumerate(countries):
		if a in c or b in c:
			c.update({a, b})
			trash = []
			for d in countries[i + 1:]:
				if c & d:
					c.update(d)
					trash.append(d)
			for x in trash:
				countries.remove(x)
			break
	else:
		countries.append({a, b})
all_possible = N * (N - 1) // 2
ways = sum(map(choose, map(len, countries)))
print(all_possible - ways)
exit()
flattened = set(it.chain.from_iterable(countries))
missing = set(range(N)) - flattened
for x in missing:
	countries.append({x})
ways = reduce(op.mul, map(len, countries))
print(ways)


def find_ind(group):
	i = 0
	while group[i]:
		i += 1
	return i
NI = input().split()
(N, I) = (int(i) for i in NI)
mem = [-1 for i in range(N)]
group = [[] for i in range(N)]
smlst_avail_ind = 0
for i in range(I):
	aus_in = input().split()
	(a1, a2) = (int(j) for j in aus_in)
	if mem[a1] == -1 and mem[a2] == -1:
		ind = find_ind(group)
		group[ind] = [a1, a2]
		mem[a1] = ind
		mem[a2] = ind
	elif mem[a1] == -1 and mem[a2] != -1:
		group[mem[a2]].append(a1)
		mem[a1] = mem[a2]
	elif mem[a1] != -1 and mem[a2] == -1:
		group[mem[a1]].append(a2)
		mem[a2] = mem[a1]
	elif mem[a1] != -1 and mem[a2] != -1 and (mem[a1] != mem[a2]):
		mem_a2 = mem[a2]
		group[mem[a1]] = group[mem[a1]] + group[mem[a2]]
		for aus in group[mem[a2]]:
			mem[aus] = mem[a1]
		group[mem_a2] = []
out = 0
specified = 0
for nat in group:
	nat_num = len(nat)
	specified += nat_num
	out += (N - nat_num) * nat_num
out += (N - specified) * (N - 1)
print(int(out / 2))


from collections import defaultdict

class UnionFind(object):

	def __init__(self, num):
		self.num = num
		self.parent = self
		self.rank = 0

	@staticmethod
	def union(x, y):
		x_root = x.find()
		y_root = y.find()
		if x_root == y_root:
			return
		if x_root.rank > y_root.rank:
			y_root.parent = x_root
		elif x_root.rank < y_root.rank:
			x_root.parent = y_root
		else:
			x_root.parent = y_root
			y_root.rank += 1

	def find(self):
		if self.num != self.parent.num:
			self.parent = self.parent.find()
		return self.parent

	def __str__(self):
		return 'Num: {}, Parent: {}, Rank: {}'.format(self.num, self.parent.num, self.rank)
(N, I) = [int(x) for x in input().split()]
UnionFinds = [UnionFind(i) for i in range(N)]
for _ in range(I):
	(first, second) = [int(x) for x in input().split()]
	UnionFind.union(UnionFinds[first], UnionFinds[second])
countries = defaultdict(int)
for i in range(N):
	countries[UnionFinds[i].find().num] += 1
(answer, curr) = (0, 0)
for count in countries.values():
	answer += count * curr
	curr += count
print(answer)


class vertex:

	def __init__(self):
		self.adj = []
		self.visited = False

def count_vertices(v, V):
	if V[v].visited == True:
		return 0
	ver = [v]
	count = 0
	while len(ver) > 0:
		next = []
		for v in ver:
			if V[v].visited == True:
				continue
			else:
				V[v].visited = True
				count += 1
				next += V[v].adj
		ver = next
	return count
var = input().split()
(N, I) = (int(var[0]), int(var[1]))
V = [vertex() for i in range(0, N)]
for i in range(0, I):
	var = input().split()
	(A, B) = (int(var[0]), int(var[1]))
	V[A].adj.append(B)
	V[B].adj.append(A)
sets = []
for i in range(0, N):
	if V[i].visited == True:
		continue
	else:
		sets.append(count_vertices(i, V))
result = N * (N - 1) >> 1
for val in sets:
	result -= val * (val - 1) >> 1
print(result)


class Node:

	def __init__(self, name, parent, size):
		self.parent = parent
		self.name = name
		self.size = size

	def get_leader(self):
		if self.parent is None:
			return self
		self.parent = self.parent.get_leader()
		return self.parent

	def union(self, other):
		my_leader = self.get_leader()
		other_leader = other.get_leader()
		if my_leader is other_leader:
			return
		if other_leader.size > my_leader.size:
			my_leader.parent = other_leader
			other_leader.size += my_leader.size
		else:
			other_leader.parent = my_leader
			my_leader.size += other_leader.size

	def get_community_size(self):
		return self.get_leader().size

def n_choose_2(n):
	return (n - 1) * n / 2
line = input().strip().split(' ')
size = int(line[0])
edges = int(line[1])
nodes = []
for i in range(0, size):
	nodes.append(Node(i, None, 1))
for i in range(0, edges):
	line = input().strip().split(' ')
	node1 = nodes[int(line[0])]
	node2 = nodes[int(line[1])]
	node1.union(node2)
leader = []
count = n_choose_2(size)
for node in nodes:
	if node.parent is None:
		leader.append(node.size)
		if node.size >= 2:
			count -= n_choose_2(node.size)
print(int(count))


__author__ = 'Nathan'
(n, i) = input().split()
n = int(n)
i = int(i)
countries = {x: {x} for x in range(n)}
unique_countries = {x for x in range(n)}
for j in range(i):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	new_country = countries[a].union(countries[b])
	for x in new_country:
		if x in unique_countries:
			countries[x] = new_country
			new_assign = x
			break
	for x in countries[new_assign]:
		countries[x] = countries[new_assign]
		if x != new_assign and x in unique_countries:
			unique_countries.remove(x)
pairs = 0
for rep in unique_countries:
	rep_country_size = len(countries[rep])
	n -= rep_country_size
	pairs += rep_country_size * n
print(pairs)


def main():
	tmp = input().split()
	N = int(tmp[0])
	I = int(tmp[1])
	people = [i for i in range(N)]
	groups = [[i] for i in range(N)]
	for i in range(I):
		tmp = input().split()
		a = int(tmp[0])
		b = int(tmp[1])
		if groups[people[a]] != groups[people[b]]:
			groups[people[a]].extend(groups[people[b]])
			num = people[b]
			grp = groups[num]
			for j in range(len(grp)):
				people[grp[j]] = people[a]
			groups[num] = 0
	total = 0
	minus = 0
	hold = dict()
	for i in range(N):
		if groups[i] != 0:
			if hold.get(len(groups[i])) == None:
				hold[len(groups[i])] = 1
			else:
				hold[len(groups[i])] += 1
	keys = sorted(hold)
	for val in keys:
		if val == 1:
			for i in range(hold[val]):
				total += N - 1 - i
			minus += hold[val]
		else:
			for i in range(hold[val]):
				total += val ** 2 * i
			minus += hold[val] * val
			total += hold[val] * val * (N - minus)
	if total == 1:
		total = 0
	print(total)
main()


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(I):
	graph = {}
	while I > 0:
		(A, B) = read_ints()
		if not A in graph:
			graph[A] = []
		if not B in graph:
			graph[B] = []
		graph[A].append(B)
		graph[B].append(A)
		I -= 1
	return graph

def traverse(graph, astronaut):
	country_size = 0
	q = queue.Queue()
	q.put(astronaut)
	while not q.empty():
		a = q.get()
		if graph[a] is None:
			continue
		country_size += 1
		edges = graph[a]
		graph[a] = None
		for b in edges:
			q.put(b)
	return country_size

def combinations(graph, N):
	combinations = astronauts = 0
	for a in graph:
		country_size = traverse(graph, a)
		combinations += astronauts * country_size
		astronauts += country_size
	while astronauts < N:
		combinations += astronauts
		astronauts += 1
	return combinations

def main():
	(N, I) = read_ints()
	graph = build_graph(I)
	print(combinations(graph, N))
main()


def bfsConn(g):
	n = len(g)
	c = [None] * n
	color = 0
	for i in range(n):
		if c[i] is None:
			q = [i]
			while len(q) > 0:
				v = q[0]
				q = q[1:]
				c[v] = color
				for e in g[v]:
					if c[e] is None:
						q += [e]
			color += 1
	result = [0] * color
	for x in c:
		result[x] += 1
	return result
(n, m) = [int(x) for x in input().split()]
g = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = [int(x) for x in input().split()]
	g[a] += [b]
	g[b] += [a]
a = bfsConn(g)
sa = [0] * len(a)
s = 0
for i in reversed(range(len(a))):
	sa[i] = s
	s += a[i]
s = sum((a[i] * sa[i] for i in range(len(a))))
print(s)


line1 = input()
numberOfAstronauts = int(line1.split(' ')[0])
numberOfCountries = int(line1.split(' ')[1])
results = []
covered = []
hh = {}
for n in range(numberOfCountries):
	data = input()
	results.append(data.split())
	covered.extend(data.split())
groups = []
for t in results:
	(jthName, kthName) = t
	jthGroup = -1
	kthGroup = -1
	for (idx, group) in enumerate(groups):
		if jthName in group:
			jthGroup = idx
		if kthName in group:
			kthGroup = idx
	if jthGroup == kthGroup:
		if jthGroup == -1:
			groups.append(set((jthName, kthName)))
	elif jthGroup != kthGroup:
		if kthGroup == -1:
			groups[jthGroup].add(kthName)
		elif jthGroup == -1:
			groups[kthGroup].add(jthName)
		else:
			merged = set()
			merged.update(groups[jthGroup])
			merged.update(groups[kthGroup])
			b1 = set(groups[jthGroup])
			b2 = set(groups[kthGroup])
			groups.remove(b1)
			groups.remove(b2)
			groups.append(merged)
full = [str(i) for i in range(numberOfAstronauts)]
missing = len(list(set(full).difference(set(covered))))
totes = []
for s in groups:
	totes.append(len(s))
money = 0
import itertools
for i in itertools.combinations(totes, 2):
	money += i[0] * i[1]

def choose(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0
print(money + sum(totes) * missing + choose(missing, 2))


(N, I) = map(int, input().split())
pairs = []
for _ in range(I):
	pairs.append(list(map(int, input().split())))
country = 0
astros = [-1] * N
for pair in pairs:
	(a, b) = (astros[pair[0]], astros[pair[1]])
	m = max(a, b)
	if m < 0:
		m = country
		country += 1
	if a >= 0 and b >= 0:
		for i in range(N):
			if astros[i] == a or astros[i] == b:
				astros[i] = m
	else:
		astros[pair[0]] = astros[pair[1]] = m
countryless = 0
for i in range(N):
	if astros[i] == -1:
		countryless += 1
if countryless > 0:
	country += 1
apc = [0] * country
for astro in astros:
	if astro > -1:
		apc[astro] += 1
if countryless > 0:
	apc[country - 1] = countryless
comb = 0
for i in range(country - 1):
	for j in range(i + 1, country):
		comb += apc[i] * apc[j]
if countryless > 0:
	comb += countryless * (countryless - 1) // 2
print(comb)


class AstroGraph(object):

	def __init__(self, N, L):
		self.astronauts = [astronaut for astronaut in range(N)]
		self.tree = [list() for astronaut in self.astronauts]
		self.read_graph(N, L)

	def read_graph(self, N, L):
		for _ in range(L):
			(a, b) = [int(x) for x in input().split()]
			self.tree[a].append(b)
			self.tree[b].append(a)

	def compute_groups(self):
		lonely_astronauts = set(self.astronauts.copy())
		groups = list()
		group_idx = 0
		while lonely_astronauts:
			queue = set()
			checked = set()
			candidate = lonely_astronauts.pop()
			checked.add(candidate)
			queue.update([astronaut for astronaut in self.tree[candidate] if astronaut not in checked])
			while queue:
				new_candidates = set()
				for astronaut in queue:
					new_candidates.update(self.tree[astronaut])
					checked.add(astronaut)
					try:
						lonely_astronauts.remove(astronaut)
					except:
						pass
				new_candidates = new_candidates.difference(checked)
				queue = new_candidates.copy()
			groups.append(len(checked))
			group_idx += 1
		return groups
(N, L) = [int(x) for x in input().split()]
pairs = AstroGraph(N, L)
groups = pairs.compute_groups()
result = 0
groups.sort()
largest = groups[-1]
no_groups = []
for no in range(1, largest + 1):
	count = groups.count(no)
	no_of_pairs = (count - 1) * count / 2
	no_of_combinations = no_of_pairs * no ** 2
	result += no_of_combinations
	no_groups.append(count)
for (idx, group) in enumerate(no_groups):
	result += sum([group * (idx + 1) * (idx2 + idx + 2) * next_group for (idx2, next_group) in enumerate(no_groups[idx + 1:])])
print(int(result))


mode = 'fieele'
if mode == 'file':
	f = open('test.txt', 'r')
d = {}
big = {}
count = 0
if mode == 'file':
	[n, I] = [int(x) for x in f.readline().split()]
else:
	[n, I] = [int(x) for x in input().split()]
for z in range(I):
	if mode == 'file':
		[p, q] = [int(x) for x in f.readline().split()]
	else:
		[p, q] = [int(x) for x in input().split()]
	found_p = False
	found_q = False
	if p in d:
		found_p = True
	if q in d:
		found_q = True
	if found_p and found_q:
		g = d[p]
		h = d[q]
		if h == g:
			continue
		if len(big[h]) >= len(big[g]):
			for i in big[g]:
				d[i] = h
			big[h] += big[g]
			big.pop(g)
		else:
			for i in big[h]:
				d[i] = g
			big[g] += big[h]
			big.pop(h)
		continue
	elif found_p:
		d[q] = d[p]
		big[d[p]].append(q)
		n -= 1
	elif found_q:
		d[p] = d[q]
		big[d[q]].append(p)
		n -= 1
	else:
		big[count] = [p, q]
		d[p] = count
		d[q] = count
		count += 1
		n -= 2
array = []
pro = 0
s = 0
for (i, j) in big.items():
	k = len(j)
	array.append(k)
	s += k
i = 0
while i < len(array) - 1:
	j = i + 1
	while j < len(array):
		pro += array[i] * array[j]
		j += 1
	i += 1
pro += s * n + n * (n - 1) // 2
print(int(pro))
if mode == 'file':
	f.close()


import itertools
(n, i) = tuple(map(int, input().split()))
groups = []
ngroups = []
astronauts = list(itertools.repeat(-1, n))
for _ in range(i):
	(a1, a2) = [int(x) for x in input().split()]
	v1 = -1
	if astronauts[a1] != -1:
		v1 = ngroups[astronauts[a1]]
		while v1 != ngroups[v1]:
			v1 = ngroups[v1]
		ngroups[astronauts[a1]] = v1
	v2 = -1
	if astronauts[a2] != -1:
		v2 = ngroups[astronauts[a2]]
		while v2 != ngroups[v2]:
			v2 = ngroups[v2]
		ngroups[astronauts[a2]] = v2
	if v1 == -1:
		if v2 == -1:
			new_group = len(groups)
			ngroups.append(len(groups))
			groups.append(2)
			astronauts[a1] = new_group
			astronauts[a2] = new_group
		else:
			astronauts[a1] = v2
			groups[v2] += 1
	elif v2 == -1:
		astronauts[a2] = v1
		groups[v1] += 1
	else:
		if v1 == v2:
			continue
		groups[v1] += groups[v2]
		groups[v2] = 0
		ngroups[v2] = ngroups[v1]
prev = 0
result = 0
for i in range(len(groups)):
	result += groups[i] * prev
	prev += groups[i]
for a in astronauts:
	if a == -1:
		result += prev
		prev += 1
print(result)


import sys

def findPrt(a):
	if prt[a] < 0:
		return a
	prt[a] = findPrt(prt[a])
	return prt[a]

def join(a, b):
	a = findPrt(a)
	b = findPrt(b)
	if a != b:
		prt[a] = b
(n, i) = sys.stdin.readline().split()
(n, i) = (int(n), int(i))
prt = [-1 for k in range(n)]
for k in range(i):
	(a, b) = sys.stdin.readline().split()
	(a, b) = (int(a), int(b))
	join(a, b)
count = [0 for k in range(n)]
for k in range(n):
	pk = findPrt(k)
	count[pk] = count[pk] + 1
print(sum([a * (n - a) for a in count]) // 2)


class Node:

	def __init__(self, value):
		self.value = value
		self.visited = False
		self.edges = set()

	def __str__(self):
		return str(self.edges)

def combos(graph):
	countries = []
	other = []
	for n in graph:
		if not n.visited:
			queue = [n]
			country = [n.value]
			while queue:
				cur = queue.pop()
				cur.visited = True
				for child_i in cur.edges:
					if child_i not in country:
						child = graph[child_i]
						country.append(child_i)
						queue.append(child)
			if len(country) < 2:
				other += country
			else:
				countries.append(country)
	count = 0
	for i in range(0, len(countries)):
		remains = sum([len(c) for c in countries[i + 1:]]) + len(other)
		count += len(countries[i] * remains)
	count += sum((len(other) - n for n in range(1, len(other))))
	print(count)
(num_nodes, num_edges) = input().split()
num_nodes = int(num_nodes)
num_edges = int(num_edges)
graph = [Node(i) for i in range(0, num_nodes)]
for _ in range(0, num_edges):
	(x, y) = input().split()
	graph[int(x)].edges.add(int(y))
	graph[int(y)].edges.add(int(x))
combos(graph)


(N, L) = list(map(int, input().split()))
countries = dict()
members = dict()
next_country = 0
for i in range(L):
	(a, b) = list(map(int, input().split()))
	if a in countries and b in countries:
		ca = countries[a]
		cb = countries[b]
		if ca != cb:
			for c in members[cb]:
				countries[c] = ca
				members[ca].add(c)
			del members[cb]
	elif a in countries:
		countries[b] = countries[a]
		members[countries[a]].add(b)
	elif b in countries:
		countries[a] = countries[b]
		members[countries[b]].add(a)
	else:
		countries[a] = next_country
		countries[b] = next_country
		members[next_country] = set([a, b])
		next_country += 1
total_ways = N * (N - 1) / 2
for (k, v) in members.items():
	total_ways -= len(v) * (len(v) - 1) / 2
print(int(total_ways))


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(I):
	graph = {}
	while I > 0:
		(A, B) = read_ints()
		if A not in graph:
			graph[A] = []
		if B not in graph:
			graph[B] = []
		graph[A].append(B)
		graph[B].append(A)
		I -= 1
	return graph

def traverse(graph, astronaut):
	country_size = 0
	q = queue.Queue()
	q.put(astronaut)
	while not q.empty():
		a = q.get()
		if graph[a] is None:
			continue
		country_size += 1
		edges = graph[a]
		graph[a] = None
		for b in edges:
			q.put(b)
	return country_size

def combinations(graph, N):
	combinations = astronauts = 0
	for a in graph:
		country_size = traverse(graph, a)
		combinations += astronauts * country_size
		astronauts += country_size
	combinations += int((astronauts + N - 1) * 0.5 * (N - astronauts))
	return combinations
(N, I) = read_ints()
graph = build_graph(I)
print(combinations(graph, N))


def check_exist(d, e):
	for x in d:
		if x in e:
			return True
	return False
(num_of_people, lines) = map(int, input().split(' '))
candidates = {}
nations = []
for _ in range(lines):
	(former, latter) = map(int, input().split(' '))
	if former not in candidates:
		candidates[former] = [latter]
	elif latter not in candidates[former]:
		candidates[former] += [latter]
	if latter not in candidates:
		candidates[latter] = [former]
	elif former not in candidates[latter]:
		candidates[latter] += [former]
visited = []
for key in candidates:
	num = 0
	if key in visited:
		continue
	queue = [key]
	while len(queue) != 0:
		next = queue.pop()
		if next not in visited:
			visited += [next]
			queue += candidates[next]
			num += 1
	nations += [num]
remaining = num_of_people - len(visited)
ret = 0
for i in range(len(nations) - 1):
	ret += sum(map(lambda x: x * nations[i], nations[i + 1:]))
print(int(ret + sum(nations) * remaining + remaining * (remaining - 1) / 2))


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(I):
	graph = {}
	while I > 0:
		(A, B) = read_ints()
		if A not in graph:
			graph[A] = []
		if B not in graph:
			graph[B] = []
		graph[A].append(B)
		graph[B].append(A)
		I -= 1
	return graph

def traverse(graph, astronaut):
	country_size = 0
	q = queue.Queue()
	q.put(astronaut)
	while not q.empty():
		a = q.get()
		if graph[a] is None:
			continue
		country_size += 1
		edges = graph[a]
		graph[a] = None
		for b in edges:
			q.put(b)
	return country_size

def combinations(graph, N):
	combinations = astronauts = 0
	for a in graph:
		country_size = traverse(graph, a)
		combinations += astronauts * country_size
		astronauts += country_size
	combinations += int((astronauts + N - 1) * 0.5 * (N - astronauts))
	return combinations

def main():
	(N, I) = read_ints()
	graph = build_graph(I)
	print(combinations(graph, N))
main()


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

def merge(x, y):
	x = find(x)
	y = find(y)
	if x != y:
		if c[x] > c[y]:
			p[y] = x
			c[x] += c[y]
		else:
			p[x] = y
			c[y] += c[x]
(n, m) = map(int, input().split())
p = list(range(n))
c = [1] * n
for _ in range(m):
	(x, y) = map(int, input().split())
	merge(x, y)
s = set()
for x in range(n):
	s.add(find(x))
r = n * (n - 1) // 2
for x in s:
	r -= c[x] * (c[x] - 1) // 2
print(r)


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(I):
	graph = {}
	while I > 0:
		(A, B) = read_ints()
		if A not in graph:
			graph[A] = []
		if B not in graph:
			graph[B] = []
		graph[A].append(B)
		graph[B].append(A)
		I -= 1
	return graph

def traverse(graph, astronaut):
	country_size = 0
	q = queue.Queue()
	q.put(astronaut)
	while not q.empty():
		a = q.get()
		if graph[a] is None:
			continue
		country_size += 1
		edges = graph[a]
		graph[a] = None
		for b in edges:
			q.put(b)
	return country_size

def combinations(graph, N):
	combinations = astronauts = 0
	for a in graph:
		country_size = traverse(graph, a)
		combinations += astronauts * country_size
		astronauts += country_size
	combinations += int((astronauts + N - 1) * 0.5 * (N - astronauts))
	return combinations

def main():
	(N, I) = read_ints()
	graph = build_graph(I)
	print(combinations(graph, N))
main()


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(I):
	graph = {}
	while I > 0:
		(A, B) = read_ints()
		if A not in graph:
			graph[A] = []
		if B not in graph:
			graph[B] = []
		graph[A].append(B)
		graph[B].append(A)
		I -= 1
	return graph

def traverse(graph, astronaut):
	country_size = 0
	q = queue.Queue()
	q.put(astronaut)
	while not q.empty():
		a = q.get()
		if graph[a] is None:
			continue
		country_size += 1
		edges = graph[a]
		graph[a] = None
		for b in edges:
			q.put(b)
	return country_size

def combinations(graph, N):
	combinations = astronauts = 0
	for a in graph:
		country_size = traverse(graph, a)
		combinations += astronauts * country_size
		astronauts += country_size
	combinations += int((astronauts + N - 1) * 0.5 * (N - astronauts))
	return combinations
(N, I) = read_ints()
graph = build_graph(I)
print(combinations(graph, N))


from collections import deque

def dfsvisit():
	l = []
	for i in range(n):
		if v[i] == 0:
			if i in d:
				l.append(dfs(i))
	t = len(l)
	cnt = 0
	for i in range(t):
		cnt = cnt + l[i] * (l[i] - 1) // 2
	print(n * (n - 1) // 2 - cnt)

def dfs(i):
	q = deque([i])
	while q:
		u = q.pop()
		c = 1
		if v[u] == 1 and u in d:
			for y in d[u]:
				if par[y] == u:
					c = c + nv[y]
			nv[u] = c
			continue
		elif v[u] == 1:
			nv[u] = c
			continue
		v[u] = 1
		q.append(u)
		if u in d:
			for y in d[u]:
				if v[y] == 0:
					q.append(y)
					par[y] = u
	return nv[i]
(n, m) = [int(x) for x in input().strip().split()]
d = dict()
for i in range(m):
	(u, v) = [int(x) for x in input().strip().split()]
	if u in d:
		d[u].append(v)
	else:
		d[u] = [v]
	if v in d:
		d[v].append(u)
	else:
		d[v] = [u]
v = [0 for i in range(n)]
par = [0 for i in range(n)]
nv = [0 for i in range(n)]
dfsvisit()


def bfs(node):
	stk = [node]
	used[node] = True
	res = 1
	while len(stk):
		nd = stk.pop()
		for conn in matr[nd]:
			if not used[conn]:
				used[conn] = True
				res += 1
				stk.append(conn)
	return res
(n, i) = map(int, input().strip().split(' '))
matr = tuple([[] for _ in range(n)])
used = list([False for _ in range(n)])
comps = []
for _ in range(i):
	(x, y) = map(int, input().strip().split(' '))
	matr[x].append(y)
	matr[y].append(x)
for ii in range(n):
	if not used[ii]:
		comps.append(bfs(ii))
res = 0
summa = sum(comps)
for ii in range(len(comps)):
	res += comps[ii] * (summa - comps[ii])
print(res // 2)


import sys
(N, I) = list(map(int, sys.stdin.readline().split()))
astronauts = [-1] * N
countries = []
for _ in range(I):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	if astronauts[A] > -1 and astronauts[B] > -1:
		if astronauts[A] != astronauts[B]:
			k = astronauts[B]
			countries[astronauts[A]].extend(countries[k])
			for i in countries[k]:
				astronauts[i] = astronauts[A]
			countries[k] = []
	elif astronauts[A] > -1 and astronauts[B] == -1:
		astronauts[B] = astronauts[A]
		countries[astronauts[A]].append(B)
	elif astronauts[A] == -1 and astronauts[B] > -1:
		astronauts[A] = astronauts[B]
		countries[astronauts[B]].append(A)
	else:
		astronauts[B] = astronauts[A] = len(countries)
		countries.append([A, B])
unpaired = sum((x == -1 for x in astronauts))
x = [len(c) for c in countries if c]
total = unpaired * (unpaired - 1) // 2
total += unpaired * sum(x)
total += sum((x[i] * x[j] for i in range(len(x) - 1) for j in range(i + 1, len(x))))
print(total)


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(I):
	graph = {}
	while I > 0:
		(A, B) = read_ints()
		if A not in graph:
			graph[A] = []
		if B not in graph:
			graph[B] = []
		graph[A].append(B)
		graph[B].append(A)
		I -= 1
	return graph

def traverse(graph, astronaut):
	country_size = 0
	q = queue.Queue()
	q.put(astronaut)
	while not q.empty():
		a = q.get()
		if graph[a] is None:
			continue
		country_size += 1
		edges = graph[a]
		graph[a] = None
		for b in edges:
			q.put(b)
	return country_size

def combinations(graph, N):
	combinations = astronauts = 0
	for a in graph:
		country_size = traverse(graph, a)
		combinations += astronauts * country_size
		astronauts += country_size
	combinations += int((astronauts + N - 1) * 0.5 * (N - astronauts))
	return combinations

def main():
	(N, I) = read_ints()
	graph = build_graph(I)
	print(combinations(graph, N))
main()


from math import factorial

def nCr(n, r):
	return factorial(n) // (factorial(r) * factorial(n - r))
(n, i) = (int(j) for j in input().strip().split())
countries = {}
for _ in range(i):
	pair = tuple((int(j) for j in input().strip().split()))
	if pair[0] in countries:
		countries[pair[0]] |= set(pair)
	else:
		countries[pair[0]] = set(pair)
	if pair[1] in countries:
		countries[pair[1]] |= set(pair)
	else:
		countries[pair[1]] = set(pair)
countries = [countries[k] for k in countries]
pnu_len = 0
starting_len = len(countries)
while pnu_len < starting_len:
	starting_len = len(countries)
	for set_ in countries:
		matches = [set_i for set_i in countries if set_ & set_i]
		if [matches] == set_:
			pnu_len = starting_len
		else:
			countries = [j for j in countries if j not in matches]
			m = set()
			for j in matches:
				m |= j
			countries.append(m)
			pnu_len = len(countries)
bad_combos = 0
for astronuts in countries:
	bad_combos += nCr(len(astronuts), 2)
print(str(nCr(n, 2) - bad_combos))


import queue

def buildGraph(pairList):
	graph = {}
	for pair in pairList:
		(A, B) = (pair[0], pair[1])
		if A not in graph:
			graph[A] = []
		if B not in graph:
			graph[B] = []
		graph[A].append(B)
		graph[B].append(A)
	return graph

def exhaustGraph(graph, astronaut):
	size = 0
	q = queue.Queue()
	if graph[astronaut] is not None:
		q.put(astronaut)
	while not q.empty():
		currentAstronaut = q.get()
		if graph[currentAstronaut] is None:
			continue
		size += 1
		connections = graph[currentAstronaut]
		if connections:
			for node in connections:
				q.put(node)
			graph[currentAstronaut] = None
	return size

def getCombinations(graph, astronauts):
	astronautCount = combinations = 0
	for astronaut in graph:
		countrySize = exhaustGraph(graph, astronaut)
		combinations += countrySize * astronautCount
		astronautCount += countrySize
	singletonCount = astronauts - astronautCount
	if singletonCount > 0:
		combinations += singletonCount * astronautCount + iterativeAdd(singletonCount)
	return combinations

def iterativeAdd(n):
	total = 0
	while n > 1:
		total += n - 1
		n -= 1
	return total

def solve():
	given = [int(x) for x in input().split()]
	(astronauts, pairs) = (given[0], given[1])
	pairList = [[int(x) for x in input().split()] for x in range(pairs)]
	graph = buildGraph(pairList)
	combinations = getCombinations(graph, astronauts)
	print(combinations)
solve()


import functools
import sys
sys.setrecursionlimit(100000)

class Graph:

	def __init__(self, n):
		self.edges = {}
		self.n = n

	def connect(self, x: int, y: int):
		self.edges.setdefault(x, []).append(y)
		self.edges.setdefault(y, []).append(x)

	def dfs(self, x: int, visited) -> int:
		if x in visited:
			return 0
		visited.add(x)
		count = 1
		for y in self.edges.get(x, []):
			count += self.dfs(y, visited)
		return count

	def get_connected_components(self):
		components = []
		visited = set([])
		for astronaut in range(self.n):
			count = self.dfs(astronaut, visited)
			if count != 0:
				components.append(count)
		return components
(N, I) = map(int, input().split())
graph = Graph(N)
for _ in range(I):
	(x, y) = map(int, input().split())
	graph.connect(x, y)
components = graph.get_connected_components()
total = sum(components)
pairs = 0
for component in components:
	pairs += component * (total - component)
pairs //= 2
print(pairs)


def bfs(s, G, seen):
	res = 0
	Q = [s]
	while Q:
		u = Q.pop()
		if u in seen:
			continue
		seen.add(u)
		res += 1
		for v in G[u]:
			Q.append(v)
	return res

def CC(G):
	components = []
	seen = set()
	for u in G:
		if u in seen:
			continue
		size = bfs(u, G, seen)
		components.append(size)
	return components

def C_nk(n, k):
	if k == 1:
		return n
	return C_nk(n, k - 1) * (n - k + 1) // k

def Sol(G):
	components = CC(G)
	summ = sum(components)
	count1 = C_nk(summ, 2)
	count2 = 0
	for c in components:
		count2 += C_nk(c, 2)
	return count1 - count2
(N, I) = map(int, input().split())
G = {k: [] for k in range(N)}
for _ in range(I):
	(u, v) = map(int, input().split())
	G[u].append(v)
	G[v].append(u)
print(Sol(G))


__author__ = 'siddharth'
from collections import Counter
from itertools import combinations as com
(N, T) = map(int, input().split())
country = [0] * N
ct = 1
for _ in range(T):
	(a, b) = map(int, input().split())
	if country[a] or country[b]:
		if country[a] and country[b]:
			c = country[b]
			for (i, v) in enumerate(country):
				if v == c:
					country[i] = country[a]
		elif country[a]:
			country[b] = country[a]
		else:
			country[a] = country[b]
	else:
		country[a] = ct
		country[b] = ct
		ct += 1
for (i, v) in enumerate(country):
	if not v:
		country[i] = ct
		ct += 1
countries = Counter(country)
if len(countries) <= 1:
	print(0)
else:
	pairs = 0
	temp = []
	ctr = 0
	for v in countries.values():
		if v > 1:
			temp.append(v)
		elif v == 1:
			ctr += 1
	for (a, b) in com(temp, 2):
		pairs += a * b
	for a in temp:
		pairs += a * ctr
	pairs += ctr * (ctr - 1) // 2
	print(pairs)


from queue import PriorityQueue
import sys
sys.setrecursionlimit(10000)
WHITE = 'WHITE'
GREY = 'GREY'
BLACK = 'BLACK'

class Graph:

	def __init__(self):
		self.vertices = dict()

	def add_edge(self, source, destination, weight):
		if source not in self.vertices:
			self.vertices[source] = Vertex(source)
		if destination not in self.vertices:
			self.vertices[destination] = Vertex(destination)
		self.vertices[source].adj_list.append(Edge(self.vertices[source], self.vertices[destination], weight))
		self.vertices[destination].adj_list.append(Edge(self.vertices[destination], self.vertices[source], weight))

class Vertex:

	def __init__(self, name):
		self.name = name
		self.adj_list = list()
		self.color = WHITE

	def __repr__(self):
		return '%s' % self.name

class Edge:

	def __init__(self, source, destination, weight):
		(self.source, self.destination, self.weight) = (source, destination, weight)

	def __repr__(self):
		return '%d %d %d ' % (self.source, self.destination, self.weight)

	def __lt__(self, other):
		return self.weight < other.weight
graph = Graph()
(n, i) = [int(x) for x in input().split()]
for ii in range(i):
	(source, destination) = input().split()
	graph.add_edge(source, destination, 1)
countries = list()
final_combinations = list()

def dfs_visit(u):
	u.color = GREY
	c = 0
	for v in u.adj_list:
		v = v.destination
		if v.color == WHITE:
			c += dfs_visit(v)
	u.color = BLACK
	return 1 + c
for u in graph.vertices.values():
	if u.color == WHITE:
		countries.append(dfs_visit(u))
total = 0
for x in countries:
	total += x * (x - 1) / 2
print(int(n * (n - 1) / 2 - total))


from operator import mul
from math import factorial
from itertools import combinations

class WeightedQuickUnion(object):

	def __init__(self):
		self.id = {}
		self.sz = {}

	def root(self, i):
		if i not in self.id:
			self.id[i] = i
			self.sz[i] = 1
			return i
		while i != self.id[i]:
			i = self.id[i]
		return i

	def connected(self, p, q):
		return self.root(p) == self.root(q)

	def union(self, p, q):
		i = self.root(p)
		j = self.root(q)
		if i == j:
			return
		if self.sz[i] < self.sz[j]:
			self.id[i] = j
			self.sz[j] += self.sz[i]
		else:
			self.id[j] = i
			self.sz[i] += self.sz[j]
wqu = WeightedQuickUnion()
(N, I) = map(int, input().split())
for _ in range(I):
	(u, v) = map(int, input().split())
	wqu.union(u, v)
uniq_c = set()
for i in wqu.id:
	uniq_c.add(wqu.root(i))
c_sz = []
for i in uniq_c:
	c_sz.append(wqu.sz[i])

def _mul(a):
	return mul(*a)
res = sum(map(_mul, combinations(c_sz, 2)))
if sum(c_sz) < N:
	d = N - sum(c_sz)
	if d >= 2:
		res += d * sum(c_sz) + int(factorial(d) / (factorial(2) * factorial(d - 2)))
	else:
		res += d * sum(c_sz)
print(res)