Unfoldung
Ramtung, baş doktorant tələbə, bu il ACM proqramlaşdırma müsabiqəsi üçün bir problem təklif etməlidir. O, doktorantura tədqiqatlarına çox cəlb olunduğundan, tədqiqat sahəsindən kənarda heç nə düşünə bilmir; hamısı hesablama həndəsəsində ən qısa yollar haqqında.
Bu sahədəki problemlərdən biri, polihedron səthində verilmiş iki nöqtə arasında ən qısa yolu tapmaqdır. Belə yolları tapmağa kömək edən bir texnika açılmadır. Polihedronun səthini bəzi xətt seqmentləri boyunca kəsirik ki, onu ümumi bir müstəviyə açmaq mümkün olsun. Bu düz səth bizə istənilən yolu tapmaq üçün daha sadə texnikaları tətbiq etməyə imkan verir. Unfoldung problemində (müəllifi Ramtungun adını daşıyır) sizdən verilmiş polihedron səthinin kənarlarından bir neçəsi boyunca kəsildikdə ümumi bir müstəviyə açıla biləcəyini tapmaq tələb olunur.
Tapşırığınızı sadələşdirmək üçün, üz-üzə yapışdırılmış vahid kublardan ibarət bərk cismin xarici səthini giriş kimi qəbul edirik ki, hər bir kub ən azı bir başqa kubla bitişikdir (əgər obyekt tək bir kubdan ibarət deyilsə). İki kubun bitişik olduğunu deyirik, əgər onların tam olaraq bir ortaq üzü varsa. Biz obyektin xarici səthini açmaq istəyirik (yəni yapışdırılmış üzləri nəzərə almırıq) ki, düz bir düzən əldə edək. Problemin girişi xarici səthin təsviri və kəsiləcək səthin bir neçə vahid kənarının təsviridir. Sadəlik üçün, verilmiş obyektin elə olduğunu qəbul edə bilərsiniz ki, xarici səthin hər bir kənarı xarici səthin tam olaraq iki üzünə bitişikdir.
Məsələn, Şəkil a və Şəkil b iki yapışdırılmış kubun xarici səthinin ümumi bir müstəviyə necə açıldığını göstərir. Şəkil a-da, nöqtəli kənarlar kəsilməyib və bərk xətlər kəsilənləri göstərir. Qeyd edək ki, efgh üzü xarici səthin bir hissəsi deyil. Bu nümunənin giriş məlumatları birinci nümunə girişində verilir. (Sağ düzəndəki üzlərin içindəki rəqəmlər (Şəkil b) nümunə giriş məlumatlarında üzləri müəyyən etmək üçün istifadə olunur.)
Sizdən belə bir səthin üzlərini açdıqdan sonra ümumi bir müstəviyə yerləşdirilə biləcəyini müəyyən edən bir proqram yazmaq tələb olunur. Açılma dedikdə, bir üzü onun kənarlarından biri ətrafında fırladaraq həmin kənara bitişik digər üzlə eyni müstəviyə gətirmək nəzərdə tutulur (belə ki, səthin içindəki üzlər arasında yaranan bucaq 180º olacaq). Qeyd edək ki, açıldıqdan sonra əldə edilən düzən üst-üstə düşə bilər. Mümkünsə, bir neçə üzü birlikdə fırlatmaq olar.
Giriş verilənləri
Giriş faylının ilk sətri bir tam ədəd t (1 ≤ t ≤ 10) ehtiva edir, test halların sayını göstərir, ardınca hər bir test halı üçün giriş məlumatları gəlir. Hər bir test halının ilk sətri xarici səthdəki üzlərin sayını göstərən bir tam ədəd f (6 ≤ f ≤ 10000) ehtiva edir. Üzlərin 1-dən f-ə qədər unikal nömrələndiyini qəbul edin. İkinci sətrdə xarici səthin üzləri arasında olan vahid kənarların sayını göstərən tam ədəd n gəlir, ardınca tam olaraq n sətir gəlir, hər biri x+y və ya x-y formasında bir sətir ehtiva edir. x və y fərqli tam ədədlərdir (1 ≤ x, y ≤ f) və səthin iki üzünü təmsil edir. Hər iki forma x üzünün y üzünə ortaq bir kənar boyunca bitişik olduğunu göstərir. Plus işarəsi x və y arasında ortaq olan kənarın kəsildiyini (bərk xətlər Şəkil a-da) və minus işarəsi kənarın kəsilmədiyini (nöqtəli xətlər) göstərir. Sətirdə boş simvol yoxdur və girişdə boş sətirlər yoxdur.
Çıxış verilənləri
Hər bir test halı üçün bir sətir olmalıdır ki, test halına aid çıxışı göstərsin. Çıxış, verilmiş səthi açmaq mümkün olarsa CAN UNFOLD, səthi açmaq mümkün deyilsə CANNOT UNFOLD və kəsilmiş kənarlar səthi iki və ya daha çox hissəyə ayırırsa DISCONNECTED olmalıdır. Qeyd edək ki, səth ayrılmışsa, çıxışınız səthin açılıb-açılmayacağından asılı olmayaraq DISCONNECTED olmalıdır. Çıxışın böyük-kiçik hərf həssas olduğunu unutmayın.