C'est la période de Noël ! Alors que la plupart des lieux de travail participent à des échanges de cadeaux de type « Secret Santa », votre entreprise prépare un complot plus sinistre : découvrir les secrets du Père Noël.

Le Père Noël possède une liste des enfants sages ou pas sages pour chaque humain sur Terre. Comme son contenu est très sensible, la liste est rédigée en polonais du Nord, une langue mystérieuse comportant $N$ lettres. Pour plus de sécurité, le Père Noël a chiffré cette liste avec un chiffrement par substitution : une permutation $H$ des nombres $1, 2, \dots, N$ qui associe chaque lettre $i$ du polonais du Nord à une lettre distincte $H(i)$. Dans un tel chiffrement, deux lettres ne peuvent pas être associées à la même lettre cible — formellement, si $i \neq j$, alors $H(i) \neq H(j)$ — sinon le Père Noël ne pourrait pas déchiffrer sa liste ! (Le Père Noël peut choisir d'associer certaines lettres à elles-mêmes, $H(i) = i$, juste pour être plus rusé.)

Heureusement pour vous, le serveur du Père Noël a été mal configuré et est exposé sur l'Internet public. Vous et vos collègues espérez pirater le serveur du Père Noël, déchiffrer sa liste et confirmer que vous êtes tous sur la liste des enfants pas sages ! (Les pirates sont toujours des enfants pas sages.)

Le serveur a été conçu pour que le Père Noël puisse vérifier rapidement sa liste lors de ses déplacements. Après qu'un utilisateur se connecte au serveur, celui-ci l'invite à saisir la liste des $N$ entiers $H(1), H(2), \dots, H(N)$ encodant la permutation $H$, vérifie que cette liste est correcte, puis déchiffre la liste secrète du Père Noël. Après des mois de recherche, vous avez découvert une vulnérabilité temporelle par canal auxiliaire. Supposons que vous saisissiez une permutation $Q$. Si $H = Q$, le serveur accorde instantanément l'accès. Sinon, considérez un graphe à $N$ sommets, et ajoutez une arête de chaque sommet $i$ vers le sommet $H(Q(i))$. Vous avez découvert que l'algorithme d'authentification complexe du serveur prendra exactement autant de secondes pour vous répondre avec un message d'erreur « Accès refusé » que le nombre de composantes connexes dans le graphe résultant.

Par exemple, supposons que $N = 4$ et que la permutation de chiffrement $H$ soit la suivante :

Si vous essayez de vous connecter au serveur avec l'entrée 4 3 2 1, comme cette permutation ne correspond pas à $H$ et que le graphe décrit ci-dessus possède deux composantes connexes (l'une contenant un cycle d'arêtes $1 \to 4 \to 2 \to 1$ et l'autre contenant uniquement la boucle $3 \to 3$), le serveur répondra avec un message d'erreur « Accès refusé » après un délai de 2 secondes.

Notez que si vous essayez de vous connecter au serveur plusieurs fois avec des entrées $Q$ différentes, il authentifiera chaque $Q$ par rapport au même $H$ stocké. Il ne modifie pas $H$ en réponse à vos entrées.

Le Père Noël remarquera si son serveur est bombardé de requêtes non autorisées. Vous avez estimé que vous ne pouvez effectuer que 1 510 tentatives de connexion avant d'éveiller trop de soupçons. Pouvez-vous trouver une stratégie efficace pour déterminer la permutation de chiffrement ?

Interaction

Il s'agit d'un problème interactif. L'interaction commence par la lecture d'un entier $N$ ($1 \le N \le 220$) depuis l'entrée standard, le nombre de lettres en polonais du Nord. Le juge n'est pas adaptatif : la permutation cachée $H$ est choisie à ce moment-là et ne changera pas pendant le reste de l'interaction.

Pour tenter de vous connecter au serveur, imprimez une ligne avec $N$ entiers séparés par des espaces $Q(1), \dots, Q(N)$, où $Q$ est une permutation de $\{1, 2, \dots, N\}$. Lisez ensuite un seul entier depuis l'entrée standard, le nombre de secondes que le serveur met à répondre à votre entrée.

Si ce délai est 0, vous avez trouvé avec succès la permutation de chiffrement $H$ et votre programme doit se terminer. Sinon, ce délai est le nombre de composantes connexes dans le graphe construit selon la procédure décrite ci-dessus.

Vous pouvez tenter de vous connecter au maximum 1 510 fois. Si vous épuisez vos tentatives, votre programme doit se terminer proprement (bien qu'il soit jugé incorrect pour avoir échoué à déchiffrer la liste du Père Noël).

Notes

N'oubliez pas de vider le flux de sortie après chaque ligne que vous imprimez et de quitter proprement une fois l'interaction terminée. Veuillez également vous assurer de suivre exactement le protocole d'interaction ci-dessus concernant les informations à imprimer sur chaque ligne de sortie : par exemple, si le protocole exige que vous imprimiez une liste d'entiers séparés par des espaces sur une seule ligne, le juge n'acceptera pas chaque entier sur sa propre ligne.

Si le juge reçoit une entrée invalide ou inattendue, il imprimera -1 puis quittera immédiatement. Votre programme doit détecter cela et quitter proprement afin de recevoir un verdict « Wrong Answer ». Si votre programme se bloque en attendant une interaction supplémentaire du juge, ou tente d'interpréter le -1 comme le nombre de composantes, vous pourriez recevoir un verdict de rejet différent (tel que « Time Limit Exceeded » ou « Runtime Error ») au lieu de « Wrong Answer ».

Vous avez reçu un outil en ligne de commande pour les tests locaux. L'outil contient des commentaires en haut expliquant son utilisation.

Exemples

Entrée 1

3

Sortie 1

1 2 3

Entrée 2

1

Sortie 2

2 1 3

Entrée 3

2

Sortie 3

3 1 2

Entrée 4

0