问题 28493 --「ZJOI2016」大森林

28493: 「ZJOI2016」大森林

时间限制: 1 Sec  内存限制: 256 MB
提交: 1  解决: 1
[提交][状态][讨论版][数据上传:][下载FPS0元][下载测试数据0元][31590kb]

题目描述

小 Y 家里有一个大森林,里面有 nnn 棵树,编号从 111nnn。一开始这些树都只是树苗,只有一个节点,标号为 111。这些树都有一个特殊的节点,我们称之为生长节点,这些节点有生长出子节点的能力。小 Y 掌握了一种魔法,能让第 lll 棵树到第 rrr 棵树的生长节点长出一个子节点。同时她还能修改第 lll 棵树到第 rrr 棵树的生长节点。她告诉了你她使用魔法的记录,你能不能管理她家的森林,并且回答她的询问呢?

输入

第一行包含两个正整数 n,mn,mn,m,表示共有 nnn 棵树和 mmm 个操作。

接下来 mmm 行,每行包含若干非负整数表示一个操作,操作格式为:

0 l r表示将第 lll 棵树到第 rrr 棵树的生长节点下面长出一个子节点,子节点的标号为上一个 000 号操作叶子标号加 111(例如,第一个 000 号操作产生的子节点标号为 222), lllrrr 之间的树长出的节点标号都相同。保证 1≤l≤r≤n1 \leq l \leq r \leq n1lrn

1 l r x表示将第 lll 棵树到第 rrr 棵树的生长节点改到标号为 xxx 的节点。对于 iii (l≤i≤r)(l \leq i \leq r)(lir) 这棵树,如果标号 xxx 的点不在其中,那么这个操作对该树不产生影响。保证 1≤l≤r≤n1 \leq l \leq r \leq n1lrnxxx 不超过当前所有树中节点最大的标号。

2 x u v询问第 xxx 棵树中节点 uuu 到节点 vvv 点的距离,也就是在第 xxx 棵树中从节点 uuu 和节点 vvv 的最短路上边的数量。保证 1≤x≤n1 \leq x \leq n1xn,这棵树中节点 uuu 和节点 vvv 存在。

输出

输出包括若干行,按顺序对于每个小 Y 的询问输出答案

样例输入

5 5
0 1 5
1 2 4 2
0 1 4
2 1 1 3
2 2 1 3

样例输出

1
2

提示




N≤105, M≤2×105N \leq 10^5, \ M \leq 2 \times 10^5N105, M2×105



来源

[提交][状态]