P13842 篱莘龙

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 解释 - $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$ 互不相同。 | 测试点编号 | $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$。