【题目描述】

有n个点，初始时没有边。有m个操作，操作分为两种：

（1） 在i和j之间增加一条无向边，保证1<=i,j<=n。

（2） 删去最后添加的k条边，保证k<=当前边数。

你想要知道最多能选取多少个两两不连通的点，以及选取的方案数。在每次操作后输出这两个值。方案数对998244353取模。

【输入数据】

第一行两个整数n，m。接下来m行每行第一个数表示操作类型，接下来2或1个数表示i，j或k。

【输出数据】

      对于每个操作，输出一行两个整数，用一个空格隔开。

【样例输入】

3 7

1 1 2

1 1 3

1 3 3

2 1

1 1 2

2 2

2 1

【样例输出】

2 2

1 3

1 3

1 3

1 3

2 2

3 1

【数据范围】

对于20%的数据，n,m<=10。

对于40%的数据，n,m<=1000。

对于100%的数据，n,m<=500000。

【题解】

这是一个维护连通性的问题

我们发现每次都只会删除最近的边

于是我们把每次加的边压入栈中

一条边只会弹出一次

于是我们采用启发式合并维护

【四校联考】点