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 ```