Problem K
Wrangler Rating

Competitive wrangling is a very popular sport – almost as popular as competitive programming. Because wrangling matches are between exactly two people, a rating system is used to determine who the best wranglers are. The original system had two rules:

1. A new wrangler starts with a rating of $1500$.

2. After a match, the winner’s rating is updated to $\max \{ x, \lfloor \frac{3y + x}{2} \rfloor \} $ and the loser’s rating is updated to $\min \{ y, \lfloor \frac{x/3 + y}{2} \rfloor \} $, where $x$ is the original rating of the winner and $y$ is the original rating of the loser.

This system was known for being unfair to new wranglers, so the old ratings were deleted and Old Man Joe was asked to design a new system.

The first change he made was adjusting the rating for new wranglers. He proposed the following:

1. The ‘new wrangler rating’ starts at $1500$.

2. Whenever a new wrangler completes their first match, their post-match rating becomes the ‘new wrangler rating.’

3. Matches between two new wranglers do not affect the ‘new wrangler rating.’

4. All wranglers start as new wranglers and are assigned the ‘new wrangler rating’ immediately before their first wrangle. After their first wrangle, they become old wranglers.

Now, if new wranglers tend to do much better or worse than $1500$, the starting rating will be more accurate.

Joe also decided to account for experience when updating rankings. Suppose a wrangler who competed in $a$ matches faces a competitor who competed in $b$ matches. If the wrangler would have gained (or lost) $z \geq 0$ rating under the old system, they will instead gain (or lose) $\lfloor \frac{b + 1}{a + b + 2} \cdot z \rfloor $.

Finally, too many players were complaining about losing too much rating in one match. Joe also noticed wranglers tended to get inflated egos when they gained too much rating, leading to many fights. So, he capped the maximum rating change from a single match at 1000. This rule only takes effect after the previous rule has been applied.

Everyone likes this new system, but Old Man Joe is pretty slow with his calculator. Can you help him out?

Input

The first line will contain two integers $2 \leq n \leq 10^5$ and $1 \leq m \leq 10^5$ indicating the number of wranglers in town and the number of matches you must process, respectively.

The next $m$ lines will contain two integers $1 \leq u, v \leq n$ ($u \neq v$), indicating that player $u$ beats player $v$ in a wrangling match.

Output

Output $m$ lines. On the $i$-th line, output two integers, indicating the ratings of the two players who competed in the $i$-th wrangling match, in the order they appear in the input.

(Partial) Explanation of Sample 1

After the first match, player 1’s rating would have been updated to

But because of the new rules, instead of gaining $1500$, they gain $\frac{1}{2} \cdot 1500 = 750$, for a new rating of $2250$.

Similarly, player 2’s rating would have been updated to

But because of the new rules, instead of losing $500$, they lose only $\frac{1}{2} \cdot 500 = 250$, for a new rating of $1250$.

Because both player 1 and player 2 are new wranglers, the new wrangler rating is not adjusted.

After the second match, player 1’s rating would have been updated to

Now because player 1 has competed in one previous match, while player 3 is new, player 1 gains only $\frac{1}{3} \cdot 1125 = 375$ rating, for a new rating of $2625$.

The rating update for player $3$ is calculated similarly. And now, since only player 3 was a new wrangler, the new wrangler rating is updated to $1250$. This means, that in the next match, player $4$ starts at $1250$ rating. And since they can gain only $1000$ rating from a single match, they move to a rating of just $2250$.

4 5
1 2
1 3
4 1
1 2
2 4

2250 1250
2625 1250
2250 2349
2582 1094
2094 1685

2 4
1 2
2 1
1 2
2 1

2250 1250
2250 1792
2792 1837
2837 2247