Səhv#10892

Səhv

1 saniyə

128 meqabayt

Asan

"'markdown Mayk, tələbə və alqoritm həvəskarı olaraq, mürəkkəb sistemlərlə işləməyə alışıb. Lakin bu, hazırda təcrübə keçdiyi şirkətdə böyük bir problemə çevrilib.

Mayka verilən layihə, şirkətin paralel hesablama üçün intellektual klasteri ilə işləməyi əhatə edir. Bu, sadəcə bir adlandırmadır; əslində sistem, ümumilikdə $n$ tapşırığı emal edən sadə bir tapşırıq planlayıcısıdır. Bəzi tapşırıqlar, onları yerinə yetirməzdən əvvəl digər tapşırıqların tamamlanmasına bağlı ola bilər. Belə asılılıqların ümumi sayı $m$ -dir.

Tapşırıqlar arasında (birbaşa və ya dolayı) dövri asılılıqların olmadığı təmin edilir.

İcra başladıqda, sistemlər bütün asılılıqların təmin olunması üçün bu tapşırıqların icra sırasını intellektual şəkildə seçirlər (sıra müxtəlif icralar arasında dəyişə bilər). Etibarlı bir sıra seçildikdən sonra, bu sırada hər bir $n$ tapşırığı icra etməyə başlayır. Sistem bir tapşırığı icra etməyə başladıqda, tapşırığın $i d$ -sini jurnal faylına çıxarır.

Təəssüf ki, bu gün Maykın şirkətdəki ilk təcrübə günü idi və o, xüsusi diqqət göstərmədi. Nəticədə, o, təsadüfən sistemi paralel olaraq $k$ dəfə işə saldı. Sistem tapşırıqları nizamsız şəkildə işə salmağa və jurnal faylına çap etməyə başladı. İndi jurnal faylı, icra olunan bütün tapşırıqların $n \cdot k$ n \cdot k identifikatorunu ehtiva edir. Eyni icradan olan tapşırıq identifikatorları, icra edildikləri sırada çap edilmişdir, lakin müxtəlif icralardan olan çıxışlar təsadüfi şəkildə qarışa bilər.

Sizin vəzifəniz - jurnal faylındakı məlumatlara əsasən, hər bir $k$ icrada hansı tapşırıqların icra edildiyini müəyyən etməkdir.

Giriş

Birinci sətir, sistemdəki tapşırıqların sayı, Maykın icra sayısı və asılılıqların sayı olan üç tam ədəd $n, k, m (1 \leq n, k \leq 500000, 0 \leq m \leq 250000, n \cdot k \leq 500000)$ n, k, m~(1 \le n, k \le 500000, 0 \le m \le 250000, n \cdot k \le 500000) ehtiva edir.

Növbəti $m$ sətirin hər biri, $a_{i}, b_{i} (1 \leq a_{i}, b_{i} \leq n, a_{i} \neq = b_{i}$ a_i, b_i~(1 \le a_i, b_i \le n, a_i \ne b_i, bütün $1 \leq i \leq m)$ 1 \le i \le m) cütlüyünü ehtiva edir və bu asılılığı təsvir edir: “ $a_{i}$ a_i işi $b_{i}$ b_i işindən əvvəl yerinə yetirilməlidir”.

Son sətir, jurnal faylına çıxarılan tapşırıq identifikasiya nömrələrini ehtiva edən $n \cdot k$ n \cdot k tam ədəd $c_{i} (1 \leq c_{i} \leq n$ c_i~(1 \le c_i \le n, bütün $1 \leq i \leq n \cdot k)$ 1 \le i \le n \cdot k) ehtiva edir.

Çıxış

Bir sətir çıxarın, $n \cdot k$ n \cdot k tam ədəd $r_{i} (1 \leq r_{i} \leq k$ r_i~(1 \le r_i \le k, bütün $1 \leq i \leq n \cdot k)$ 1 \le i \le n \cdot k) olan, jurnal faylında hər bir tapşırığa uyğun gələn icra $i d$ -sini göstərir. Xüsusilə, $r_{i}$ r_i jurnal faylında $i$ -ci tapşırığa uyğun gələn icra $i d$ -si olmalıdır.

Əgər bir neçə həll yolu varsa, istənilən birini çıxarın. Giriş məlumatlarının ziddiyyətli olmadığı və həll yolunun həmişə mövcud olduğu təmin edilir. "'

Nümunələr

Nümunə 1