codeforces-scrape

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

1346E.md (2414B)


      1 Source: https://codeforces.com/problemset/problem/1346/E
      2 
      3 E. Magic Tricks
      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 Masha is going to participate in a talent show conducted by the university she studies at. She wants to impress the audience with lots of different magic tricks!
     22 
     23 For one of her tricks, she uses $n$ sponge balls, one of which is a special one. First, she arranges the balls in a row in such a way that the special ball is put on position $k$ (positions are numbered from $1$ to $n$ from left to right). After that, she performs $m$ swaps: during the $i$-th swap, she chooses the ball on position $x_i$ and the ball on position $y_i$, and swaps them.
     24 
     25 Since Masha is a magician, she fakes some of her actions to trick the audience — when she starts performing a swap, she may fake it, so it is not performed (but it looks like it is performed for the audience). There are no constraints on which swaps Masha should fake or should actually perform — for example, she may fake all of the swaps, or even not fake anything at all.
     26 
     27 For the trick to work perfectly, the special ball should end up on a specific position — Masha has not decided yet, which position is perfect. Since faking swaps is difficult, for each position she wants to know the minimum number of swaps she has to fake so that the special ball ends up there.
     28 
     29 Unfortunately, Masha is a magician, neither a mathematician nor a programmer. So she needs your help in calculating what she wants!
     30 
     31 Input
     32 
     33 The first line contains three integers $n$, $m$ and $k$ ($2 \le n \le 2 \cdot 10^5$; $1 \le m \le 2 \cdot 10^5$; $1 \le k \le n$) — the number of balls, the number of swaps and the initial position of the special ball, respectively.
     34 
     35 Then $m$ lines follow, the $i$-th line contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$; $x_i \ne y_i$) denoting the $i$-th swap.
     36 
     37 Output
     38 
     39 Print $n$ integers. The $i$-th integer should be the minimum number of swaps Masha has to fake so the special ball ends up on position $i$ (or $-1$, if Masha cannot put the special ball there).
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 4 5 1
     47 3 4
     48 2 1
     49 4 1
     50 3 1
     51 3 1
     52 ```
     53 
     54 Output
     55 
     56 ```
     57 2 0 3 1
     58 ```
     59 
     60 Input
     61 
     62 ```
     63 5 7 4
     64 3 2
     65 3 2
     66 4 2
     67 3 4
     68 4 1
     69 3 2
     70 5 2
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 2 2 0 3 1
     77 ```
     78 
     79 Input
     80 
     81 ```
     82 7 15 5
     83 5 3
     84 4 2
     85 6 1
     86 2 4
     87 1 6
     88 3 7
     89 5 6
     90 4 2
     91 6 4
     92 2 6
     93 6 3
     94 6 3
     95 7 6
     96 2 6
     97 7 2
     98 ```
     99 
    100 Output
    101 
    102 ```
    103 -1 1 1 1 2 1 0
    104 ```