Qraf#7618
a_1, a_2, \ldots, a_n ardıcıllığı çpermutasiya adlanır, əgər o, -dən -ə qədər hər bir tam ədədi düz bir dəfə ehtiva edirsə.
a_1, a_2, \ldots, a_n təpələrinin permutasiyası istiqamətləndirilmiş qrafın topoloji sıralaması adlanır, əgər -dan -yə hər bir istiqamətləndirilmiş kənar üçün təpəsi bu permutasiyada təpəsindən əvvəl yerləşirsə.
a_1, a_2, \ldots, a_n permutasiyası b_1, b_2, \ldots, b_n permutasiyasından leksikoqrafik baxımdan kiçikdir, əgər elə indeksi mövcuddursa ki, bütün 1 \le i \lt m üçün a_i = b_i olsun və a_m \lt b_m olsun.
İstiqamətləndirilmiş asiklik qraf verilmişdir. Ona ən çox ədəd istiqamətləndirilmiş kənar əlavə edin ki, alınan qraf asiklik olaraq qalsın və onun leksikoqrafik baxımdan ən kiçik topoloji sıralaması mümkün qədər böyük olsun.
Birinci sətirdə üç tam ədəd , və k~(1 \le n \le 10^5, 0 \le m, k \le 10^5) verilir — ilkin qrafdakı təpələrin və istiqamətləndirilmiş kənarların sayı, həmçinin əlavə etməyə icazə verilən istiqamətləndirilmiş kənarların maksimum sayı.
Sonrakı sətirin hər birində iki tam ədəd u_i və v_i~(1 \le u_i, v_i \le n) verilir, bunlar u_i-dən v_i-yə istiqamətləndirilmiş kənarı təsvir edir.
Qrafda tsikl olmadığı təmin olunur.
Birinci sətirdə tam ədəd — dəyişdirilmiş qrafın leksikoqrafik baxımdan ən kiçik topoloji sıralamasını çap edin. İkinci sətirdə əlavə edilən istiqamətləndirilmiş kənarların sayını bildirən bir tam ədəd (0 \le x \le k) çap edin. Sonrakı sətirin hər birində əlavə edilən bir kənarın təsvirini giriş məlumatlarındakı ilə eyni formatda çap edin.
Nümunə 1
Nümunə 2