Trucco Straordinario#11320
Alice è una maga e crea un nuovo trucco. Ha carte con numeri diversi da a scritti su di esse. Prima di tutto, chiede a uno spettatore di mescolare il mazzo e disporre le carte in fila. Sia a_i il numero sulla -esima carta da sinistra.
Poi Alice sceglie due permutazioni e . C'è una restrizione su e : le permutazioni non possono avere punti fissi. In altre parole, \forall i: p_i \ne i e q_i \ne i.
Una volta scelte le permutazioni, Alice mescola le carte secondo di esse. Ora la -esima carta da sinistra diventa la carta a[p[q[i]]]. Il trucco è considerato riuscito se, dopo il rimescolamento, il numero sulla -esima carta da sinistra è .
Aiuta Alice a scegliere le permutazioni e , oppure determina se ciò è impossibile per la permutazione iniziale data.
La prima riga contiene il numero di casi di test (1 \le t \le 10^5).
Ogni test è descritto su due righe. La prima riga contiene un intero (1 \le n \le 10^5) — il numero di carte. La seconda riga contiene interi a_i (1 \le a_i \le n, \forall i \ne j: a_i \ne a_j) — la permutazione iniziale delle carte.
È garantito che la somma di su tutti i test non superi 10^5.
Stampa la risposta per ogni caso di test nell'ordine in cui compaiono nell'input.
Per ogni caso di test, stampa "Impossible" su una singola riga se non esiste alcuna soluzione.
Altrimenti, stampa "Possible" sulla prima riga, seguita da due righe contenenti le permutazioni e .
Esempio 1