Description

输入输出格式

Input

第一行两个整数n，m。
接下来m行每行两个整数l[i]，r[i]，表示每次操作的区间。

output

共m行，每行一个整数ans[i]，表示第i次操作后新产生出ans[i]对认识的人。

样例

Sample Input

5 5
2 3
2 4
3 5
1 5
2 4

Sample Output

1
2
2
5
0

Hint

• 对于20%的数据，1<=n，m<=100。
• 对于50%的数据，1<=n，m<=5000。
• 对于100%的数据，1<=n，m<=300000，1<=l[i]<=r[i]<=n。

Time: 1s

Memory: 256MB

标程看题解//禁止抄袭