CodeCoder vs TopForces

Competitive programming is popular in Byteland. Every citizen of Byteland is registered on two judge sites, CodeCoder and TopForces. Each site runs its own rating system. On each site every citizen has one integer rating that estimates their skill, and no two citizens share a rating on the same site. A higher rating means a better skill.

Citizens of Byteland are optimistic. Citizen $A$ thinks they have a chance to beat citizen $B$ in a contest if there is a sequence of citizens $A = P_0, P_1, \ldots, P_k = B$ with $k \ge 1$ such that for every $i$ with $0 \le i < k$, citizen $P_i$ has a higher rating than $P_{i+1}$ on at least one of the two sites.

For every citizen, find how many citizens other than themselves they think they have a chance to beat.

The first line contains an integer $n$, the number of citizens ($1 \le n \le 100\,000$).

The $i$-th of the next $n$ lines contains two integers $CC_i$ and $TF_i$, the rating of citizen $i$ on CodeCoder and on TopForces ($1 \le CC_i, TF_i \le 10^6$). On each site the $n$ ratings are pairwise distinct.

Print $n$ lines. The $i$-th line contains $b_i$, the number of citizens other than citizen $i$ that citizen $i$ thinks they have a chance to beat. Print the answers in the input order.