Description

小R有n部手机，为了便于管理，他对一些手机设置了“呼叫转移”的功能。

具体来说，第 i(1≤i≤n) 部手机有个参数 ai(0≤ai≤n,ai≠i) 。若 ai≠0 则表示第 i 部手机接到电话时会将电话无条件转移给第 ai 部手机（此时如果 aai≠0， 会继续进行呼叫转移）。

如果一部手机接到电话会导致至少 109 次呼叫转移，则这次电话无法接通。

现在有m个事件依次发生，具体如下：

∙1 x y表示将第x部手机的参数设置为y，即将 ax 设置为y ;

∙2 x表示询问给第x部手机打电话，最终接到电话的手机编号（如果无法接通，则输出-1 ）。

小R当然知道怎么做啦！但是他想考考你。

Input

输入的第一行有两个整数n, m。保证 1≤n,m≤2∗105 。

接下来一行，包含n个整数，第i个整数为 ai 。

接下来m行，每一行为一个事件，具体格式见问题描述。

对于事件1，保证 1≤x≤n,0≤y≤n,x≠y ；对于事件2，保证 1≤x≤n

Output

对每个询问事件输出一行一个整数，表示最终接到电话的手机编号，如果无法接通，输出-1。

Sample Input

5 6

2 3 4 5 0

2 2

2 5

1 4 3

2 1

1 4 0

2 1

Sample Output

5

5

-1

4

HINT

对于20%的数据， n,m≤5000

对于另外20%的数据，只有2操作

对于所有数据， n,m≤2∗105

正解是LCT…

然而暴力可以过80%的点

然而我却只拿了20分…

注意啊注意啊…

memset这东西是第三次坑我了…

memset跑得真的好慢啊…

#include<stdio.h>

#include<iostream>

#include<string.h>

using namespace std;

const int maxN = (int)2e5;

int fa[maxN + 1];

int vis[maxN + 1];

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("phone.in", "r", stdin);

    freopen("phone.out", "w", stdout);

    #endif

    ios::sync_with_stdio(false);

    int n, m;

    cin >> n >> m;

    for(int i = 1; i <= n; i ++)

        cin >> fa[i];

    for(int i = 1; i <= m; i ++)

    {

        int opt;

        cin >> opt;

        if(opt == 1)

        {

            int u, v;

            cin >> u >> v;

            fa[u] = v;

        }

        if(opt == 2)

        {

            int u;

            cin >> u;

            int flag = 0;

            while(1)

            {

                if(vis[u] == i)

                    break;

                vis[u] = i;

                if(! fa[u])

                {

                    flag = 1;

                    break;

                }

                u = fa[u];

            }

            if(! flag)

                printf("-1\n");

            else

                printf("%d\n", u);

        }

    }

}