题目描述

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

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

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

输入格式

从 loong.in 中读入数据。

• 第一行包含一个正整数 $c$，表示测试点编号。样例满足 $c=0$。
• 第二行包含一个正整数 $n$。
• 接下来 $n$ 行，第 $i$ 行包含两个正整数 $a_i,b_i$。保证所有 $a_i,b_i$ 互不相同。

输出格式

输出到 loong.out 中。

输出 $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$		无
$7$	$2\times 10^5$	C
$8\sim 10$		无
$11$	$10^6$	A
$12$		B
$13$		C
$14\sim 16$	$5\times 10^5$	无
$17\sim 20$	$10^6$

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