资源运输

内存限制：128 MiB 时间限制：10 Sec

小Y盯上了最近发行的即时战略游戏——ResourceTransport。但在前往通关之路的道路上，一个小游戏挡住了小Y的步伐。“国家的本质是生产与收集资源”是整款游戏的核心理念，这个小游戏也不例外。简单的说，用户需要管理一个国家，使其繁荣富强。

一个国家含有N个城市，游戏开始时城市间没有任何道路。城市可以通过高速公路连接。为了减少建设费用，每对城市间最多存在一条路径。

小Y拥有极强的游戏天赋，很快就把所有城市的生产能力提到了满级，把高速公路的建设费用修改成了0。

悲剧的是，对于每个连通的城市群，都要把该城市群中的某个城市设立成资源集合处，小Y把这件事忘了；更悲剧的是，建造高速公路这件事，小Y也忘了。

可小Y是个完美主义者，他请来了你帮他设立资源集合处，自己负责建造高速公路。假设连通城市群中的某个城市i到该城市群的资源集合处最少需要经过Di条高速公路，那么总运输费用为Sigma(Di)。你需要在每个连通城市群中设立一个资源集合处，使得总费用最小。小Y有时会向你询问此时最小的总费用。

问题很简单，麻烦的是小Y会在你好不容易算出最小总费用时建造一条新的高速公路。由于每个连通的城市群只能有一个资源集合处，所以最小总费用又得重新计算，这可真是个苦差事……

第一行两个整数N，M分别表示国家中的城市数与小Y的操作数。

接下来M行，每行可能为：

1.A x y：表示在城市x和城市y间建造一条高速公路，保证此操作出现N-1次；

2.Q：表示小Y询问此时的最小总费用。

对于每个Q操作，单独输出一行一个整数Ans，表示所求的答案。

样例输入

样例输出


			

0

4

12

【样例解释】

       1.开始所有城市互不联通，每个城市都是资源集合处，费用为0；

2.后来分别把城市1、城市4、城市7、城市8设立为资源集合处，费用为4；

3.最后把城市4设立为资源集合处，费用为12。

N<=40000,M<=80000

#2888. 资源运输

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示