Dream Pudding

Problem Source

HNOI2009

Problem Description

There are $n$ puddings placed in a row, and $m$ operations are performed. Each operation turns all the puddings of one colour into another colour, and then asks how many colour segments there are in total at the moment.

For example, four puddings with colours $1, 2, 2, 1$ form $3$ colour segments in total.

Input Format

The first line contains two integers $n, m\ (1 \le n, m \le 10^5)$, the number of puddings and the number of operations.

The second line contains $n$ integers $a_1, a_2, \dots, a_n\ (1 \le a_i \le 10^6)$, the colour of the $i$-th pudding.

The following $m$ lines describe one operation each. Each line begins with an integer $op$ indicating the operation type:

• If $op = 1$, then two integers $x, y$ follow, meaning change all puddings of colour $x$ into colour $y$. It is guaranteed that $1 \le x, y \le 10^6$, and $x$ may equal $y$.
• If $op = 2$, it means a query.

Output Format

For each operation of the second type (a query), output in order how many colour segments there are at that moment.

Sample Input

4 3
1 2 2 1
2
1 2 1
2

Sample Output

3
1