405154: GYM101807 F Final Fixture

Like in many countries, there is a football league in Hackerland. The top league (called Tourist League) has $$$N$$$ teams, where $$$N$$$ is an even number. The teams are conveniently numbered from $$$1$$$ to $$$N$$$.

For those unfamiliar with football leagues, here is the basic information that you need to know for this task. Three statistics determine a team's standing: points, goals scored, and goals conceded. For every match a team plays, they score goals and concede goals.

• If they score more goals than they concede, then they win and earn three points.
• If they score the same number of goals as they concede, then they draw and earn one point.
• If they score fewer goals then they concede, then they lose and earn no points.

For two teams $$$A$$$ and $$$B$$$, let $$$P_A$$$ be the total points team $$$A$$$ has, $$$S_A$$$ be the total number of goals scored by team $$$A$$$, and $$$C_A$$$ be the total number of goals conceded by team $$$A$$$. Likewise for $$$P_B$$$, $$$S_B$$$, and $$$C_B$$$. Team $$$A$$$ is ranked higher than team $$$B$$$ if and only if one of the following is true:

• $$$P_A > P_B$$$ (more points)
• $$$P_A = P_B$$$ and $$$S_A - C_A > S_B - C_B$$$ (same points, superior goal difference)
• $$$P_A = P_B$$$, $$$S_A - C_A = S_B - C_B$$$, and $$$S_A > S_B$$$ (same points, same goal difference, more goals scored)

There is no further tiebreaker. Therefore, it is possible for two teams to have the same rank. A team's rank is given by $$$1 + $$$ (number of teams ranked higher than it).

The final fixture in the league is always the most exciting one, especially at the top and at the bottom of the table, where teams fight fiercely for their respective targets. More important, all matches will start at the same time, and a team's fate may depend on scorelines of matches played hundreds of miles away!

For all $$$N$$$ teams in the Tourist League, you know their points, goals scored, and goals conceded, right before the final fixture. You also know the pairing for the final fixture.

Here is your task: based on your data, determine each team's best and worst final rank. For the sake of this task, there is no upper limit on the number of goals a team can score within a match; even a $$$10^9-0$$$ scoreline is considered possible.

The given data (points, goals scored, goals conceded) may be inconsistent, since they come from a questionable source. Nevertheless, you are to make predictions based on the data.

The pairing is guaranteed to be consistent, i.e. each team will play against exactly one other team.

The first line of input consists of an even integer $$$N$$$ ($$$2 \le N \le 5000$$$).

$$$\frac{N}{2}$$$ lines follow. The $$$i$$$-th line consists of two space-separated integers $$$A_i$$$ and $$$B_i$$$, meaning that team $$$A_i$$$ will play against team $$$B_i$$$ in the final fixture. Each of $$$1, 2, \dots, N$$$ appears exactly once in $$$\{A_1, \dots, A_{\frac{N}{2}}, B_1, \dots, B_{\frac{N}{2}}\}$$$.

$$$N$$$ lines follow. The $$$i$$$-th line consists of three space-separated integers $$$P_i$$$, $$$S_i$$$, and $$$C_i$$$, representing the points of, goals scored by, and goals conceded by team $$$i$$$ ($$$0 \le P_i \le 30000$$$; $$$0 \le S_i, C_i \le 10^5$$$).

Output $$$N$$$ lines. On the $$$i$$$-th line, output the best final rank of team $$$i$$$, followed by the worst final rank of team $$$i$$$. Separate the two numbers by one space.

2
1 2
3 100000 0
0 0 100000

1 2
1 2

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

1 3
1 4
1 3
3 4

2
1 2
1 1 0
5 2 7

2 2
1 1

10
2 3
9 10
1 6
7 8
4 5
47 65 12
34 34 20
34 36 24
28 32 22
23 25 25
23 21 28
19 23 34
15 21 32
14 17 39
5 11 49

1 1
2 3
2 3
4 4
5 6
5 6
7 7
8 9
8 9
10 10

Sample input 1 is an example of extreme scorelines. Team $$$2$$$ can still take first place, for example by winning the final game $$$262144 - 131072$$$.

Sample input 3 is an example of inconsistent data.

Sample input 4 is from this season's Hong Kong Premier League. (It turns out that the ranking is unchanged after the final fixture.)