这是一个交互式问题。

现有 $n$ 个集合，编号从 $1$ 到 $n$，其中第 $i$ 个集合仅包含整数 $i$。你需要处理 $q$ 次查询。第 $i$ 次查询（从 $1$ 开始计数）由一对整数 $(X_i, Y_i)$ 描述。它会创建一个编号为 $n + i$ 的新集合，该集合由集合 $X_i$ 和 $Y_i$ 中的整数并集组成。

每次创建一个新集合时，你必须报告该集合中不同整数的数量。你不需要报告精确结果。如果集合的正确大小为 $A$，而你输出的整数为 $B$，只要满足 $0.5 \cdot A \le B \le 2.0 \cdot A$，该回答即被视为正确。

在某些评测系统上刷新输出可能会产生较大开销，因此所有查询被分为每批 $50$ 个。你的程序应当读取前 $50$ 个查询，输出这 $50$ 个查询的答案并刷新输出，然后读取下一批 $50$ 个查询，以此类推。最后一批查询的数量可能少于 $50$ 个。

交互器是非自适应的，这意味着对于每个测试点，查询序列在所有运行中都是相同的。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 50\,000, 1 \le q \le 5 \cdot 10^5$)，分别表示初始集合的数量和查询的数量。

接下来的 $q$ 行包含查询。第 $i$ 行包含两个整数 $X_i$ 和 $Y_i$ ($1 \le X_i, Y_i < n + i$)。

输出格式

对于每次查询，输出一个整数，占一行，表示你对所创建集合大小的估计值。

请记得每 $50$ 次查询后刷新输出！

样例

输入 1

4 5
1 2
2 3
5 6
6 7
4 7

输出 1

2
2
3
3
4