|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
MOG Training #2Ended |
C - CodeCoder vs TopForces
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Competitive programming is very popular in Byteland. In fact, every Bytelandian citizen is registered at two programming sites — CodeCoder and TopForces. Each site maintains its own proprietary rating system. Each citizen has a unique integer rating at each site that approximates their skill. Greater rating corresponds to better skill.
People of Byteland are naturally optimistic. Citizen $A$ thinks that he has a chance to beat citizen $B$ in a programming competition if there exists a sequence of Bytelandian citizens $A = P_0, P_1, \ldots, P_k = B$ for some $k \geq 1$ such that for each $i$ ($0 \leq i < k$), $P_i$ has higher rating than $P_{i + 1}$ at one or both sites.
Each Bytelandian citizen wants to know how many other citizens they can possibly beat in a programming competition.
Input
The first line of the input contains an integer $n$ — the number of citizens ($1 \leq n \leq 100\,000$). The following $n$ lines contain information about ratings. The $i$-th of them contains two integers $CC_i$ and $TF_i$ — ratings of the $i$-th citizen at CodeCoder and TopForces ($1 \leq CC_i, TF_i \leq 10^6$). All the ratings at each site are distinct.
Output
For each citizen $i$ output an integer $b_i$ — how many other citizens they can possibly beat in a programming competition. Each $b_i$ should be printed in a separate line, in the order the citizens are given in the input.
Sample test(s)
Input
4
2 3
3 2
1 1
4 5
Output
2
2
0
3