== include(page="template/taskheader" task_id="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:

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|).

* Vecinii copilului de pe poziţia $i$ îşi schimbă locurile ({$1 < i < numărul de copii rămaşi in joc$}).
* Vecinii copilului de pe poziţia $i$ sunt eliminaţi din joc ({$1 < i < numărul de copii rămaşi 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\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?

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?

h2. 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|.

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$.

h2. 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|.

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$.

h2. Restricţii generale

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

* $2 ≤ M ≤ N$
* Suma $N$-urilor a celor $T$ teste este $≤ 10^6^$
* $N$ şi $M$ au aceeaşi paritate

h2. Subtaskuri
h3. Subtask 1 (10 puncte)

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

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

h3. Subtask 2 (20 puncte)

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

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

h3. Subtask 3 (20 puncte)

* |T\le10|
* |2\leN\le8|

* $T ≤ 10$
* $2 ≤ N ≤ 8$

h3. Subtask 4 (50 puncte)

* Fără restricţii suplimentare
h2. Exemplu

h3. Explicaţie

...

În primul test, copiii pot efectua următoarele operaţii:
 
{$[3, 1, 4, 2, 5] → interschimbă vecinii lui 2 → [3, 1, 5, 2, 4] → interschimbă vecinii lui 1 → [5, 1, 3, 2, 4] → interschimbă vecinii lui 3 → [5, 2, 3, 1, 4]$}
 
În al doilea test, nu este posibil să se obţină {$[1, 2, 4, 3]$} plecând de la {$[3, 2, 4, 1]$}.
 
În al treilea test, copiii pot efectua următoarele operaţii:
 
{$[1, 6, 4, 3, 2, 5] → interschimbă vecinii lui 3 → [1, 6, 2, 3, 4, 5] → elimină vecinii lui 6 → [6, 3, 4, 5]$}.
 
În al patrulea test, nu este posibil să se obţină {$[2, 4, 1]$} plecând de la {$[4, 2, 3, 1, 5]$}.

== include(page="template/taskfooter" task_id="vecini3") ==