Cutting Trees
题号：NC306166
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

有 n 棵树，第 i 棵树有两个参数 l_i,r_i，满足 1\le l_i\le i\le r_i\le n。
你可以选择若干棵树，将它们同时砍倒，并对于其中每棵树决定它们倾倒的方向。若第 i 棵树向左倾倒，则它会覆盖第 l_i\sim i 棵树，否则它会覆盖第 i\sim r_i 棵树。
出于某些原因，你希望每棵未砍倒的树都不会被任何已砍倒的树覆盖。
对于每个 i 求出，如果第 i 棵树必须被砍倒，那么总共至少需要砍倒多少棵树才能满足要求。
每个测试点中有多组测试数据。

输入描述:

第一行，一个整数 T，表示数据组数。
对于每组数据：
第一行，一个整数 n。
接下来 n 行，每行两个整数 l_i,r_i。

输出描述:

对于每组数据：
一行，n 个整数，依次表示每一棵树必须被砍倒时的答案。
示例1

输入

复制 
4
5
1 2
1 3
1 5
3 5
4 5
7
1 1
1 3
2 3
3 5
4 6
5 6
6 7
10
1 2
1 3
2 3
3 4
4 5
6 6
6 8
7 9
9 9
9 10
15
1 1
1 2
1 3
1 5
1 6
4 8
1 10
4 15
1 10
1 10
1 15
1 15
1 15
1 15
1 15

输出

复制 
1 2 3 2 1
1 2 1 2 2 1 1
1 2 1 1 1 1 2 2 1 1
1 1 1 3 3 3 7 7 2 1 5 4 3 2 1

备注:

n\ge 1,\sum n\le 2\times 10^5,1\le l_i\le i\le r_i \le n。