== 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:
* 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?
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 <tex>N</tex> copii numerotaţi cu numerele naturale de la <tex>1</tex> la <tex>N</tex>. 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 <tex>A</tex> a numerelor de la <tex>1</tex> la <tex>N</tex>. Copiii joacă un joc în care au voie să efectueze următoarele <tex>2</tex> tipuri de operaţii:
* Vecinii copilului de pe poziţia <tex>i</tex> îşi schimbă locurile (<tex>1 < i < numărul de copii rămaşi în joc</tex>).
* Vecinii copilului de pe poziţia <tex>i</tex> sunt eliminaţi din joc (<tex>1 < i < numărul de copii rămaşi în joc</tex>).
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ă <tex>A</tex> şi folosind cele două tipuri de operaţii, să ajungă la o configuraţie finală <tex>B</tex>. Configuraţia finală <tex>B</tex> este formată dintr-o submulţime de <tex>M</tex> copii (<tex>M \le N</tex>) a tuturor celor <tex>N</tex> copii aşezaţi în linie dreaptă într-o anumită ordine. Se garantează că <tex>N</tex> şi <tex>M</tex> 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ă <tex>A</tex> la cea finală <tex>B</tex>. 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 <tex>vecini3.in</tex> conţine numărul <tex>T</tex> de teste din cadrul inputului. Urmează cele <tex>T</tex> teste.
Fiecare test conţine pe prima linie numerele naturale <tex>N</tex> şi <tex>M</tex>. Pe a doua linie a fiecărui test se află <tex>N</tex> numere reprezentând configuraţia iniţială <tex>A</tex>. Pe a treia linie a fiecărui test se află <tex>M</tex> numere reprezentând configuraţia finală <tex>B</tex>. Şirul <tex>A</tex> este o permutare a numereleor de la <tex>1</tex> la <tex>N</tex>, iar şirul <tex>B</tex> este alcătuit din <tex>M</tex> numere distincte cu valori cuprinse între <tex>1</tex> şi <tex>N</tex>.
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 <tex>vecini3.out</tex> va conţine răspunsul pentru cele <tex>T</tex> teste, pe rânduri separate. Dacă este posibil să se ajungă din configuraţia iniţială în cea finală atunci se afişează <tex>1</tex>, altfel se afişează <tex>0</tex>.
h2. Restricţii generale
* |2\leM\leN|
* Suma |N|-urilor a celor |T| teste este |\le10^{6}|
* |N| şi |M| au aceeaşi paritate
* <tex>2 \le M \le N</tex>
* Suma <tex>N</tex>-urilor a celor <tex>T</tex> teste este <tex>\le 10^{6}</tex>
* <tex>N</tex> şi <tex>M</tex> au aceeaşi paritate
h2. Subtaskuri
h3. Subtask 1 (10 puncte)
h1. Subtask 1 (10 puncte)
* |N=M| în toate cele |T| teste ale fişierului
* |T\le10|
* |2\leN\le8|
* <tex>N = M</tex> în toate cele <tex>T</tex> teste ale fişierului
* <tex>T \le 10</tex>
* <tex>2 \le N \le 8</tex>
h3. Subtask 2 (20 puncte)
h1. Subtask 2 (20 puncte)
* |N=M| în toate cele |T| teste ale fişierului
* <tex>N = M</tex> în toate cele <tex>T</tex> teste ale fişierului
h3. Subtask 3 (20 puncte)
h1. Subtask 3 (20 puncte)
* |T\le10|
* |2\leN\le8|
* <tex>T \le 10</tex>
* <tex>2 \le N \le 8</tex>
h3. Subtask 4 (50 puncte)
h1. Subtask 4 (50 puncte)
* Fără restricţii suplimentare
h2. Exemplu
