CF2178D Xmas or Hysteria

[Mass Hysteria](https://hearthstone.blizzard.com/en-us/cards/50071-mass-hysteria) (Hearthstone) $ \color{white}{\text{You are sus}} $ Franklin is plotting a Christmas attack where he casts the spell Mass Hysteria on a village of elves. There are $ n $ elves numbered $ 1 $ to $ n $ , where elf $ i $ has a health value of $ h_i $ and an attack value of $ a_i $ . Initially, $ h_i=a_i $ for all $ i $ , and all $ a_i $ are distinct. Elf $ i $ is alive if and only if its health is positive (i.e., $ h_i>0 $ ). When Franklin casts Mass Hysteria, the following process is repeated: - Choose a pair of distinct living elves $ x $ and $ y $ ( $ h_x,h_y>0 $ ) such that elf $ x $ has not attacked before. If no such pair exists, terminate the process. - Then, elf $ x $ attacks elf $ y $ , decreasing $ h_y $ by $ a_x $ . Additionally, due to recoil, $ h_x $ is decreased by $ a_y $ . Note that $ a_x $ and $ a_y $ remain unchanged. The process will repeat until it is impossible to choose a valid pair of elves. It can be shown that Mass Hysteria terminates after at most $ n $ iterations. Given an integer $ m $ , construct a valid sequence of attacks such that exactly $ m $ elves are alive when the process ends; or determine that no such sequence exists.

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 two integers $ n $ and $ m $ ( $ 2\le n\le 2\cdot 10^5, 0\le m\le n $ ) — the number of elves in the village and the number of elves to be left alive. The second line contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1\le a_i\le 10^9 $ ) — the initial attack and health values of the elves. It is guaranteed that all $ a_i $ are distinct. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10 ^ 5 $ .

For each test case, if it is impossible for exactly $ m $ elves to remain alive, print $ -1 $ . Otherwise, output a valid sequence of attacks as follows: - On the first line, output an integer $ k $ ( $ 0\le k\le n $ ) — the number of iterations in Mass Hysteria. - Then $ k $ lines follow, the $ i $ -th line containing two integers $ x_i $ and $ y_i $ ( $ 1\leq x_i,y_i\leq n $ , $ x_i\neq y_i $ ), indicating that elf $ x_i $ attacks elf $ y_i $ in the $ i $ -th iteration. The sequence must satisfy all of the following conditions: - Immediately before the $ i $ -th iteration, both elves $ x_i $ and $ y_i $ are alive and elf $ x_i $ has not attacked in any previous iteration. - After the $ k $ -th iteration, exactly $ m $ elves are alive and there does not exist a pair of distinct living elves $ x $ and $ y $ such that elf $ x $ has not attacked before. If there are multiple answers, you may output any of them. Any valid sequence satisfying the above conditions will be accepted.

In the first test case, one possible sequence of attacks is shown below: \# $ x $ $ y $ Health values after attackElves that have attacked0—— $ [1, 4, 2, 3] $ $ [] $ 1 $ 3 $ $ 1 $ $ [-1, 4, 1, 3] $ $ [3] $ 2 $ 2 $ $ 4 $ $ [-1, 1, 1, -1] $ $ [2, 3] $ After $ 2 $ iterations, only elves $ 2 $ and $ 3 $ are alive. Since both of them have already attacked, no further valid attack is possible, and Mass Hysteria terminates. In the second test case, the only possible choices for $ (x,y) $ in the first iteration are $ (1,2) $ or $ (2,1) $ . In either case, elf $ 1 $ ends up with $ -1 $ health, so it is impossible for both elves to remain alive at the end. Note that Mass Hysteria will last at least one iteration as there exists a valid $ (x,y) $ for the first iteration. In the sixth test case, only elf $ 3 $ is alive after all attacks. Even though elf $ 3 $ has not attacked before, Mass Hysteria terminates since there is no other elf it can attack.