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 ≤ numarul de copii ramasi in joc ).
• Vecinii copilului de pe poziţia i sunt eliminaţi din joc ( 1 < i < numarul de copii ramasi in 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 ≤ N$) 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 ≤ M ≤ N
• Suma N-urilor a celor T teste este ≤ 10⁶
• N şi M au aceeaşi paritate

Subtaskuri

Subtask 1 (10 puncte)

• N = M în toate cele T teste ale fişierului
• T ≤ 10
• 2 ≤ N ≤ 8

Subtask 2 (20 puncte)

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

Subtask 3 (20 puncte)

• T ≤ 10
• 2 ≤ N ≤ 8

Subtask 4 (50 puncte)

• Fără restricţii suplimentare

Exemplu

Explicaţie

...

Cum se trimit solutii?