Disklərin çeşidlənməsi#10883
Verilmişdir n + 1 çubuq və disk. Əvvəlcə ilk çubuğun hər birində dəqiq disk var. Hər bir disk rəngdən birinə malikdir, rənglər -dən -ə qədər nömrələrlə təyin olunur. Hər bir rəngdən dəqiq disk var. n + 1 nömrəli çubuq isə boşdur.
Hər addımda biz və b~(a \ne b) çubuqlarını seçə bilərik ki, ən azı diskə malik olsun və ən çox diskə malik olsun, və çubuğunun üstündəki diski çubuğunun üstünə köçürək. Diqqət yetirin ki, heç bir çubuq eyni anda -dən çox disk tuta bilməz.
Sizin məqsədiniz diskləri sıralamaqdır. Xüsusilə, siz bir sıra əməliyyatlar (potensial olaraq ) yerinə yetirməlisiniz ki, sonda ilk çubuğun hər biri dəqiq bir rəngdən diskə malik olsun və (n + 1)-ci çubuq boş qalsın.
Diskləri maksimum əməliyyatla sıralamaq üçün həll tapın. Bu şərtlə həmişə həllin mövcud olduğunu sübut etmək olar. Bir neçə həll mövcud olduqda, istənilən birini çıxarın.
Birinci sətir təbii ədəd n~(1 \le n \le 1000) ehtiva edir. Növbəti sətirin hər biri təbii ədəd c_{i,j}~(1 \le i \le 3, 1 \le j \le n, 1 \le c_{i,j} \le n) ehtiva edir — çubuqlarda əvvəlcə yerləşdirilmiş hər bir diskin rəngi. İlk sətir disklərin üst sırasını göstərir, ikinci sətir orta sıranı, üçüncü sətir isə alt sıranı göstərir.
Birinci sətir qeyri-mənfi tam ədəd k~(0 \le k \le 6n) ehtiva etməlidir — əməliyyatların sayı. Növbəti sətirin hər biri iki fərqli ədəd a_i, b_i~(1 \le a_i, b_i \le n + 1, bütün 1 \le i \le k) ehtiva etməlidir, bu -ci əməliyyatı təmsil edir (şərtdə yazıldığı kimi).
Nümunə 1
Nümunə 2