#6038. 「雅礼集训 2017 Day5」远行

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

Miranda 生活的城市有 N 个小镇,一开始小镇间没有任何道路连接。随着经济发现,小镇之间陆续建起了一些双向的道路但是由于经济不太发达,在建设过程中,会保证对于任意两个小镇,最多有一条路径能互相到达。有的时候 Miranda 会从某个小镇开始进行徒步旅行,每次出发前,她都想选择一个她能到达的最远的小镇作为终点,并且她在行走过程中是不会走回头路的,为了估算这次旅行的时间,她会需要你告诉她这次旅行的时间会是多少呢?可以假设通过每条道路都需要单位时间,并且 Miranda 不会在小镇停留。

输入格式

第一行一个整数 \text{type} ,表示数据类型。
第二行两个整数 N Q
接下来 Q 行,每行先读入一个整数 t ,若 t = 1 ,则接下来读入两个整数 u v ,表示小镇 u 与小镇 v 建立了一条新道路。若 t = 2 ,读入一个整数 u ,表示 Miranda 要开始一次从小镇 u 出发的旅行。

  • \text{type} = 1 ,记 \text{lastAns} 表示最近一次 Miranda 旅行的时间,那么对于每次操作的 u u, v ,都要异或上 \text{lastAns}
  • \text{type} = 0 ,则不需要对数据进行处理。

输出格式

对于每次询问,输出 Miranda 能到达的最远的小镇的距离是多少。注意 Miranda 可能只能留在开始的小镇。

样例

样例输入

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

样例输出

0
1
0
3
2
3

数据范围与提示

对于 20\% 的数据, N \leq 5000, Q \leq 10000
对于 50\% 的数据, N \leq 100000, Q \leq 200000
对于另外 20\% 的数据, \text{type} = 0
对于 100\% 的数据, N \leq 300000, Q \leq 500000, \text{type} \in \{ 0, 1 \} ,解密后的 u v 满足 1 \leq u, v \leq N ,且道路的修建会满足:每一时刻,都不存在 u, v 使得 u, v 之间能通过多种方式到达。