Bounty for Heads#10259
Vitaliy enjoys playing gambling games, and his favorite involves players, each numbered from to . Every player starts with two balances: their winnings, initially set to , and a bounty on their head, initially set to .
The game consists of exactly n-1 consecutive events, where two different players still in the game are selected. The first player knocks out the second. When this happens, the first player's winnings increase by the bounty of the second player, and the first player's bounty increases by half of the second player's bounty. The second player is then eliminated from the game and can no longer participate in any knockouts.
Your task is to determine a sequence of events that either minimizes or maximizes the total winnings of all players.
The first line contains two integers and (2 \le n \le 10^5, 0 \le t \le 1) — the number of players and a flag indicating whether to minimize or maximize the winnings. A value of for means you should minimize the winnings, while means you should maximize them.
Output n-1 lines. Each line should contain two integers a_i and b_i (1 \leq a_i, b_i \leq n), indicating that player a_i knocked out player b_i at step .
Example 1
Example 2
Consider the first example. The players' balances evolve as follows:
Initial balances: (0, 1), (0, 1), (0, 1).
After the first step: (0, 1), (1, 1.5), (0, 1).
After the second step: (0, 1), (2, 2), (0, 1).
The total winnings are 2 + 0 + 0 = 2.
Now, consider the second example. The players' balances evolve as follows:
Initial balances: (0, 1), (0, 1), (0, 1).
After the first step: (0, 1), (0, 1), (1, 1.5).
After the second step: (0, 1), (1.5, 1.75), (1, 1.5).
The total winnings are 1 + 0 + 1.5 = 2.5.
In of the tests, t=0.
In the other of the tests, t=1.