codeforces-scrape

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

1583B.md (3073B)


      1 Source: https://codeforces.com/problemset/problem/1583/B
      2 
      3 B. Omkar and Heavenly 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 Lord Omkar would like to have a tree with $n$ nodes ($3 \le n \le 10^5$) and has asked his disciples to construct the tree. However, Lord Omkar has created $m$ ($\mathbf{1 \le m \lt n}$) restrictions to ensure that the tree will be as heavenly as possible.
     22 
     23 A tree with $n$ nodes is an connected undirected graph with $n$ nodes and $n-1$ edges. Note that for any two nodes, there is exactly one simple path between them, where a simple path is a path between two nodes that does not contain any node more than once.
     24 
     25 Here is an example of a tree:
     26 
     27  ![](https://espresso.codeforces.com/0c2c664b43f98f7f388ef52d12fba06d30758778.png) 
     28 
     29 A restriction consists of $3$ pairwise distinct integers, $a$, $b$, and $c$ ($1 \le a,b,c \le n$). It signifies that node $b$ cannot lie on the simple path between node $a$ and node $c$.
     30 
     31 Can you help Lord Omkar and become his most trusted disciple? You will need to find heavenly trees for multiple sets of restrictions. It can be shown that a heavenly tree will always exist for any set of restrictions under the given constraints.
     32 
     33 Input
     34 
     35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). Description of the test cases follows.
     36 
     37 The first line of each test case contains two integers, $n$ and $m$ ($3 \leq n \leq 10^5$, $\mathbf{1 \leq m \lt n}$), representing the size of the tree and the number of restrictions.
     38 
     39 The $i$-th of the next $m$ lines contains three integers $a_i$, $b_i$, $c_i$ ($1 \le a_i, b_i, c_i \le n$, $a$, $b$, $c$ are distinct), signifying that node $b_i$ cannot lie on the simple path between nodes $a_i$ and $c_i$.
     40 
     41 It is guaranteed that the sum of $n$ across all test cases will not exceed $10^5$.
     42 
     43 Output
     44 
     45 For each test case, output $n-1$ lines representing the $n-1$ edges in the tree. On each line, output two integers $u$ and $v$ ($1 \le u, v \le n$, $u \neq v$) signifying that there is an edge between nodes $u$ and $v$. Given edges have to form a tree that satisfies Omkar's restrictions.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 2
     53 7 4
     54 1 2 3
     55 3 4 5
     56 5 6 7
     57 6 5 4
     58 5 3
     59 1 2 3
     60 2 3 4
     61 3 4 5
     62 ```
     63 
     64 Output
     65 
     66 ```
     67 1 2
     68 1 3
     69 3 5
     70 3 4
     71 2 7
     72 7 6
     73 5 1
     74 1 3
     75 3 2
     76 2 4
     77 ```
     78 
     79 Note
     80 
     81 The output of the first sample case corresponds to the following tree:
     82 
     83  ![](https://espresso.codeforces.com/5026d10ec0a05362ee58628c4fadde31d96fbbaf.png)  For the first restriction, the simple path between $1$ and $3$ is $1, 3$, which doesn't contain $2$. The simple path between $3$ and $5$ is $3, 5$, which doesn't contain $4$. The simple path between $5$ and $7$ is $5, 3, 1, 2, 7$, which doesn't contain $6$. The simple path between $6$ and $4$ is $6, 7, 2, 1, 3, 4$, which doesn't contain $5$. Thus, this tree meets all of the restrictions.
     84 
     85 The output of the second sample case corresponds to the following tree:
     86 
     87  ![](https://espresso.codeforces.com/91bb7614d530ff4a97985fdbc5086f2e60568451.png)