Zexal的拯救世界

题目

知识点：并查集

在一条数轴上坐落着$N$个国家，分别是$1～N$。一开始所有的国家都处于黑暗状态。接着$Zexal$使用$M$次魔法，第$i$次魔法将会为$[Li,Ri]$这些国家带来光明。请输出每次魔法使用后仍然处于黑暗状态下的国家数量。

输入

输入一行为$N$和$M$。下面$M$行每行两个数$Li、Ri$ $(1<=Li<=Ri<=N<=200000,1<=M<=200000)$

输出

输出$M$行，每次魔法使用后仍然处于黑暗状态下的国家数量。

输入样例

10 3
3 3
5 7
2 8

输出样例

9
6
3

Tips

线段树$（×）$

并查集$（√）$