J. Best Friends
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have $$$N$$$ friends, numbered $$$1$$$ to $$$N$$$. Each friend chooses exactly one best friend, so the situation can be modeled as a directed graph where every vertex has outdegree $$$1$$$.

For a person $$$v$$$, define $$$\mathrm{indeg}(v)$$$ as the number of people who currently consider $$$v$$$ their best friend (i.e., the indegree of $$$v$$$).

You will process $$$Q$$$ queries of two types:

  • Type 1: 1 x y — person $$$x$$$ changes their best friend to person $$$y$$$.
  • Type 2: 2 — output the MEX of the multiset $$$\{\mathrm{indeg}(1), \mathrm{indeg}(2), \dots, \mathrm{indeg}(N)\}$$$.

The MEX (minimum excluded value) of a multiset of nonnegative integers is the smallest nonnegative integer that does not appear in the multiset.

Input

he first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \le N \le 5 \cdot 10^4$$$, $$$1 \le Q \le 10^5$$$).

The second line contains $$$N$$$ integers $$$f_1, f_2, \dots, f_N$$$ ($$$1 \le f_i \le N$$$), where $$$f_i$$$ is the current best friend of person $$$i$$$.

Each of the next $$$Q$$$ lines describes a query in one of the following forms:

  • 1 x y ($$$1 \le x, y \le N$$$)
  • 2
Output

For every query of type 2, output a single integer — the MEX of the indegrees of all $$$N$$$ people at that moment.

Example
Input
4 5
3 3 4 2
2
1 4 3
2
1 2 1
2
Output
3
2
3