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 ∈ [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 ≤ m ≤ n ≤ 2 ⋅ 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 ≤ t_i ≤ 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 ≤ a_i, b_i ≤ m, a_i ≠ 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]. 
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
# region fastio

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 SMT:
    def __init__(self,arr):
        self.n=len(arr)-1
        self.arr=[0]*(self.n<<2)
        self.lazy=[0]*(self.n<<2)
        def Build(l,r,rt):
            if l==r:
                self.arr[rt]=arr[l]
                return
            m=(l+r)>>1
            Build(l,m,rt<<1)
            Build(m+1,r,rt<<1|1)
            self.pushup(rt)
        Build(1,self.n,1)

    def pushup(self,rt):
        self.arr[rt]=self.arr[rt<<1]+self.arr[rt<<1|1]

    def pushdown(self,rt,ln,rn):#lr,rn表区间数字数
        if self.lazy[rt]:
            self.lazy[rt<<1]+=self.lazy[rt]
            self.lazy[rt<<1|1]=self.lazy[rt]
            self.arr[rt<<1]+=self.lazy[rt]*ln
            self.arr[rt<<1|1]+=self.lazy[rt]*rn
            self.lazy[rt]=0
            
    def update(self,L,R,c,l=1,r=None,rt=1):#L,R表示操作区间
        if r==None: r=self.n
        if L<=l and r<=R:
            self.arr[rt]+=c*(r-l+1)
            self.lazy[rt]+=c
            return
        m=(l+r)>>1
        self.pushdown(rt,m-l+1,r-m)
        if L<=m: self.update(L,R,c,l,m,rt<<1)
        if R>m: self.update(L,R,c,m+1,r,rt<<1|1)
        self.pushup(rt)

    def query(self,L,R,l=1,r=None,rt=1):
        if r==None: r=self.n
        #print(L,R,l,r,rt)
        if L<=l and R>=r:
            return self.arr[rt]
        m=(l+r)>>1
        self.pushdown(rt,m-l+1,r-m)
        ans=0
        if L<=m: ans+=self.query(L,R,l,m,rt<<1)
        if R>m: ans+=self.query(L,R,m+1,r,rt<<1|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):
    #print('lci',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]
    #print('lc',x,y)
    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])
        #print(idx[i],idx[i+1],lc)
        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])
    
''' 
sys.setrecursionlimit(200000)
import threading
threading.stack_size(10**8)
t=threading.Thread(target=main)
t.start()
t.join()
'''
