#2810. D

D

题目描述

集训队里面有n\red{n}个人,大家都在A\red{A}B\red{B}两个网站上做题,A\red{A}网站和B\red{B}网站都有自己的rating\red{rating}

集训队里面的每个人都想证明自己比别人强,所以当自己的其中一个网站的分数比另一个人高的时候就会觉得自己比那个人强。如果A\red{A}B\red{B}强,B\red{B}C\red{C}强的话,A\red{A}也会认为他比C\red{C}强,

以此类推,如果对于一个序列P1,P2,...,Pk\red{P_1,P_2,...,P_k}都满足Pi\red{P_i}Pi+1\red{P_{i+1}}强的话,那么P1\red{P_1}就认为比Pk\red{P_k}强。

能否帮每个人计算一下他比多少人强呢?

输入格式

第一行输入一个整数n\red{n}

接下来n\red{n}行,每行两个整数ai,bi\red{a_i,b_i}分别表示这个人在A\red{A}网站和B\red{B}网站的rating\red{rating}

输出格式

输出n\red{n}行,每行表示这个人比多少人强。

样例

输入样例

4
2 3
3 2
1 1
4 5

输出样例

2
2
0
3

提示

对于100%\red{100\%}的数据,1<=n<=100000,1<=ai,bi<=106\red{1<=n<=100000,1<=a_i,b_i<=10^6};

对于40%\red{40\%}的数据,1<=n<=1000.\red{1<=n<=1000.}