Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Након потпуног уништења Пајазитова, дух Милојица је решио да почасти своју децу златницима. Он је спремио за свако од \(n\) деце по један златник. Златници су нумерисани бројевима од \(1\) до \(n\), и на сваком златнику је написан његов јединствен број. Број на златнику означава индекс детета којем је Милојица наменио тај златник. Како су мали духови веома дисциплинована створења они су се поређали у низ дужине \(n\) сортирано растуће по индексу. Нажалост, Милојица није веровао у своју децу и златнике је поређао у неком поретку који не мора бити растући. Да би избегао незадовољство своје деце, он мора сортирати низ златника у растућем поретку. За овај подухват он користи једно стабло са \(m\) чворова које је преко корена (чвора нумерисаног са \(1\)) повезано са првом позицијом у низу златника.
У једном потезу Милојица може померити један златник на суседно поље ако се у том тренутку на том пољу не налази ниједан златник. Под пољем сматрамо неку позицију у низу златника или неки чвор у стаблу. Приметимо да са позиције \(1\) у низу, златник можемо померити на позицију \(2\) или у корен стабла. Слично, из корена стабла златник можемо померити у неко од његове деце или на позицију \(1\) у низу.
Поставља се једноставно питање: Да ли Милојица након коначно много корака може растуће сортирати своје златнике? Како су духови мало заборавна бића, Милојица није сигуран који је тачно поредак златника оставио и како изгледа стабло повезано са низом, па вас је замолио да одговорите на тражено питање за \(t\) различитих распореда златника и изгледа стабла.
У првој линији стандардног улаза налази се природан број \(t\), број упита за које желимо да испитамо могућност сортирања.
Сваки упит је описан на следећи начин:
У првој линији упита налази се природан број \(n\), број златника и број Милојичине деце.
У другој линији упита налази се пермутација бројева \(\{1, 2, \dots, n\}\): \(p_1, p_2, \dots, p_n\), почетни распоред златника у низу.
У трећој линији упита налази се природан број \(m\), број чворова у стаблу.
Наредних \(m-1\) линија садрже по два броја \(u_i\), \(v_i\), парове повезаних чворова у стаблу.
На стандардни излаз исписати \(t\) линија које представљају одговоре на упите. У \(i\)-тој линији исписати ,,DA’’ (без наводника) ако је у \(i\)-том упиту могуће растуће сортирати низ златника, а у супротном исписати ,,NE’’ (без наводника).
2
3
3 1 2
4
1 2
2 3
1 4
3
3 2 1
2
2 1DA
NE
Први упит изгледа као на слици. Милојица има три детета и три златника. Златници су поређани у редоследу \([3, 1, 2]\). Стабло има четири чвора.
Један од могућих алгоритама сортирања би имао следеће кораке: 1. Померити златник са бројем \(3\) који се налази на позицији \(1\) у низу најпре у корен стабла (чвор нумерисан са \(1\)), након тога у чвор нумерисан са \(4\). 2. Померити златник са бројем \(1\) који се налази на позицији \(2\) у низу најпре на позицију \(1\) у низу, након тога у корен стабла, потом у чвор нумерисан са \(2\) и на крају у чвор нумерисан са \(3\). 3. Померити златник са бројем \(2\) који се налази на позицији \(3\) у низу најпре на позицију \(2\), након тога на позицију \(1\), после тога у корен стабла и најзад у чвор нумерисан са \(2\). 4. Вратити златник са бројем \(3\) који се налази у чвору нумерисаном са \(4\) прво у корен стабла, након тога на позицију \(1\) у низу, па на позицију \(2\) и на крају на позицију \(3\). 5. Вратити златник са бројем \(2\) који се налази у чвору нумерисаном са \(2\) прво у корен стабла, након тога на позицију \(1\) у низу и на крају на позицију \(2\). 6. Вратити златник са бројем \(1\) који се налази у чвору нумерисаном са \(3\) прво у чвор нумерисан са \(2\), након тога у корен стабла и на крају на позицију \(1\) у низу.
Након наведених операција низ златника ће бити сортиран растуће, па је одговор на овај упит,,DA’’.
У другом упиту имамо пермутацију златника сортирану у опадајућем поретку и стабло са два чвора. Како год померали златнике није могуће сортирати их растуће, па је одговор ,,NE’’.
Постоје четири подзадатка:
Стабло је неусмерен повезан граф са \(m\) чворова и \(m-1\) веза. Корен стабла је чвор који нема свог претка у стаблу.