Sətirlərin transformasiyası
İki sətir u və v verilmişdir, hər biri yalnız a və b hərflərindən ibarətdir. Məqsədimiz u sətirini v sətirinə çevirməkdir. Bunun üçün aşağıdakı dəyişmə əməliyyatından istifadə edə bilərik: u sətirində iki kəsişməyən ab və ba fraqmentlərini seçib onların yerlərini dəyişmək. u sətirini bu dəyişmə əməliyyatları ilə v sətirinə çevirmək mümkündürmü?
Giriş məlumatları
Birinci sətir bir ədəd n (2 ≤ n ≤ 10^6) - sətirlərin uzunluğunu göstərir. Sonra hər biri n hərfdən ibarət olan iki sətir gəlir, hərflər yalnız a və ya b ola bilər. Birinci sətir u-nu, ikinci sətir isə v-ni təsvir edir. Sətirlərin fərqli olduğunu qəbul edin.
Çıxış məlumatları
Əgər u sətirini dəyişmə əməliyyatları ilə v sətirinə çevirmək mümkündürsə, birinci sətirdə TAK (polyak dilində bəli) yazın, əks halda NIE (polyak dilində yox) yazın.
Əgər cavab müsbətdirsə və n ≤ 4000-dirsə, proqram dəyişmə əməliyyatlarının nümunə ardıcıllığını göstərməlidir. Birinci sətirdə əməliyyatların sayı m (1 ≤ m ≤ 10^6) göstərilməlidir. Sonrakı m sətirin hər biri iki tam ədəd a[i], b[i] (1 ≤ a[i], b[i] ≤ n - 1) ehtiva edir - dəyişdirilən fraqmentlərin başlanğıc mövqelərini göstərir: a[i] ab fraqmentinin başlanğıcını, b[i] isə ba fraqmentinin başlanğıcını göstərir.
Əgər bir neçə həll varsa, onlardan hər hansı birini göstərin. Xüsusilə, əməliyyatların sayını minimallaşdırmağa ehtiyac yoxdur, yəni m ədədini.