这是一道交互题。
新首都跳蚤利亚需要建立地铁线路！hehe 蚤负责了这个项目。
跳蚤利亚有 $n$ 个地铁站，还有 $m$ 条线路计划设立，第 $i$ 条铁轨将在 $u_i$ 和 $v_i$ 之间建立一条双向线路（$u_i\neq v_i$）。可能有两条线路连接的地铁站相同。
由于跳蚤利亚是面向未来的节能环保城市，hehe 蚤希望地铁的建设也要避免浪费。hehe 蚤仔细地审查工程建设方案，并定义了什么叫做“绿色区间”：对于任何满足 $1 \le l \le r \le m$ 的整数 $l, r$，我们称 $[l, r]$ 是一个区间；如果在只修建所有 $u_i, v_i \in [l, r]$ 的线路的情况下，地铁网络不包含环，那么我们称这个区间是绿色的。
hehe 蚤突然好奇：有多少个区间 $[l, r]$ 是绿色的呢？但这样的好奇持续了 $10^{-9}$ 秒后， hehe 蚤就想到了做法。如果一个区间是绿色的，那它的子区间也是绿色的。于是可以用双指针，对于所有的区间左端点 $l\in[1,m]$，计算出使得 $[l, r]$ 是绿色的最大的右端点值 $r$ 即可。而维护是否有环这一信息，只需使用跳蚤国最新自研数据结构 hehe 树。
作为跳蚤国顶级科学家之一，hehe 蚤刚在大量系统中植入了 hehe 树，所以这问题已经变得没意思了。为了挑战自我，hehe 蚤拿出了一台植入 hehe 树失败的机器，仅包含部分 hehe 树功能。具体来说，这台机器支持：
给定 $id$，在图中建立双向线路 $u_{id}, v_{id}$，注意，如果假如建立后图中产生了环，机器会报错。
拆除图中加入时间最晚的一条双向线路。
给定 $id$，询问 $u_{id}, v_{id}$ 两点间是否可以通过已经建立的双向线路连通。
拿出了这台机器后，hehe 蚤又得出了一个基于分治的强大的做法，并给出了答案。hehe 蚤大呼简单。
但 hehe 蚤又想了想，觉得自己应该在跳蚤国内弘扬这股 “麻烦自己，麻烦别人” 的挑战精神。于是 hehe 蚤把这台机器交给了你。他会从小到大依次对每个左端点 $l\in [1,m]$，向你询问，所有以 $l$ 为左端点的绿色区间 $[l, r]$ 中最大的右端点值 $r$。因为 hehe 蚤觉得这个问题太简单，所以在你计算答案 $r$ 时，你不可以让机器加入编号大于 $r$ 的线路。
一句话题意：有一个长度为 $m$ 的边序列，你需要使用交互库提供的可撤销并查集接口，在线地对于每个 $l$ 求出最大的 $r$，使得区间 $[l,r]$ 内的边不形成环。
任务
本题仅支持 C++。
你必须引用 subway.h 头文件。
你需要实现下面的过程：
void init(int n, int m, int lim);这个过程将在所有 solve 调用前，恰好被调用一次。
其中 $n$ 表示地铁站数量，$m$ 表示线路数量，$\textit{lim}$ 表示你可以使用 merge 次数的上限。
int solve(int l);这个过程将被调用恰好 $m$ 次，且第 $i$ 次调用的 l 一定是 $i$。你需要返回 $r_l$ 表示最大的 $r$ 满足区间 $[l,r]$ 中的边不成环。
你可以在 solve 的过程中调用以下过程和交互库交互：
void merge(int x);这个函数的作用是建立双向线路 $u_x,v_x$。
这个函数只能在 solve 过程中被调用，并且必须满足 $x\in [l, r_l]$，其中 $l$ 是当前 solve 过程的参数，以及加入这条边不会使 hehe 树维护的图成环，否则你的交互过程会被判定为失败。
你调用这个函数的次数不能超过 $\textit{lim}$ 次，并且如果你调用这个函数的次数超过了 $2\times 10^7$，你的交互过程将被判定为不合法。
void undo();这个函数将撤销最后一次没有被撤销的 merge 操作，如果没有可以被撤销的 merge 操作，你的交互过程会被判定为失败。
bool check(int x);如果 $u_x$ 和 $v_x$ 联通，函数将返回 false，否则返回 true。
换言之，返回值表示加入第 $x$ 条线路是否不会成环。
不同 solve 轮次间 hehe 蚤维护的图将被保留，并且初始不包含任何边。
评测方式
样例评测库将读入如下格式的输入数据：
第一行包括三个正整数 $n,m$ 和 $\textit{lim}$，分别表示地铁站个数，线路条数和交互限制。
接下来 $m$ 行，每行两个整数 $u_i,v_i$，表示一条线路。
样例评测库将输出如下格式的输出数据：
对于每一组数据，如果你交互过程合法，交互库将输出 Success 或 Too many merge，并在第二行输出你调用 merge 的次数，第三行输出你求出的答案，否则会输出 Wrong Answer [id]，你可以查阅样例评测库来确定错误类型。
最终测试中，线路序列是确定的，不会因为你的询问而改变。
样例
input
4 4 1000 1 2 2 3 3 4 4 2
output
Success Count of merge: 6 3 3 4 4
explanation
以下是一个合法的交互过程。
| 交互库调用 | 选手调用 | 返回 | 并查集状态 |
|---|---|---|---|
init(4, 4, 1000) |
$~$ | $~$ | $(1),(2),(3),(4)$ |
solve(1) |
$~$ | $~$ | $(1),(2),(3),(4)$ |
| $~$ | merge(1) |
$~$ | $(1,2),(3),(4)$ |
| $~$ | check(2) |
true |
$(1,2),(3),(4)$ |
| $~$ | merge(2) |
$~$ | $(1,2,3),(4)$ |
| $~$ | check(3) |
true |
$(1,2,3),(4)$ |
| $~$ | merge(3) |
$~$ | $(1,2,3,4)$ |
| $~$ | check(4) |
false |
$(1,2,3,4)$ |
solve |
$~$ | 3 |
$(1,2,3,4)$ |
solve(2) |
$~$ | $~$ | $(1,2,3,4)$ |
| $~$ | undo() |
$~$ | $(1,2,3),(4)$ |
| $~$ | undo() |
$~$ | $(1,2),(3),(4)$ |
| $~$ | undo() |
$~$ | $(1),(2),(3),(4)$ |
| $~$ | merge(3) |
$~$ | $(1),(2),(3,4)$ |
| $~$ | merge(2) |
$~$ | $(1),(2,3,4)$ |
| $~$ | check(4) |
false |
$(1),(2,3,4)$ |
solve |
$~$ | 3 |
$(1),(2,3,4)$ |
solve(3) |
$~$ | $~$ | $(1),(2,3,4)$ |
| $~$ | undo() |
$~$ | $(1),(2),(3,4)$ |
| $~$ | check(4) |
false |
$(1),(2),(3,4)$ |
| $~$ | merge(4) |
$~$ | $(1),(2,3,4)$ |
solve |
$~$ | 4 |
$(1),(2,3,4)$ |
solve(4) |
$~$ | $~$ | $(1),(2,3,4)$ |
solve |
$~$ | 4 |
$(1),(2,3,4)$ |
其中 solve 的返回值均在若干行后的，标注着交互库调用 solve 的行。
数据范围与提示
保证若你的交互过程满足题目限制，且 check 次数不超过 $8\times 10^6$，交互库不会占用超过 $\texttt{1s}$ 时间和 $\texttt{32MB}$ 空间。
| 子任务编号 | $n\leq$ | $m\leq$ | $\textit{lim}\geq$ | 特殊性质 | 分值 |
|---|---|---|---|---|---|
| $1$ | $1000$ | $1000$ | $10^6$ | 无 | $10$ |
| $2$ | $10^4$ | $2\times 10^4$ | $5\times 10^6$ | 无 | $30$ |
| $3$ | $10^5$ | $2\times 10^5$ | $5\times 10^6$ | 数据随机 | $30$ |
| $4$ | $10^5$ | $2\times 10^5$ | $5\times 10^6$ | 无 | $30$ |
对于所有数据，$2\leq n, m,lim \leq 5\times 10^6$。
时间限制：$\texttt{3s}$
空间限制：$\texttt{512MB}$
鄂公网安备 42010202000505 号