Tarazlanmış ağac#2950
Verilmiş kökü olan və ədəd zirvədən ibarət bir ağac var, burada zirvələr -dən -ə nömrələnib və onlar ya qırmızı, ya da qara rəngdədir.
Bir ağac aşağıdakı şərtləri ödədikdə qırmızı-qara ağac (red-black tree) adlanır:
Hər zirvənin ya , ya da uşağı var.
Bütün yarpaqlar qara rəngdədir.
Kökdən istənilən yarpağa qədər bütün yollar eyni sayda qara zirvədən keçir.
Qırmızı zirvənin qırmızı valideyni ola bilməz.
Sizin vəzifəniz verilmiş ağacın qırmızı-qara ağac olub-olmadığını yoxlamaqdır. Əgər belədirsə, ona izomorf olan -- ağacını qurun.
Birinci sətirdə (1 \leq n \leq 10^5) verilir. Növbəti cütlük hər biri -ci zirvənin valideynini və onun rəngini göstərir (rəng — qırmızı və ya — qara hərfi ilə göstərilir). Kökün valideyni -ci nömrəli zirvənin özüdür.
Əgər cavab YES-dirsə, həmçinin izomorf -- ağacını aşağıdakı formatda verin: əvvəlcə kənarların sayı, sonra isə kənarların siyahısı çıxarılmalıdır. Zirvələrin nömrələnməsi orijinal ağacdakı kimi olmalıdır. Əks halda yalnız NO çıxarın.
Nümunə 1