Dövlət yolları
Orta əsrlərdə Baytlandiya ərazisində bir neçə dövlət mövcud idi. Bu dövrlərdə dövlətlərin sərhədləri daim dəyişirdi və nəticədə böyük şəhərlər bir dövlətdən digərinə keçirdi. İndi tarixçilər müxtəlif zamanlarda dövlətlərin konfiqurasiyasını müəyyən etməyə çalışırlar.
Onların istifadə etdiyi üsullardan biri, xronikalarda şəhərləri birləşdirən yolların statusunun qeyd olunmasına əsaslanır. Əgər hər hansı bir tarixi anda yol dövlət statusuna malikdirsə, tarixçilər hesab edirlər ki, bu yolla birləşdirilən şəhərlər həmin anda mütləq eyni dövlətə məxsusdur. Lakin hərəkət üçün xronikalarda qeyd olunmayan yerli əhəmiyyətli yollar da istifadə olunurdu. Buna görə də, hər hansı iki şəhərin eyni dövlətdə dövlət yolu ilə birləşdirildiyi iddiası ümumiyyətlə doğru deyil, eləcə də eyni dövlətə məxsus olan hər hansı iki şəhər arasında yalnız dövlət yolları ilə hərəkət etmək mümkün olduğu iddiası da doğru deyil.
Bu yanaşmanı yoxlamaq üçün tarixçilərə yolların statusunu xronoloji ardıcıllıqla saxlayan və müəyyən bir anda verilmiş şəhərlərin - və yalnız onların - vahid dövlət təşkil edə biləcəyini müəyyən edən bir sistem lazımdır.
Giriş verilənləri
Girişin ilk sətiri orta əsr Baytlandiyasında şəhərlərin sayı və hadisələrin (xronikalardakı qeydlər və sorğular) sayı olan iki tam ədəd n və q (1 ≤ n ≤ 1000000, 1 ≤ q ≤ 2000000) ehtiva edir. Şəhərlər ardıcıl tam ədədlərlə 1-dən n-ə qədər nömrələnmişdir.
Sonra hadisələr və sorğular xronoloji ardıcıllıqla verilir (sorğu, ondan əvvəl baş vermiş bütün hadisələrin olduğu, lakin ondan sonra heç bir hadisənin baş vermədiyi anı əhatə edir). Hər bir q sətiri hadisə və ya sorğunu ifadə edir və aşağıdakı formatda olur:
"1 u v" (birinci tip hadisə) şəhərlər u və v arasında yolun dövlət statusu aldığını göstərir (1 ≤ u < v ≤ n);
"2 m" (ikinci tip hadisə) xronikaların başlanğıcından m-ci birinci tip hadisə nəticəsində dövlət statusu almış yolun artıq bu statusa malik olmadığını göstərir (m bu hadisədən əvvəl baş vermiş birinci tip hadisələrin sayına qədər dəyərlər ala bilər);
"3 k u_1 u_2 ... u_k" - sorğu: artıq işlənmiş bütün hadisələr tərəfindən təsvir olunan anda, şəhərlərinin siyahısı k şəhərdən ibarət olan {u_1, u_2, ..., u_k} nömrəli şəhərlərdən ibarət olan bir dövlətin mövcud ola biləcəyini göstərir (1 ≤ k ≤ n, 1 ≤ u_1 < u_2 < ... < u_k ≤ n).
Xronikalarda qeyd olunan bütün yollarda hərəkət ikitərəflidir və hər hansı iki müxtəlif şəhər arasında bir yoldan çox yol yoxdur.
Baza ilkin olaraq (ilk sorğudan əvvəl) heç bir yol dövlət statusuna malik deyildi. Eyni yol istənilən qədər dövlət statusundan adi statusa və əksinə dəyişə bilər. Hər bir m ikinci tip hadisələrdə bir dəfədən çox rast gəlinməyəcək. Bütün k dəyərlərinin cəmi 2000000-dən çox deyil.
Çıxış verilənləri
Hər bir sorğuya cavab olaraq, əgər verilmiş şəhərlər siyahısı müvafiq anda hər hansı bir dövlətin tam şəhərlər siyahısı ola biləcəksə, ayrı bir sətirdə "YES" yazın, əks halda "NO" yazın.