监听计划 (HNSDFZ #7)

题目描述

黑猫警长Lunk最近发现了$n$个MHA集团，从$1$到$n$编号。鉴于MHA集团数量庞大，Lunk需要先对他们进行全面了解后才可以动手。

Lunk决定派遣间谍渗入MHA集团的通信网络中来监听他们。MHA集团的通信网络是依靠两两集团之间的通信线路构成的。消息可以通过多条通信线路到达其他集团。Lunk的间谍十分强大，他们也可以通过这些通信线路来监听每一个能到达的集团。

然而Lunk是资本家，他不希望花费太多资本用于雇佣间谍。他只想用最少的间谍来监听所有的MHA集团。很不幸的是，这些集团间的通信线路质量不好，有一定的寿命，MHA集团每天都会添加一些新的通信线路来确保通信畅通。因此Lunk希望知道每天通信网络稳定后，最少需要多少个间谍才可以监听所有的集团。

本题采用交互式测评。请在下载一栏中获取样例交互库。

样例交互库包含network.h和implementer.cpp两个文件。选手源程序需要包含network.h这个头文件。

你需要实现以下四个函数：

$\text{initialize}(n, \;q)$：在交互库初始化时会调用该函数，用于初始化你的程序。
- $n$表示MHA集团的数量。
- $q$表示天数，意思是Lunk将只关注第$1$到第$q$天的情况。
$\text{add-connection}(u, \;v, \;t)$：单个数据点中将会被调用$q$次，表示每天MHA集团加入的新的通信线路。
- $u$、$v$表示在编号为$u$和$v$的两个MHA集团间架设通信线路。
- $t$表示通信线路的寿命。如果该线路是第$i$天加入的，那么这条线路只会在$[i, \;i + t)$这段时间内有效。
$\text{query}()$：每次调用完$\text{add-connection}$之后会被调用，用于回答Lunk的询问。
$\text{finalize}()$：交互库结束时将调用该函数，用于释放你程序所使用的资源。

network.h中也有对这四个函数的注释文档。

implementer.cpp是样例交互库。假设你编写的源文件为network.cpp，那么使用以下命令编译：

1	g++ implementer.cpp network.cpp -o exec

exec是可执行文件。

第一行输入两个正整数$n$、$q$，表示集团的个数和总共的天数。

接下来$q$行每行输入三个正整数$u$、$v$和$t$，表示每天通信网络中集团$u$和集团$v$之间添加了一条寿命为$t$的通信网络。

最开始MHA集团之间没有通信线路。

输出$q$行，每行一个正整数，表示每天通信网络变动完毕后最少需要派遣的间谍的人数。

本题共$10$个测试点，其限制如下：

对于所有数据，满足$1 \leqslant t \leqslant 2 \times 10^5$。

时间限制：$1\mathrm{s}$

空间限制：$512\mathrm{MB}$

注意：交互库本身的运行所用时间不会超过$0.1\mathrm{s}$，所用内存不会多于$32\mathrm{MB}$。