Graf#7618
Dizi a_1, a_2, \ldots, a_n, eğer 'den 'e kadar olan her tam sayıyı tam olarak bir kez içeriyorsa permütasyon olarak adlandırılır.
Köşelerin a_1, a_2, \ldots, a_n permütasyonu, yönlü bir grafın topolojik sıralaması olarak adlandırılır, eğer 'dan 'ye giden her yönlü kenar için köşesi bu permütasyonda köşesinden daha önce yer alıyorsa.
a_1, a_2, \ldots, a_n permütasyonu, b_1, b_2, \ldots, b_n permütasyonundan sözlüksel olarak küçüktür, eğer öyle bir indeksi varsa ki, tüm 1 \le i < m için a_i = b_i ve a_m < b_m olsun.
Yönlü asiklik bir graf verilmiştir. Bu grafa en fazla tane yönlü kenar ekleyin, öyle ki elde edilen graf asiklik kalsın ve onun sözlüksel olarak en küçük topolojik sıralaması mümkün olduğunca büyük olsun.
İlk satır, orijinal graftaki köşe ve yönlü kenar sayısını, ayrıca eklenmesine izin verilen maksimum yönlü kenar sayısını belirten üç tam sayı , ve k~(1 \le n \le 10^5, 0 \le m, k \le 10^5) içerir.
Sonraki satırın her biri, u_i'den v_i'ye giden yönlü bir kenarı tanımlayan iki tam sayı u_i ve v_i~(1 \le u_i, v_i \le n) içerir.
Grafın çevrim (döngü) içermediği garanti edilmektedir.
İlk satırda, değiştirilmiş grafın sözlüksel olarak en küçük topolojik sıralamasını temsil eden tam sayı yazdırın. İkinci satırda, eklenen yönlü kenar sayısını belirten tek bir tam sayı (0 \le x \le k) yazdırın. Sonraki satırın her birinde, girişte kullanılan formatla aynı formatta eklenen bir kenarın tanımını yazdırın.
Örnek 1
Örnek 2