题目描述

自从WC退役以来，大爷是越来越懒惰了。为了帮助他活动筋骨，也是受到了弹飞绵羊一题的启发，机房的小伙伴们

决定齐心合力构造一个下面这样的序列。这个序列共有N项，每项都代表了一个小伙伴的力量值，如果大爷落到了

第i个小伙伴的手里，那么第i个小伙伴会把大爷弹到第i+ai个小伙伴手里，其中ai就是第i个小伙伴的力量值，也

就是序列的第i项。然而，因为大爷太沉了，所以有些小伙伴不能撑到锻（you）炼（xi）结束，所以我们中途会替

换一些小伙伴，也就是改变序列的某些项。而且，因为大爷太沉了，所以有些小伙伴不能把大爷扔向前方，而是会

把大爷往反方向扔，也就是序列中的一些项会是负的（当然，也可能是零喽）。现在机智的大爷通过在空中的观察

，已经知道小伙伴们的所有活动——即初始序列、所有更改操作，他想请你算一算，如果他在某时刻落到了某个位

置，那么他会在几次弹起之后落到小伙伴序列之外（毕竟摔在地上还是蛮疼的）。

输入

第一行为两个整数N和M，代表序列长度和操作次数。

第二行为N个整数，代表初始的小伙伴序列。

接下来有M行，每行代表一个操作。

如果这一行的第一个数是1，代表该操作是一个询问操作，接下来一个数X，代表询问此时大爷从X处，经过几次弹

起会摔在地上。如果永远不会摔在地上，请输出-1。

如果这一行的第一个数是2，代表该操作是一个更改操作，接下来两个数X，Y，代表将序列的第X项改为Y。

N,M <= 200000  |Ai| < N

输出

对于每次询问操作，输出弹起次数或-1。

样例输入

3 19

1 1 1

1 1

1 2

1 3

2 1 2

1 1

1 2

1 3

2 3 -1

1 1

1 2

1 3

2 2 233

1 1

1 2

1 3

2 2 -233

1 1

1 2

1 3

样例输出

3

2

1

2

2

1

-1

-1

-1

3

1

2

3

1

2

 

的进阶版。

可以发现每个联通块要么是一棵树，要么是一棵内向基环树。

树的话直接像弹飞绵羊那样用LCT维护就行了。

对于基环树我们假设多出的那条边是树根指向另一个点，那么对于这条边我们不连接它，而是存起来。

在删除一条边时如果是基环上的边，那么就可以将之前树根存的那条边连上了。

判断能否弹出直接看当前点是在树中还是基环树中即可。

注意因为这是有向边，所以不能随意改变原树的根。

#include
      
       #include