logo AlgoBeat OnlineJudge
登录 注册

#102888. [BZOJ 2888] 资源运输

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

题目描述

有一张初始没有边的 个点的图,现在需要支持以下两种操作:

  • A x y,加入一条连接 的边,保证 不在同一连通块且此操作恰好出现 次;
  • Q,询问此时若在 每个连通块 里选择一个关键点,并记录 表示 到所在连通块的关键点的距离时, 的最小值,距离指路径上经过的边的数量。

每次询问独立。

输入格式

第一行两个整数 表示点的数量和操作数。

接下来 行,每行一个操作,格式见题目描述。

输出格式

对于每个询问,输出一行一个整数表示答案。

样例

样例输入 #1

8 10
Q
A 1 2
A 4 5
A 6 7
A 3 4
Q
A 2 5
A 6 8
A 4 6
Q

样例输出 #1

0
4
12

样例解释

对于第一次询问,所有点互不联通,每个点都设为关键点,答案是

对于第二次询问,设置关键点为 ,答案是

对于第三次询问,设置关键点为 ,答案是

数据范围与提示

对于 的数据,