Deyzi Labirintləri

Deyzi işdən sonra stress atmaq üçün labirintlərdə gəzməyi sevir. Onun sevdiyi labirintlər bir giriş və bir çıxış otağından ibarət olan otaqlar dəstəsindən ibarətdir və hər otaqda digər otaqlara aparan bir neçə tək tərəfli qapı var. Deyzinin məqsədi girişdən çıxışa gedən yolu tapmaqdır.

Deyzinin labirintləri həll etmək üçün bir metodu var. O, hər hansı bir otağın müxtəlif qapılarının fərqli rənglərə malik olduğunu müşahidə edib və buna görə də yolunu qapıların rənglərini izləyərək yadda saxlaya bilir. Bunun üçün o, labirintə girməzdən əvvəl planı öyrənir və keçməli olduğu qapıların rənglərinə uyğun müxtəlif rəngli kartlardan ibarət bir dəst hazırlayır. Hər dəfə bir otağa girdikdə, dəstindəki üst kartın rənginə uyğun olan qapıdan keçir və sonra həmin kartı atır.

Bəzən Deyzinin dəstləri "tam" olmur və o, boş dəstə ilə və ya üst kartın rəngi heç bir qapıya uyğun gəlməyən bir otağa gəlir. Belə hallarda Deyzi otaqdakı qapılardan birindən keçir və üst kartı atmaq əvəzinə, seçdiyi qapının rəngində bir kartı dəstinin üstünə əlavə edir.

Gəlin üç otaq və üç qapıdan ibarət olan aşağıdakı labirint nümunəsini nəzərdən keçirək: girişdən otaq $1$-ə aparan qırmızı qapı, otaq $1$-dən geri girişə aparan ikinci qırmızı qapı və otaq $1$ ilə çıxış arasında mavi qapı. Bu labirint nümunəsində (aşağıda təsvir edilmişdir):

• əgər Deyzi üstündə qırmızı və altında mavi kart olan bir dəstə ilə başlayarsa, o, otaq $1$-ə gedəcək, qırmızı kartı atacaq, sonra çıxışa gedəcək və mavi kartı atacaq;

• əgər Deyzi bir qırmızı kart olan bir dəstə ilə başlayarsa, ilk addım olaraq mütləq otaq $1$-ə gedəcək, qırmızı kartı atacaq və oradan ya mavi qapını seçib çıxışa gedə bilər (dəstinin sonunda boş olub-olmaması əhəmiyyətli deyil) ya da qırmızı qapını seçib yeganə qırmızı kartla girişə qayıda bilər;

• əgər o, boş dəstə ilə başlayırsa və ya girişə gəlirsə, mütləq qeyri-müəyyən müddətə dövr edəcək. Həqiqətən, girişdə yalnız otaq $1$-ə aparan bir qapı var. O, otaq $1$-ə çatdıqda, dəstinin üstündə qırmızı kart var, buna görə də qırmızı qapıdan keçməli və bu kartı atmalı, bu da onu boş dəstə ilə giriş otağına qaytaracaq.

Deyzi bilir ki, bütün labirintlərində həmişə lazımi dəstə ilə giriş otağından çıxış otağına keçə bilər. Lakin bəzi dəstlər onun qaçmasına imkan vermir, hansı seçimi etsə də. O, maraqlanır: ona qaçmağa imkan verən minimal dəstə ölçüsü nədir? Deyzi sizə labirintin planını verir və düzgün seçim edərsə, girişdən çıxışa keçməsinə imkan verəcək minimal dəstə ölçüsünü müəyyən etməyə kömək etməyinizi xahiş edir.