2120C.md (2289B)
1 Source: https://codeforces.com/problemset/problem/2120/C 2 3 C. Divine Tree 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Harshith attained enlightenment in Competitive Programming by training under a Divine Tree. A divine tree is a rooted tree$^{\text{∗}}$ with $n$ nodes, labelled from $1$ to $n$. The divineness of a node $v$, denoted $d(v)$, is defined as the smallest node label on the unique simple path from the root to node $v$. 22 23 Aryan, being a hungry Competitive Programmer, asked Harshith to pass on the knowledge. Harshith agreed on the condition that Aryan would be given two positive integers $n$ and $m$, and he had to construct a divine tree with $n$ nodes such that the total divineness of the tree is $m$, i.e., $\displaystyle\sum\limits_{i=1}^n d(i)=m$. If no such tree exists, Aryan must report that it is impossible. 24 25 Desperate for knowledge, Aryan turned to you for help in completing this task. As a good friend of his, help him solve the task. 26 27 $^{\text{∗}}$A tree is a connected graph without cycles. A rooted tree is a tree where one vertex is special and called the root. 28 29 Input 30 31 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. 32 33 The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 10^6$, $1 \le m \le 10^{12}$). 34 35 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$. 36 37 Output 38 39 For each test case, output a single integer $k$ in one line — the root of the tree. 40 41 Then $n-1$ lines follow, each containing a description of an edge of the tree — a pair of positive integers $u_i,v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$), denoting the $i$-th edge connects vertices $u_i$ and $v_i$. 42 43 The edges and vertices of the edges can be printed in any order. If there are multiple solutions, print any of them. 44 45 If there is no solution, print "-1" instead. 46 47 Example 48 49 Input 50 51 ``` 52 2 53 54 1 2 55 56 4 6 57 ``` 58 59 Output 60 61 ``` 62 -1 63 3 64 3 1 65 1 2 66 2 4 67 ``` 68 69 Note 70 71 In the first test case, there is a single node with a value of $1$, so getting a sum of $2$ is impossible. 72 73 In the second test case, getting a sum of $6$ is possible with the given tree rooted at $3$.