Fişierul intrare/ieşire:	vecini3.in, vecini3.out	Sursă	Science On 2021, clasa 9
Autor	Mihaela Cismaru	Adăugată de	Todoran Alexandru Raul •alextodoran
Timp execuţie pe test	0.5 sec	Limită de memorie	268435 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Vecini3

Suntem în anul 2030 şi ăn sfârşit pandemia s-a încheiat iar elevii s-au întors la şcoală. La ora de sport sunt |N| copii numerotaţi cu numerele naturale de la |1| la |N|. La început, aceştia sunt aşezaţi în linie dreaptă într-o anumită ordine. Aşezarea copiilor poate fi văzută ca pe o permutare |A| a numerelor de la |1| la |N|. Copiii joacă un joc în care au voie să efectueze următoarele |2| tipuri de operaţii:

• Vecinii copilului de pe poziţia |i| îşi schimbă locurile (|1<i<numărul de copii rămaşi în joc|).
• Vecinii copilului de pe poziţia |i| sunt eliminaţi din joc (|1<i<numărul de copii rămaşi în joc|).

Chiar dacă una dintre operaţii implică eliminarea a doi copii, acest joc nu este despre un singur câştigător, ci despre lucrul în echipă. Aşadar, profesorul de sport le cere copiiloe să colaboreze şi, plecând de la configuraţia iniţială |A| şi folosind cele două tipuri de operaţii, să ajungă la o configuraţie finală |B|. Configuraţia finală |B| este formată dintr-o submulţime de |M| copii (|M\leN|) a tuturor celor |N| copii aşezaţi în linie dreaptă într-o anumită ordine. Se garantează că |N| şi |M| au aceeaşi paritate. Copiii cunt puţin bulversaţi şi ar vrea mai întâi să ştie dacă măcar este posibil să ajungă din configuraţia iniţială |A| la cea finală |B|. Ai putea să îi ajuţi şi să le răspunzi la această întrebare?

Date de intrare

Prima linie a fişierului de intrare |vecini3.in| conţine numărul |T| de teste din cadrul inputului. Urmează cele |T| teste.
Fiecare test conţine pe prima linie numerele naturale |N| şi |M|. Pe a doua linie a fiecărui test se află |N| numere reprezentând configuraţia iniţială |A|. Pe a treia linie a fiecărui test se află |M| numere reprezentând configuraţia finală |B|. Şirul |A| este o permutare a numereleor de la |1| la |N|, iar şirul |B| este alcătuit din |M| numere distincte cu valori cuprinse între |1| şi |N|.

Date de ieşire

Fişierul de ieşire |vecini3.out| va conţine răspunsul pentru cele |T| teste, pe rânduri separate. Dacă este posibil să se ajungă din configuraţia iniţială în cea finală atunci se afişează |1|, altfel se afişează |0|.

Restricţii generale

• |2\leM\leN|
• Suma |N|-urilor a celor |T| teste este |\le10^{6}|
• |N| şi |M| au aceeaşi paritate

Subtaskuri

Subtask 1 (10 puncte)

• |N=M| în toate cele |T| teste ale fişierului
• |T\le10|
• |2\leN\le8|

Subtask 2 (20 puncte)

• |N=M| în toate cele |T| teste ale fişierului

Subtask 3 (20 puncte)

• |T\le10|
• |2\leN\le8|

Subtask 4 (50 puncte)
* Fără restricţii suplimentare

Exemplu

Explicaţie

...

Cum se trimit solutii?