codeforces-scrape

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

1433D.md (2207B)


      1 Source: https://codeforces.com/problemset/problem/1433/D
      2 
      3 D. Districts Connection
      4 
      5 time limit per test
      6 
      7 1 second
      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 There are $n$ districts in the town, the $i$-th district belongs to the $a_i$-th bandit gang. Initially, no districts are connected to each other.
     22 
     23 You are the mayor of the city and want to build $n-1$ two-way roads to connect all districts (two districts can be connected directly or through other connected districts).
     24 
     25 If two districts belonging to the same gang are connected directly with a road, this gang will revolt.
     26 
     27 You don't want this so your task is to build $n-1$ two-way roads in such a way that all districts are reachable from each other (possibly, using intermediate districts) and each pair of directly connected districts belong to different gangs, or determine that it is impossible to build $n-1$ roads to satisfy all the conditions.
     28 
     29 You have to answer $t$ independent test cases.
     30 
     31 Input
     32 
     33 The first line of the input contains one integer $t$ ($1 \le t \le 500$) — the number of test cases. Then $t$ test cases follow.
     34 
     35 The first line of the test case contains one integer $n$ ($2 \le n \le 5000$) — the number of districts. The second line of the test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the gang the $i$-th district belongs to.
     36 
     37 It is guaranteed that the sum of $n$ does not exceed $5000$ ($\sum n \le 5000$).
     38 
     39 Output
     40 
     41 For each test case, print:
     42 
     43 * NO on the only line if it is impossible to connect all districts satisfying the conditions from the problem statement.
     44 * YES on the first line and $n-1$ roads on the next $n-1$ lines. Each road should be presented as a pair of integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n; x_i \ne y_i$), where $x_i$ and $y_i$ are two districts the $i$-th road connects.
     45 
     46 For each road $i$, the condition $a[x_i] \ne a[y_i]$ should be satisfied. Also, all districts should be reachable from each other (possibly, using intermediate districts).
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 4
     54 5
     55 1 2 2 1 3
     56 3
     57 1 1 1
     58 4
     59 1 1000 101 1000
     60 4
     61 1 2 3 4
     62 ```
     63 
     64 Output
     65 
     66 ```
     67 YES
     68 1 3
     69 3 5
     70 5 4
     71 1 2
     72 NO
     73 YES
     74 1 2
     75 2 3
     76 3 4
     77 YES
     78 1 2
     79 1 3
     80 1 4
     81 ```