Problem
Adını açıklamamıza izin verilmeyen Çok Gizli Örgütlerden biri, herhangi bir sığınaktan diğerine geçilebilen, eşit uzunlukta tünellerle birbirine bağlanan
N yer altı sığınaklarından oluşan bir ağdır ( doğrudan değil). Dış dünya ile iletişim, bazı sığınaklarda bulunan özel gizli çıkışlar aracılığıyla gerçekleştirilir.
Kuruluşun acil bir durumda bir personel tahliye planı hazırlaması gerekiyordu. Bunu yapmak için, sığınakların her biri için en yakın çıkışa ulaşmanın ne kadar süreceğini bulmanız gerekir. Bu tür görevlerde uzman olarak size, Çok Gizli Örgütün tesislerinin belirli bir açıklamasına göre sığınakların her biri için gereken süreyi hesaplamanız talimatı verildi. Size kolaylık sağlamak için sığınaklar
1 ile
N arasında numaralandırılmıştır.
Giriş:
- ilk iki satır iki doğal sayı içerir
N,
K (
\(1 <= N <= 100000\) ,
\(1 <= K <= N\)) — sırasıyla sığınak sayısı ve çıkış sayısı;
- üçüncü satırda, çıkışların bulunduğu bunkerlerin numaralarını gösteren,
1'den
N'e kadar boşlukla ayrılmış
K farklı sayılar;
- dördüncü satır,
M sayısını içerir (
\(1 <= M <= 100000\)) — tünel sayısı;
- aşağıdaki
M satırlar sayı çiftlerini girer – bir tünelle birbirine bağlanan sığınak sayısı.
Tünellerin her biri her iki yönde de hareket edebilir. Bir kuruluşun bir sığınaktan kendisine giden tünelleri yoktur, ancak bir çift sığınak arasında birden fazla tünel olabilir.
Çıktı: boşlukla ayrılmış
N sayıları yazdır — sığınakların her biri için çıkışa ulaşmak için gereken minimum süre. Bir tünelden geçme süresinin
1 olduğunu varsayalım.
Örnekler
| # |
Girdi |
Çıktı |
| 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 |