Problem
Salah satu Organisasi Rahsia Besar, yang namanya tidak dibenarkan kami dedahkan, ialah rangkaian kubu bawah tanah
N yang disambungkan oleh terowong yang sama panjang, yang melaluinya seseorang boleh pergi dari mana-mana kubu ke mana-mana yang lain ( tidak semestinya secara langsung). Komunikasi dengan dunia luar dilakukan melalui pintu keluar rahsia khas, yang terletak di beberapa bunker.
Organisasi perlu merangka pelan pemindahan kakitangan sekiranya berlaku kecemasan. Untuk melakukan ini, untuk setiap bunker, anda perlu mengetahui berapa lama masa yang diperlukan untuk sampai ke pintu keluar terdekat. Anda, sebagai pakar dalam tugas sedemikian, diarahkan untuk mengira masa yang diperlukan untuk setiap bunker mengikut penerangan yang diberikan tentang premis Pertubuhan Rahsia Besar. Untuk kemudahan anda, kubu bernombor dari
1 hingga
N.
Input:
- dua baris pertama mengandungi dua nombor asli
N,
K (
\(1 <= N <= 100000\) ,
\(1 <= K <= N\)) — bilangan bunker dan bilangan pintu keluar masing-masing;
- dalam baris ketiga, nombor berbeza
K yang dipisahkan ruang daripada
1 hingga
N, menunjukkan nombor kubu tempat pintu keluar berada;
- baris keempat mengandungi nombor
M (
\(1 <= M <= 100000\)) — bilangan terowong;
- dalam
M berikut garisan memasukkan pasangan nombor – bilangan bunker yang disambungkan oleh terowong.
Setiap terowong boleh bergerak dalam kedua-dua arah. Organisasi tidak mempunyai terowong yang mengarah dari bunker ke dirinya sendiri, tetapi boleh terdapat lebih daripada satu terowong antara sepasang bunker.
Output: cetak
N nombor yang dipisahkan ruang — untuk setiap bunker, masa minimum yang diperlukan untuk sampai ke pintu keluar. Andaikan bahawa masa untuk melalui satu terowong ialah
1.
Contoh
| # |
Input |
Output |
| 1 |
3
1
2
3
1 2
3 1
2 3
| 1 0 1 |
| 2 |
10
2
10 8
9
67
75
58
8 1
1 10
10 3
34
49
9 2 |
1 4 1 2 1 3 2 0 3 0 |