codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.