题目描述

Yuki 家里养着 $n$ 只奶龙，第 $i$ 只奶龙的攻击力为 $a_i$，防御力为 $b_i$。

对于第 $i$ 只奶龙和第 $j$ 只奶龙（$i\ne j$），如果 $a_i>b_j$，则第 $i$ 只奶龙会攻击第 $j$ 只奶龙。

你需要对于每个不大于 $n$ 的正整数 $k$ 求出，在第 $1$ 只奶龙到第 $k$ 只奶龙中，最多可以选择多少只奶龙，使得这些奶龙中不存在某只奶龙会攻击另一只奶龙。

输入格式

第一行包含一个正整数 $c$，表示测试点编号。样例满足 $c=0$。

第二行包含一个正整数 $n$。

接下来 $n$ 行，第 $i$ 行包含两个正整数 $a_i,b_i$。保证所有 $a_i,b_i$ 互不相同。

输出格式

输出 $n$ 行，第 $i$ 行包含一个整数，表示 $k=i$ 时的答案。

0
3
1 6
3 2
5 4

1
2
2

提示

样例 1 解释

• $k=1$ 时显然只能选择第一只奶龙。
• $k=2$ 时可以选择前两只奶龙。
• $k=3$ 时，如果选择全部奶龙，则第三只奶龙会攻击第二只奶龙。所以答案最多为 $2$。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 10^6$；
• $1 \le a_i,b_i \le 2n$，所有 $a_i,b_i$ 互不相同。

• 特殊性质 A：保证 $a_i> b_i$。
• 特殊性质 B：保证 $a_i< b_i$。
• 特殊性质 C：保证只有不超过 $100$ 只奶龙满足 $a_i>b_i$。