codeforces-scrape

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

34D.md (1720B)


      1 Source: https://codeforces.com/problemset/problem/34/D
      2 
      3 D. Road Map
      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 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 There are *n* cities in Berland. Each city has its index — an integer number from 1 to *n*. The capital has index *r*1. All the roads in Berland are two-way. The road system is such that there is exactly one path from the capital to each city, i.e. the road map looks like a tree. In Berland's chronicles the road map is kept in the following way: for each city *i*, different from the capital, there is kept number *p**i* — index of the last city on the way from the capital to *i*.
     22 
     23 Once the king of Berland Berl XXXIV decided to move the capital from city *r*1 to city *r*2. Naturally, after this the old representation of the road map in Berland's chronicles became incorrect. Please, help the king find out a new representation of the road map in the way described above.
     24 
     25 Input
     26 
     27 The first line contains three space-separated integers *n*, *r*1, *r*2 (2 ≤ *n* ≤ 5·104, 1 ≤ *r*1 ≠ *r*2 ≤ *n*) — amount of cities in Berland, index of the old capital and index of the new one, correspondingly.
     28 
     29 The following line contains *n* - 1 space-separated integers — the old representation of the road map. For each city, apart from *r*1, there is given integer *p**i* — index of the last city on the way from the capital to city *i*. All the cities are described in order of increasing indexes.
     30 
     31 Output
     32 
     33 Output *n* - 1 numbers — new representation of the road map in the same format.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 3 2 3  
     41 2 2
     42 ```
     43 
     44 Output
     45 
     46 ```
     47 2 3
     48 ```
     49 
     50 Input
     51 
     52 ```
     53 6 2 4  
     54 6 1 2 4 2
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 6 4 1 4 2
     61 ```