You have a set of $n$ discs, the $i$-th disc has radius $i$. Initially, these discs are split among $m$ towers: each tower contains at least one disc, and the discs in each tower are sorted in descending order of their radii from bottom to top.

You would like to assemble one tower containing all of those discs. To do so, you may choose two different towers $i$ and $j$ (each containing at least one disc), take several (possibly all) top discs from the tower $i$ and put them on top of the tower $j$ in the same order, as long as the top disc of tower $j$ is bigger than each of the discs you move. You may perform this operation any number of times.

For example, if you have two towers containing discs $[6, 4, 2, 1]$ and $[8, 7, 5, 3]$ (in order from bottom to top), there are only two possible operations:

  move disc $1$ from the first tower to the second tower, so the towers are $[6, 4, 2]$ and $[8, 7, 5, 3, 1]$;  move discs $[2, 1]$ from the first tower to the second tower, so the towers are $[6, 4]$ and $[8, 7, 5, 3, 2, 1]$. 

Let the difficulty of some set of towers be the minimum number of operations required to assemble one tower containing all of the discs. For example, the difficulty of the set of towers $[[3, 1], [2]]$ is $2$: you may move the disc $1$ to the second tower, and then move both discs from the second tower to the first tower.

You are given $m - 1$ queries. Each query is denoted by two numbers $a_i$ and $b_i$, and means "merge the towers $a_i$ and $b_i$" (that is, take all discs from these two towers and assemble a new tower containing all of them in descending order of their radii from top to bottom). The resulting tower gets index $a_i$.

For each $k \in [0, m - 1]$, calculate the difficulty of the set of towers after the first $k$ queries are performed.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($2 \le m \le n \le 2 \cdot 10^5$) — the number of discs and the number of towers, respectively.

The second line contains $n$ integers $t_1$, $t_2$, ..., $t_n$ ($1 \le t_i \le m$), where $t_i$ is the index of the tower disc $i$ belongs to. Each value from $1$ to $m$ appears in this sequence at least once.

Then $m - 1$ lines follow, denoting the queries. Each query is represented by two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le m$, $a_i \ne b_i$), meaning that, during the $i$-th query, the towers with indices $a_i$ and $b_i$ are merged ($a_i$ and $b_i$ are chosen in such a way that these towers exist before the $i$-th query).


-----Output-----

Print $m$ integers. The $k$-th integer ($0$-indexed) should be equal to the difficulty of the set of towers after the first $k$ queries are performed.


-----Example-----
Input
7 4
1 2 3 3 1 4 3
3 1
2 3
2 4

Output
5
4
2
0



-----Note-----

The towers in the example are:

  before the queries: $[[5, 1], [2], [7, 4, 3], [6]]$;  after the first query: $[[2], [7, 5, 4, 3, 1], [6]]$;  after the second query: $[[7, 5, 4, 3, 2, 1], [6]]$;  after the third query, there is only one tower: $[7, 6, 5, 4, 3, 2, 1]$.

Difficulty: HARD
Tags: Tree algorithms

Data structures

Implementation

Spanning trees
Skill types: Data structures

Starter code:

Solutions:
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = [int(x) for x in input().split()]
s = [set() for i in range(m + 1)]
for i in range(n):
	s[a[i]].add(i + 1)
f = [0] * (m + 2)
for i in range(m + 1):
	f[i] = i

def fin(x):
	if f[x] == x:
		return x
	f[x] = fin(f[x])
	return f[x]
ans = 0
for i in range(1, m + 1):
	for j in s[i]:
		if j in s[i] and j - 1 in s[i]:
			ans += 1
out = [n - ans - 1]
for i in range(m - 1):
	(x, y) = map(int, input().split())
	x = fin(x)
	y = fin(y)
	if len(s[x]) < len(s[y]):
		(x, y) = (y, x)
	for i in s[y]:
		if i in s[y] and i - 1 in s[x]:
			ans += 1
		if i in s[y] and i + 1 in s[x]:
			ans += 1
	out.append(n - ans - 1)
	s[x] |= s[y]
	f[y] = x
print('\n'.join((str(x) for x in out)))


from sys import stdin

def main():
	(n, m) = [int(i) for i in stdin.readline().split()]
	a = [int(i) for i in stdin.readline().split()]
	ans = n - 1
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			ans -= 1
	towers = [set() for i in range(m + 1)]
	res = []
	res.append(ans)
	for i in range(n):
		towers[a[i]].add(i)
	for j in range(m - 1):
		(x, y) = [int(i) for i in stdin.readline().split()]
		if len(towers[x]) < len(towers[y]):
			(x, y) = (y, x)
		for i in towers[y]:
			if i - 1 in towers[x]:
				ans -= 1
			if i + 1 in towers[x]:
				ans -= 1
		towers[x] |= towers[y]
		towers[y] = towers[x]
		res.append(ans)
	print('\n'.join((str(i) for i in res)))
main()


class UnionFindNode:

	def __init__(self, group_id, parent=None):
		self.group_id_ = group_id
		self.parent_ = parent
		self.ts = []

	def is_root(self):
		return not self.parent_

	def root(self):
		parent = self
		while not parent.is_root():
			parent = parent.parent_
			self.parent_ = parent
		return parent

	def find(self):
		root = self.root()
		return root.group_id_

	def unite(self, unite_node):
		root = self.root()
		unite_root = unite_node.root()
		if len(root.ts) > len(unite_root.ts):
			(n_root, child) = (root, unite_root)
		else:
			(n_root, child) = (unite_root, root)
		c = 0
		for x in child.ts:
			x = nodes[x].root().group_id_
			if x == n_root.group_id_:
				c += 1
				continue
			n_root.ts.append(x)
		child.parent_ = n_root
		return c
import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
X = list(map(int, input().split()))
nodes = [UnionFindNode(i) for i in range(M)]
for i in range(N - 1):
	if X[i] != X[i + 1]:
		x = nodes[X[i] - 1]
		y = nodes[X[i + 1] - 1]
		x.ts.append(X[i + 1] - 1)
		y.ts.append(X[i] - 1)
R = 0
for i in range(M):
	R += len(nodes[i].ts)
R = R // 2
print(R)
for _ in range(M - 1):
	(a, b) = map(int, input().split())
	(a, b) = (nodes[a - 1], nodes[b - 1])
	R -= a.unite(b)
	print(R)


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
from fractions import Fraction
INF = float('inf')
mod = int(1000000000.0) + 7
(n, m) = mdata()
t = mdata()
t = [i - 1 for i in t]
d = [set() for i in range(m)]
cnt = 0
for i in range(n):
	d[t[i]].add(i)
	if i > 0:
		if t[i] != t[i - 1]:
			cnt += 1
ans = [str(cnt)]
for i in range(m - 1):
	(a1, b1) = mdata()
	(a1, b1) = (a1 - 1, b1 - 1)
	a = d[a1]
	b = d[b1]
	if len(a) < len(b):
		(a, b) = (b, a)
	for i in b:
		cnt -= i + 1 in a
		cnt -= i - 1 in a
	a |= b
	d[a1] = a
	ans.append(str(cnt))
out('\n'.join(ans))


import sys
input = sys.stdin.readline

class Dsu:

	def __init__(self, _n):
		self.n = _n
		self.p = [-1] * _n

	def get(self, v):
		u = v
		while self.p[u] != -1:
			u = self.p[u]
		while self.p[v] != -1:
			nxt = self.p[v]
			self.p[v] = u
			v = nxt
		return u

	def unite(self, v, u):
		v = self.get(v)
		u = self.get(u)
		if v == u:
			return
		self.p[v] = u
(n, m) = map(int, input().split())
real = Dsu(m)
a = list(map(lambda x: int(x) - 1, input().split()))
idxs = [[] for i in range(n)]
for i in range(n):
	idxs[a[i]].append(i)
ans = 0
for i in range(1, n):
	if a[i] != a[i - 1]:
		ans += 1
print(ans)
for _ in range(1, m):
	(v, u) = map(lambda x: int(x) - 1, input().split())
	v = real.get(v)
	u = real.get(u)
	if len(idxs[v]) > len(idxs[u]):
		(v, u) = (u, v)
	real.unite(v, u)
	if v != u:
		for i in idxs[v]:
			if i >= 1 and a[i] == v and (a[i - 1] == u):
				ans -= 1
			if i + 1 < n and a[i] == v and (a[i + 1] == u):
				ans -= 1
		for i in idxs[v]:
			idxs[u].append(i)
			a[i] = u
	print(ans)


import sys
inpy = [int(x) for x in sys.stdin.read().split()]
(n, m) = (inpy[0], inpy[1])
belong = inpy[2:2 + n]
qur = []
for i in range(m - 1):
	qur.append((inpy[i * 2 + 2 + n], inpy[i * 2 + 3 + n]))
contain = [[] for _ in range(m + 1)]
res = 0
for i in range(n - 1):
	if belong[i] != belong[i + 1]:
		res += 1
	contain[belong[i]].append(i)
contain[belong[-1]].append(n - 1)
print(res)
match = {}
for (i, j) in qur:
	(a, b) = (i, j)
	(i, j) = (match.get(i, i), match.get(j, j))
	if len(contain[j]) > len(contain[i]):
		match[a] = j
		(i, j) = (j, i)
	for x in contain[j]:
		if x > 0 and belong[x - 1] == i:
			res -= 1
		if x + 1 < n and belong[x + 1] == i:
			res -= 1
	for x in contain[j]:
		belong[x] = i
		contain[i].append(x)
	contain[j] = []
	print(res)


import sys
from array import array
from typing import List, Tuple, TypeVar, Generic, Sequence, Union

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

class UnionFind(object):
	__slots__ = ['nodes']

	def __init__(self, n: int):
		self.nodes = [-1] * n

	def find(self, x: int) -> int:
		if self.nodes[x] < 0:
			return x
		else:
			self.nodes[x] = self.find(self.nodes[x])
			return self.nodes[x]

	def unite(self, x: int, y: int) -> bool:
		(root_x, root_y, nodes) = (self.find(x), self.find(y), self.nodes)
		if root_x != root_y:
			if nodes[root_x] > nodes[root_y]:
				(root_x, root_y) = (root_y, root_x)
			nodes[root_x] += nodes[root_y]
			nodes[root_y] = root_x
		return root_x != root_y

	def size(self, x: int) -> int:
		return -self.nodes[self.find(x)]

def main():
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	real = list(range(m + 1))
	indexes = [[] for _ in range(m + 1)]
	uf = UnionFind(m + 1)
	difficulty = 0
	for (i, x) in enumerate(a):
		indexes[x].append(i)
		if i > 0 and a[i - 1] != a[i]:
			difficulty += 1
	ans = [difficulty] + [0] * (m - 1)
	for (qi, (u, v)) in enumerate((map(int, input().split()) for _ in range(m - 1)), start=1):
		(x, y) = (uf.find(u), uf.find(v))
		if uf.size(x) > uf.size(y):
			(x, y) = (y, x)
		(real_x, real_y) = (real[x], real[y])
		for i in indexes[real_x]:
			if i > 0 and a[i - 1] == real_y:
				difficulty -= 1
			if i < n - 1 and a[i + 1] == real_y:
				difficulty -= 1
		for i in indexes[real_x]:
			a[i] = real_y
		indexes[real_y] += indexes[real_x]
		indexes[real_x].clear()
		uf.unite(x, y)
		real[uf.find(x)] = real_y
		ans[qi] = difficulty
	sys.stdout.buffer.write('\n'.join(map(str, ans)).encode('utf-8'))
main()


import io, os
import sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main():
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	ANS = n - 1
	for i in range(n - 1):
		if A[i] == A[i + 1]:
			ANS -= 1
	SET = [set() for i in range(m + 1)]
	for i in range(n):
		SET[A[i]].add(i)
	A = [ANS]
	for tests in range(m - 1):
		(x, y) = map(int, input().split())
		if len(SET[x]) <= len(SET[y]):
			for j in SET[x]:
				if j - 1 in SET[y]:
					ANS -= 1
				if j + 1 in SET[y]:
					ANS -= 1
			SET[y] |= SET[x]
			SET[x] = SET[y]
		else:
			for j in SET[y]:
				if j - 1 in SET[x]:
					ANS -= 1
				if j + 1 in SET[x]:
					ANS -= 1
			SET[x] |= SET[y]
			SET[y] = SET[x]
		A.append(ANS)
	sys.stdout.write('\n'.join(map(str, A)))
main()


import sys
input = sys.stdin.readline
M1 = lambda s: int(s) - 1
(N, M) = map(int, input().split())
e = [-1] * N

def find(x):
	if e[x] < 0:
		return x
	e[x] = find(e[x])
	return e[x]

def join(a, b):
	(a, b) = (find(a), find(b))
	if a == b:
		return
	if e[a] > e[b]:
		(a, b) = (b, a)
	e[a] += e[b]
	e[b] = a
T = [[] for _ in range(M)]
for (i, v) in enumerate(map(M1, input().split())):
	if T[v]:
		join(T[v][0], i)
	T[v].append(i)
diff = N - 1
for i in range(N - 1):
	if find(i) == find(i + 1):
		diff -= 1
ans = [str(diff)]
for _ in range(M - 1):
	(i, j) = map(M1, input().split())
	(a, b) = (T[i], T[j])
	if len(a) < len(b):
		(a, b) = (b, a)
	ra = find(a[0])
	for v in b:
		if v > 0 and find(v - 1) == ra:
			diff -= 1
		if v < N - 1 and find(v + 1) == ra:
			diff -= 1
	ans.append(str(diff))
	join(ra, v)
	a.extend(b)
	T[i] = T[j] = a
print('\n'.join(ans))


def get_ints():
	return map(int, input().split())

def main():
	(_, m) = get_ints()
	s = [set() for _ in range(m)]
	(prev, score) = (-1, -1)
	for (index, dest) in enumerate(get_ints()):
		s[dest - 1].add(index)
		if prev != dest:
			score += 1
		prev = dest
	ans = [score]
	for _ in range(m - 1):
		(x, y) = get_ints()
		(x, y) = (x - 1, y - 1)
		target = x
		if len(s[x]) < len(s[y]):
			(x, y) = (y, x)
		for e in s[y]:
			if e - 1 in s[x]:
				score -= 1
			if e + 1 in s[x]:
				score -= 1
		for e in s[y]:
			s[x].add(e)
		s[target] = s[x]
		ans.append(score)
	print(*ans, sep='\n')
main()


class UnionFindVerSize:

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

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

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

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

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

	def calc_group_num(self):
		N = len(self._parent)
		ans = 0
		for i in range(N):
			if self.find_root(i) == i:
				ans += 1
		return ans
import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
t = list(map(int, input().split()))
t = [t[i] - 1 for i in range(n)]
query = []
for i in range(m - 1):
	(a, b) = list(map(int, input().split()))
	query.append((a - 1, b - 1))
tower = [[] for i in range(m)]
for i in range(n):
	id = t[i]
	if not tower[id]:
		tower[id].append((i + 1, i + 1))
	else:
		(start, end) = tower[id].pop()
		if end + 1 == i + 1:
			tower[id].append((start, i + 1))
		else:
			tower[id].append((start, end))
			tower[id].append((i + 1, i + 1))
test = []
for i in range(m):
	for (start, end) in tower[i]:
		if end != n:
			test.append((t[start - 1], t[end]))
start = [-1] * len(test)
end = [m - 1] * len(test)
temp = [[] for i in range(m)]
for i in range(len(test)):
	T = (end[i] + start[i]) // 2
	temp[T].append(i)

def parabisect():
	uf = UnionFindVerSize(m)
	for i in range(m - 1):
		(a, b) = query[i]
		uf.unite(a, b)
		while temp[i]:
			j = temp[i].pop()
			(id1, id2) = test[j]
			if uf.is_same_group(id1, id2):
				end[j] = i
			else:
				start[j] = i
			if end[j] - start[j] > 1:
				T = (end[j] + start[j]) // 2
				temp[T].append(j)
for i in range(20):
	parabisect()
res = [0] * m
for i in range(len(test)):
	res[end[i] + 1] -= 1
for i in range(1, m):
	res[i] += res[i - 1]
for i in range(m):
	print(len(test) + res[i])


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
s = [set() for i in range(m + 1)]
u = [-1] * (m + 1)
for i in range(n):
	s[a[i]].add(i + 1)

def find(x):
	if u[x] <= 0:
		return x
	else:
		u[x] = find(u[x])
		return u[x]
count = 0
for i in range(n - 1):
	if a[i] != a[i + 1]:
		count += 1
ans = [count]
for i in range(1, m):
	(x, y) = map(int, input().split())
	x = find(x)
	y = find(y)
	if len(s[x]) < len(s[y]):
		(x, y) = (y, x)
	for j in s[y]:
		if j - 1 in s[x]:
			count -= 1
		if j + 1 in s[x]:
			count -= 1
	ans.append(count)
	s[x] |= s[y]
	u[y] = x
for i in ans:
	print(i)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def main():
	(n, m) = RL()
	arr = RLL()
	pa = [i for i in range(m + 1)]
	rec = [set() for _ in range(m + 1)]
	ct = n - 1
	for i in range(1, n):
		if arr[i - 1] == arr[i]:
			ct -= 1
	for i in range(n):
		rec[arr[i]].add(i + 1)
	res = [ct]

	def find(a):
		if a != pa[a]:
			pa[a] = find(pa[a])
		return pa[a]
	for _ in range(m - 1):
		(a, b) = RL()
		(pra, prb) = (find(a), find(b))
		if len(rec[pra]) > len(rec[prb]):
			(pra, prb) = (prb, pra)
		for i in rec[pra]:
			if i + 1 in rec[prb]:
				ct -= 1
			if i - 1 in rec[prb]:
				ct -= 1
		res.append(ct)
		pa[pra] = prb
		rec[prb] |= rec[pra]
	for i in res:
		print(i)
main()


class UnionFind:

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

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

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

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

	def Count(self, x):
		return -self.root[self.Find_Root(x)]
import sys
input = sys.stdin.buffer.readline
(N, M) = map(int, input().split())
T = list(map(int, input().split()))
Query = [list(map(int, input().split())) for _ in range(M - 1)]
uni = UnionFind(M)
dic = {}
for (i, t) in enumerate(T):
	if t in dic:
		dic[t].add(i)
	else:
		dic[t] = {i}
uniToKey = [i for i in range(M + 1)]
ans = N - 1
for L in dic.values():
	for node in L:
		if node - 1 in L:
			ans -= 1
print(ans)
for (a, b) in Query:
	a = uni.Find_Root(a)
	b = uni.Find_Root(b)
	ka = uniToKey[a]
	kb = uniToKey[b]
	if len(dic[ka]) < len(dic[kb]):
		newkey = kb
		for node in dic[ka]:
			if node - 1 in dic[kb]:
				ans -= 1
			if node + 1 in dic[kb]:
				ans -= 1
		for node in dic[ka]:
			dic[kb].add(node)
	else:
		newkey = ka
		for node in dic[kb]:
			if node - 1 in dic[ka]:
				ans -= 1
			if node + 1 in dic[ka]:
				ans -= 1
		for node in dic[kb]:
			dic[ka].add(node)
	uni.Unite(a, b)
	r = uni.Find_Root(a)
	uniToKey[r] = newkey
	print(ans)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.readline
	(N, M) = map(int, input().split())
	T = list(map(int, input().split()))
	ans = N - 1
	S = [set() for _ in range(M + 1)]
	for (i, t) in enumerate(T):
		S[t].add(i + 1)
	for i in range(1, M + 1):
		for x in S[i]:
			if x + 1 in S[i]:
				ans -= 1
	print(ans)
	for _ in range(M - 1):
		(a, b) = map(int, input().split())
		if len(S[a]) < len(S[b]):
			(S[a], S[b]) = (S[b], S[a])
		for x in S[b]:
			if x - 1 in S[a]:
				ans -= 1
			if x + 1 in S[a]:
				ans -= 1
		for x in S[b]:
			S[a].add(x)
		print(ans)
main()


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 0
	for w in arr:
		c += ceil(w / x)
	return c

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

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

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

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

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [(ch, len(list(g))) for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

@bootstrap
def dfs(x, y):
	global T
	tin[x] = T
	T += 1
	up[x][0] = y
	for i in range(1, 19):
		up[x][i] = up[up[x][i - 1]][i - 1]
	for ch in g[x]:
		yield dfs(ch, x)
	tout[x] = T
	T += 1
	yield None

def isa(x, y):
	return tin[x] <= tin[y] and tout[x] >= tout[y]

def lca(x, y):
	if isa(x, y):
		return x
	for i in range(18, -1, -1):
		if not isa(up[x][i], y):
			x = up[x][i]
	return up[x][0]
t = 1
for i in range(t):
	(n, m) = RL()
	t = RLL()
	idx = [0] * n
	for i in range(n):
		idx[i] = t[i] - 1
	cur = list(range(m))
	g = [[] for i in range(2 * m - 1)]
	for i in range(m - 1):
		(x, y) = RL()
		x -= 1
		y -= 1
		nidx = m + i
		g[nidx].append(cur[x])
		g[nidx].append(cur[y])
		cur[x] = nidx
	root = 2 * m - 2
	tin = [0] * (2 * m - 1)
	tout = [0] * (2 * m - 1)
	up = [[0] * 19 for i in range(2 * m - 1)]
	T = 0
	dfs(root, root)
	psum = [0] * m
	for i in range(n - 1):
		lc = lca(idx[i], idx[i + 1])
		if lc < m:
			psum[0] += 1
		else:
			psum[lc - m + 1] += 1
	for i in range(m - 1):
		print(n - 1 - psum[i])
		psum[i + 1] += psum[i]
	print(n - 1 - psum[m - 1])


from sys import stdin, gettrace
from itertools import accumulate, islice
if gettrace():
	inputi = input
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

class Stree:

	def __init__(self, f, n, default, init_data):
		self.ln = 2 ** (n - 1).bit_length()
		self.f = f
		self.data = [default for _ in range(2 * self.ln)]
		self.data[self.ln:self.ln + n] = init_data
		for j in range(self.ln - 1, 0, -1):
			self.data[j] = f(self.data[j * 2], self.data[j * 2 + 1])

	def update(self, i, a):
		p = self.ln + i
		self.data[p] = a
		while p > 1:
			p = p // 2
			self.data[p] = self.f(self.data[p * 2], self.data[p * 2 + 1])

	def get(self, i, j):

		def _get(l, r, p):
			if i <= l and j >= r:
				return self.data[p]
			else:
				m = (l + r) // 2
				if j <= m:
					return _get(l, m, p * 2)
				elif i >= m:
					return _get(m, r, p * 2 + 1)
				else:
					return self.f(_get(l, m, p * 2), _get(m, r, p * 2 + 1))
		return _get(0, self.ln, 1)

def euler_dfs(adj, root=0):
	n = len(adj)
	parent = [None] * n
	depth = [-1] * n
	depth[0] = 0
	stack = [(root, adj[root])]
	euler = []
	eulerfirst = [-1] * n
	while stack:
		(p, aa) = stack.pop()
		if eulerfirst[p] == -1:
			eulerfirst[p] = len(euler)
		euler.append(p)
		for c in aa[::-1]:
			if c != parent[p]:
				parent[c] = p
				depth[c] = depth[p] + 1
				stack.append((p, []))
				stack.append((c, adj[c]))
	return (euler, eulerfirst, parent, depth)

class Lca:

	def __init__(self, adj, root=0):
		self.adj = adj
		(self.euler, self.eulerfirst, self.parent, self.depth) = euler_dfs(adj, root)

		def f(l, r):
			if self.depth[l] < self.depth[r]:
				return l
			else:
				return r
		self.stree = Stree(f, len(self.euler), 0, self.euler)
		self.cache = {}

	def lca(self, a, b):
		if (a, b) in self.cache:
			return self.cache[a, b]
		if a == b:
			return a
		fa = self.eulerfirst[a]
		fb = self.eulerfirst[b]
		if fb < fa:
			(fa, fb) = (fb, fa)
		res = self.stree.get(fa, fb)
		self.cache[a, b] = res
		return res

	def dist(self, a, b):
		return self.depth[a] + self.depth[b] - 2 * self.depth[self.lca(a, b)]

def main():
	(n, m) = map(int, inputi().split())
	tt = [int(a) - 1 for a in inputi().split()]
	cur = list(range(m))
	tree = [[] for _ in range(m * 2 - 1)]
	for i in range(m - 1):
		(a, b) = map(lambda x: int(x) - 1, inputi().split())
		tree[m + i] = [cur[a], cur[b]]
		cur[a] = m + i
	lca = Lca(tree, 2 * m - 2)
	seq = [0] * (m * 2 - 1)
	for i in range(n - 1):
		j = lca.lca(tt[i], tt[i + 1])
		seq[j] += 1
	tseq = list(accumulate(seq))
	for ts in tseq[m - 1:2 * m - 1]:
		print(n - 1 - ts)
main()


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main():
	(n, m) = map(int, input().split())
	towers = [set() for i in range(m + 1)]
	t = [int(i) for i in input().split() if i != '\n']
	ans = 0
	for i in range(n):
		towers[t[i]].add(i + 1)
		if i > 0:
			if t[i - 1] != t[i]:
				ans += 1
	output = [ans]
	for ii in range(m - 1):
		(a, b) = map(int, input().split())
		if len(towers[a]) < len(towers[b]):
			for j in towers[a]:
				if j != 1:
					if j - 1 in towers[b]:
						ans -= 1
				if j != n:
					if j + 1 in towers[b]:
						ans -= 1
			towers[b] |= towers[a]
			towers[a] = towers[b]
		else:
			for j in towers[b]:
				if j != 1:
					if j - 1 in towers[a]:
						ans -= 1
				if j != n:
					if j + 1 in towers[a]:
						ans -= 1
			towers[a] |= towers[b]
			towers[b] = towers[a]
		output.append(ans)
	sys.stdout.write('\n'.join(map(str, output)))
main()


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def MI1():
	return map(int1, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

class LCA:

	def __init__(self, to, root=0):
		self.memo = {}
		self.to = to
		self.n = len(to)
		self.parents = [-1] * (self.n + 1)
		self.depth = [0] * self.n
		self.__dfs(root)
		self.max_level = max(self.depth).bit_length()
		self.ancestor = [self.parents] + [[-1] * (self.n + 1) for _ in range(self.max_level)]
		row0 = self.ancestor[0]
		for lv in range(self.max_level):
			row1 = self.ancestor[lv + 1]
			for u in range(self.n):
				row1[u] = row0[row0[u]]
			row0 = row1

	def __dfs(self, root):
		stack = [root]
		while stack:
			u = stack.pop()
			pu = self.parents[u]
			du = self.depth[u]
			for v in self.to[u]:
				if v == pu:
					continue
				self.parents[v] = u
				self.depth[v] = du + 1
				stack.append(v)

	def anc(self, u, v):
		diff = self.depth[u] - self.depth[v]
		if diff < 0:
			(u, v) = (v, u)
		if (u, v) in self.memo:
			return self.memo[u, v]
		diff = abs(diff)
		lv = 0
		while diff:
			if diff & 1:
				u = self.ancestor[lv][u]
			(lv, diff) = (lv + 1, diff >> 1)
		if u == v:
			self.memo[u, v] = u
			return u
		for lv in range(self.depth[u].bit_length() - 1, -1, -1):
			anclv = self.ancestor[lv]
			if anclv[u] != anclv[v]:
				(u, v) = (anclv[u], anclv[v])
		self.memo[u, v] = self.parents[u]
		return self.parents[u]
(n, m) = MI()
tt = LI1()
pos = list(range(m))
to = [[] for _ in range(2 * m - 1)]
for i in range(m, 2 * m - 1):
	(u, v) = MI1()
	pu = pos[u]
	pv = pos[v]
	to[i].append(pu)
	to[i].append(pv)
	pos[u] = i
lca = LCA(to, 2 * m - 2)
cnt = [0] * m
for (t0, t1) in zip(tt, tt[1:]):
	if t0 == t1:
		cnt[0] += 1
	else:
		a = lca.anc(t0, t1) - m + 1
		cnt[a] += 1
ans = n - 1
for c in cnt:
	ans -= c
	print(ans)


import sys
from collections import defaultdict as dd
from bisect import *
pl = 1
from math import *
from copy import *
if pl:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('outpt.txt', 'w')

def li():
	return [int(xxx) for xxx in input().split()]

def fi():
	return int(input())

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def inc(u):
	return ord(u) - ord('a')
t = 1

def find(i):
	if i == pos[i]:
		return pos[i]
	pos[i] = find(pos[i])
	return pos[i]

def union(x, y):
	global ans
	xs = find(x)
	ys = find(y)
	if xs != ys:
		if rank[xs] < rank[ys]:
			(ys, xs) = (xs, ys)
		for i in dsu[ys]:
			dsu[xs].append(i)
			if i > 1 and a[i - 2] == xs:
				ans -= 1
			if i < n and a[i] == xs:
				ans -= 1
		rank[xs] += 1
		pos[ys] = xs
		for i in dsu[ys]:
			a[i - 1] = xs
		dsu[ys] = []
t = 1
while t > 0:
	t -= 1
	(n, m) = mi()
	pos = [i for i in range(n + 1)]
	dsu = [[] for i in range(m + 1)]
	rank = [0 for i in range(m + 1)]
	a = li()
	ans = 0
	for i in range(n):
		if i != 0:
			if a[i] != a[i - 1]:
				ans += 1
		dsu[a[i]].append(i + 1)
	print(ans)
	for j in range(m - 1):
		(p, q) = li()
		union(p, q)
		print(ans)


import sys

def input():
	return sys.stdin.readline().rstrip()

def input_split():
	return [int(i) for i in input().split()]
(n, m) = input_split()
indices = input_split()
towers = [[] for i in range(m)]
for i in range(n):
	ind = indices[i] - 1
	towers[ind].append(i)
jumps = [0 for i in range(m)]
for i in range(m):
	temp = towers[i]
	for j in range(1, len(temp)):
		if temp[j] != temp[j - 1] + 1:
			jumps[i] += 1
answers = [sum(jumps) - 1 + m]
new_towers = [set(towers[i]) for i in range(m)]
queries = []
for _ in range(m - 1):
	(a, b) = input_split()
	a -= 1
	b -= 1
	queries.append((a, b))
for (a, b) in queries:
	(orig_a, orig_b) = (a, b)
	swapped = False
	if len(new_towers[a]) < len(new_towers[b]):
		pass
	else:
		(b, a) = (a, b)
		swapped = True
	new_gaps = 0
	for el in new_towers[a]:
		if el == 0:
			if 1 in new_towers[b]:
				new_gaps -= 0
			else:
				new_gaps += 1
		elif el == n - 1:
			if n - 2 in new_towers[b]:
				new_gaps -= 0
			else:
				new_gaps += 1
		elif el - 1 in new_towers[b] and el + 1 in new_towers[b]:
			new_gaps -= 1
		elif el - 1 in new_towers[b] or el + 1 in new_towers[b]:
			new_gaps += 0
		else:
			new_gaps += 1
		new_towers[b].add(el)
	jumps_in_new_tower = jumps[b] + new_gaps
	answers.append(answers[-1] - (jumps[a] + jumps[b] + 2) + (jumps_in_new_tower + 1))
	jumps[orig_a] = jumps_in_new_tower
	if not swapped:
		new_towers[a] = new_towers[b]
print(*answers, sep='\n')