题目描述
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$ 时的答案。
样例 1 输入
0 3 1 6 3 2 5 4
样例 1 输出
1 2 2
样例 1 解释
- $k=1$ 时显然只能选择第一只奶龙。
- $k=2$ 时可以选择前两只奶龙。
- $k=3$ 时，如果选择全部奶龙，则第三只奶龙会攻击第二只奶龙。所以答案最多为 $2$。
样例 2
见 loong/loong2.in 与 loong/loong2.ans。
样例 3
见 loong/loong3.in 与 loong/loong3.ans。
样例 4
见 loong/loong4.in 与 loong/loong4.ans。
样例 5
见 loong/loong5.in 与 loong/loong5.ans。
样例 6
见 loong/loong6.in 与 loong/loong6.ans。
样例 7
见 loong/loong7.in 与 loong/loong7.ans。
数据范围
对于所有测试数据，保证：
- $1 \le n \le 10^6$；
- $1 \le a_i,b_i \le 2n$，所有 $a_i,b_i$ 互不相同。
| 测试点编号 | $n\le$ | 特殊性质 |
|---|---|---|
| $1$ | $20$ | 无 |
| $2\sim 3$ | $400$ | 无 |
| $4$ | $2000$ | B |
| $5\sim 6$ | $2000$ | 无 |
| $7$ | $10^5$ | B |
| $8$ | $10^5$ | C |
| $9\sim 11$ | $10^5$ | 无 |
| $12$ | $10^6$ | A |
| $13$ | $10^6$ | B |
| $14$ | $10^6$ | C |
| $15\sim 17$ | $5\times 10^5$ | 无 |
| $18\sim 20$ | $10^6$ | 无 |
- 特殊性质 A：保证 $a_i> b_i$。
- 特殊性质 B：保证 $a_i< b_i$。
- 特殊性质 C：保证只有不超过 $100$ 只奶龙满足 $a_i>b_i$。