... Քանի՞ ժամանակ է անցնելու, մինչև Sky Net-ը վերցնի մարդկությանը: ...
Կա մի դաշտ, որը կարելի է ներկայացնել որպես ցանց, որտեղ տողեր և սյուներ կան: Յուրաքանչյուր բջիջ ունի ուղղություն. աջ (R), ներքև (D), ձախ (L), կամ վեր (U).
Բջիջների ուղղությունների վերաբերյալ որոշ սահմանափակումներ կան.
Բջիջը չի կարող ցույց տալ ցանցի սահմաններից դուրս;
Յուրաքանչյուր բջիջ ունի ճիշտ մեկ բջիջ, որը ցույց է տալիս դրան:
Յուրաքանչյուր բջիջից մենք կարող ենք կրկնակի հետևել ուղղություններին և ստանալ քայլ: (r_1,c_1),(r_2,c_2),\ldots, որտեղ յուրաքանչյուր i\ge 1 համար բջիջ (r_i,c_i) ցույց է տալիս (r_{i+1},c_{i+1})-ին:
Քայլը (r_1,c_1),(r_2,c_2),\ldots,(r_k,c_k) կոչվում է փակ եթե.
k \ge 2;
(r_1,c_1)=(r_k,c_k);
Բոլոր բջիջները (r_1,c_1),(r_2,c_2),\ldots,(r_{k-1},c_{k-1}) զույգ առ զույգ տարբեր են:
Ցանցը կոչվում է գեղեցիկ, եթե ցանցի բջիջները կարող են բաժանվել ճիշտ երկու փակ քայլերի:
Կառուցեք գեղեցիկ ցանց, կամ որոշեք, որ դա անհնար է անել:
Առաջին տողը պարունակում է երկու ամբողջ թիվ և (1 \le n, m \le 100) — ցանցի չափը:
Առաջին տողում արտածեք "Այո", եթե դաշտը գոյություն ունի, և "Ոչ", եթե ոչ:
Եթե պատասխանն է Այո, ապա հաջորդ տողերում արտածեք նիշ {R, D, L, U} — ցանցի նկարագրությունը:
Example 1
Example 2
Առաջին օրինակին, արտածվող ցանցը հետևյալն է.
RRD
ULL
DLL
RRU
Այն կարող է ներկայացվել որպես ճիշտ երկու փակ քայլեր: Օրինակ.
(1,1)\to(1,2)\to(1,3)\to(2,3)\to(2,2)\to(2,1)\to(1,1):
(3,1)\to(4,1)\to(4,2)\to(4,3)\to(3,3)\to(3,2)\to(3,1):
Երկու փակ քայլերը հետևում են սլաքներին, չեն խաչվում և միասին պարունակում են բոլոր n \cdot m բջիջները: Այսպիսով, արտածումը վավեր է:
Երկրորդ օրինակին, կարելի է ցույց տալ, որ անհնար է կառուցել գեղեցիկ 3 \times 3 ցանց:
( միավոր) n=m=2;
( միավոր) n=m=4;
( միավոր) n=2;
( միավոր) n=4;
( միավոր) Երկուսն էլ և զույգ են;
( միավոր) Ոչ մի լրացուցիչ սահմանափակում: