| Codeforces Round 1137 (Div. 2) |
|---|
| Contest is running |
| 00:37:53 |
| Score | |
|---|---|
| Problem A | 336 |
| Problem B | 504 |
| Problem C | 840 |
| Problem D | 1344 |
| Problem E | 1344 |
| Problem F | 1680 |
| Successful hack | 100 |
| Unsuccessful hack | -50 |
| Unsuccessful submission | -50 |
| Resubmission | -50 |
In the open arm wrestling tournament of the village of Silach, $$$n$$$ athletes take part. All athletes were first ordered by strength and numbered from $$$1$$$ (the strongest) to $$$n$$$ (the weakest). If the numbers of two athletes differ by $$$d$$$ or more, then in a match between them the stronger one (with the smaller number) always wins. If the numbers differ by less than $$$d$$$, then their strengths are approximately equal, and the match may end with either athlete winning.
The tournament consists of $$$n-1$$$ matches. The loser of a match is immediately eliminated, and the winner gets a place in one of the subsequent matches (or is declared the absolute winner if the match is the final one and all other athletes have already been eliminated). The organizers numbered all matches from $$$n+1$$$ to $$$2n-1$$$ inclusive, and for each match specified the pair of numbers of its participants: a number from $$$1$$$ to $$$n$$$ denotes the athlete with that number, and a number from $$$n+1$$$ to $$$2n-2$$$ denotes the winner of the match with that number. The matches take place sequentially, so the numbers of the participants of match $$$k$$$ are always less than $$$k$$$, and the final match has number $$$2n-1$$$.
Given the tournament scheme, determine for each athlete the maximum number of matches in which they can take part (for at least one possible way the tournament may unfold).
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains a pair of positive integers $$$n$$$ and $$$d$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq d \leq n$$$) — the number of athletes in the tournament and the minimum difference between numbers for which the result of a match between athletes is predetermined.
Then follow $$$n-1$$$ lines — the description of the matches with numbers from $$$n+1$$$ to $$$2n-1$$$ inclusive. Each line contains a pair of positive integers $$$p_1$$$ and $$$p_2$$$ ($$$1 \leq p_1, p_2 \leq 2n-2$$$). The number $$$p_i$$$ means that the corresponding match involves either the athlete with number $$$p_i$$$, if $$$1 \leq p_i \leq n$$$, or the winner of the match with number $$$p_i$$$, if $$$n+1 \leq p_i \leq 2n-2$$$. It is guaranteed that each number from $$$1$$$ to $$$2n-2$$$ inclusive appears exactly once in the descriptions of the matches, and that in the description of match $$$k$$$ the participants have numbers less than $$$k$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output $$$n$$$ integers, each from $$$1$$$ to $$$n-1$$$: the maximum possible number of matches in which the athlete with the corresponding number can take part.
25 12 53 46 78 15 22 53 46 78 1
1 3 2 1 11 3 3 2 1
The tournaments described in the input follow the same scheme shown in the figure.
In the first test case, the stronger participant always wins, since $$$d=1$$$.
In match $$$6$$$, athletes $$$2$$$ and $$$5$$$ meet, and $$$2$$$ wins. In match $$$7$$$, athletes $$$3$$$ and $$$4$$$ meet, and $$$3$$$ wins. In match $$$8$$$, the winners of matches $$$6$$$ and $$$7$$$ meet, that is, athletes $$$2$$$ and $$$3$$$, and $$$2$$$ wins. In the last match, $$$9$$$, the winner of match $$$8$$$ (that is, athlete $$$2$$$) and athlete $$$1$$$ meet. Athlete $$$1$$$ wins the match and the tournament.
Therefore, athlete $$$1$$$ will take part only in match $$$9$$$, athlete $$$2$$$ — in matches $$$6$$$, $$$8$$$, and $$$9$$$, athlete $$$3$$$ — in matches $$$7$$$ and $$$8$$$, athlete $$$4$$$ — only in match $$$7$$$, and athlete $$$5$$$ — only in match $$$6$$$.
In the second test case, matches between athletes whose numbers differ by $$$1$$$ may end with either participant winning.
In match $$$6$$$, athletes $$$2$$$ and $$$5$$$ meet, and $$$2$$$ wins (since $$$5-2 \geq d$$$). In match $$$7$$$, athletes $$$3$$$ and $$$4$$$ meet, and either of them may win ($$$4-3 \lt d$$$). In match $$$8$$$, the winner of match $$$6$$$ (athlete $$$2$$$) meets the winner of match $$$7$$$ (athlete $$$3$$$ or $$$4$$$). In the match between athletes $$$2$$$ and $$$3$$$, either may win, while in the match between $$$2$$$ and $$$4$$$, $$$2$$$ always wins. In the last match, $$$9$$$, the winner of match $$$8$$$ (either $$$2$$$ or $$$3$$$) meets athlete $$$1$$$. In the match between $$$2$$$ and $$$1$$$, either may win, while in the match between $$$3$$$ and $$$1$$$, $$$1$$$ always wins.
Athlete $$$1$$$ will in any case take part only in match $$$9$$$. Athlete $$$2$$$ will definitely take part in matches $$$6$$$ and $$$8$$$, and may take part (if they do not lose to athlete $$$3$$$ in match $$$8$$$) in match $$$9$$$. Athlete $$$3$$$ will definitely take part in match $$$7$$$ and may take part (if they defeat athletes $$$4$$$ and $$$2$$$ in matches $$$7$$$ and $$$8$$$) in matches $$$8$$$ and $$$9$$$. Athlete $$$4$$$ will definitely take part in match $$$7$$$, may take part in match $$$8$$$, but will definitely go no further. Athlete $$$5$$$ is eliminated in the very first match in any case.
| Name |
|---|


