Le réseau électrique a été réparé et le projecteur holographique a enfin démarré avec succès. Alors que la nuit s'approfondit, les projections holographiques dans le ciel deviennent éblouissantes. Une fois tout prêt, petit T et petit S lancent officiellement les activités nocturnes, invitant tout le monde à participer ensemble à ce jeu d'ombre et de lumière minutieusement préparé, testant la complicité du duo : "Aura".

Les faisceaux lumineux au centre de la place s'entrelacent, convergeant lentement pour former un arbre holographique complet. L'arbre lumineux est composé de plusieurs nœuds de groupes de lumière en suspension et de lignes de flux lumineux les reliant, présentant une structure arborescente pure. Au début du jeu, aucune ligne n'est allumée, et les joueurs ne peuvent observer aucune ligne éclairée. Karuha, qui exécute le système, révélera d'abord un nombre mystérieux à un joueur stationné devant la console. Ensuite, les lignes de flux lumineux s'allumeront une par une. Ce joueur doit décider de la direction du flux au moment où chaque ligne apparaît ; tandis que le partenaire, debout à l'autre bout de la scène, doit déduire avec précision ce nombre mystérieux en se basant uniquement sur la structure de l'arbre orienté final.

En tant que participants à la célébration, Neri et Noir décident de coopérer pour relever ce défi.

Dans ce défi, Neri sera stationnée devant la console. Karuha, le système, lui donnera d'abord deux entiers positifs $n, s$ ($1 \le s \le 2^{n-1}$), représentant respectivement le nombre de groupes de lumière contenus dans l'arbre holographique complet et le nombre mystérieux.

Ensuite, Karuha allumera successivement $n - 1$ lignes de flux lumineux, et Neri doit immédiatement spécifier la direction du flux pour chaque ligne au moment où elle s'allume.

Pour Noir, debout à l'autre bout de la scène principale, elle observera la forme finale de l'arbre holographique complet rempli de flux lumineux. Elle doit déduire le nombre mystérieux $s$ transmis par Karuha à Neri en se basant sur la direction du flux de ces lignes.

Pour gagner ce jeu d'ombre et de lumière, Neri et Noir doivent élaborer une stratégie à l'avance afin d'assurer une réussite fluide dans ce jeu qui teste la complicité du duo.

Détails d'implémentation

Votre programme sera exécuté deux fois indépendamment. La première fois, il jouera le rôle de Neri pour décider de la direction du flux de chaque ligne, et la seconde fois, il jouera le rôle de Noir pour déduire le nombre mystérieux à partir de la forme finale de l'arbre holographique. L'interacteur jouera le rôle de Karuha et transmettra les informations à votre programme.

Lors de la première exécution, votre programme recevra d'abord le nombre de groupes de lumière $n$ et le nombre mystérieux $s$ contenus dans l'arbre holographique, puis recevra successivement les $n - 1$ lignes de flux lumineux allumées. Votre programme doit immédiatement envoyer à la bibliothèque d'interaction la direction spécifiée pour le flux, afin de transmettre les informations à la seconde exécution.

Lors de la seconde exécution, votre programme recevra de l'interacteur les informations provenant de la première exécution, c'est-à-dire la direction du flux des lignes de flux lumineux sur l'arbre holographique, puis devra déduire le nombre mystérieux $s$ transmis par Karuha à Neri en se basant sur ces informations.

Entrée

Chaque point de test contient plusieurs groupes de données de test. La première ligne de l'entrée contient deux entiers positifs $T, r$ ($1 \le T \le 10^4, r \in \{1, 2\}$), représentant le nombre de groupes de test et le numéro de l'étape. Pour chaque groupe de test :

• Si $r = 1$, alors :

  • La première ligne contient deux entiers positifs $n, s$ ($3 \le n \le 30, 1 \le s \le 2^{n-1}$), représentant respectivement le nombre de groupes de lumière contenus dans l'arbre holographique complet et le nombre mystérieux ;
  • Ensuite, $n - 1$ lignes de flux lumineux seront allumées successivement. Chaque fois qu'une ligne de flux lumineux est allumée, deux entiers positifs $u, v$ ($1 \le u < v \le n$) sont entrés, représentant les deux groupes de lumière connectés par la ligne de flux lumineux. Vous devez immédiatement sortir une ligne contenant deux entiers positifs $u, v$ ou $v, u$, indiquant que la direction du flux est de $u$ vers $v$ ou de $v$ vers $u$.
  • Pour chaque ligne de flux lumineux, vous devez sortir la direction du flux de cette ligne et vider le tampon de sortie standard avant de pouvoir continuer à recevoir la ligne de flux lumineux suivante.

• Si $r = 2$, alors :

  • La première ligne contient un entier positif $n$ ($3 \le n \le 30$), représentant le nombre de groupes de lumière contenus dans l'arbre holographique complet ;
  • Ensuite, $n - 1$ lignes sont entrées, chaque ligne contenant deux entiers positifs $u, v$ ($1 \le u, v \le n$), représentant une ligne de flux lumineux allant du groupe de lumière $u$ vers le groupe de lumière $v$.
  • Vous devez immédiatement sortir une ligne contenant un entier positif, représentant le nombre mystérieux $s$ déduit.
  • Pour chaque groupe de test, vous devez sortir le nombre mystérieux $s$ déduit et vider le tampon de sortie standard avant de pouvoir continuer à recevoir le groupe de test suivant.
  • L'ordre d'entrée des données de test dans un seul point de test peut être différent de celui de la première exécution.
  • Pour un même groupe de test, l'ordre d'entrée des lignes de flux lumineux peut être différent lors des deux exécutions, mais les numéros des groupes de lumière restent inchangés.

Figure 1 : Première série de données de test

Figure 2 : Deuxième série de données de test

Exemples

Entrée 1

2 1
7 21
1 6
3 5
2 4
3 4
1 2
6 7
9 59
1 2
1 4
3 4
3 5
3 8
5 6
6 7
8 9

Sortie 1

6 1
3 5
4 2
3 4
1 2
7 6
1 2
1 4
3 4
3 5
8 3
5 6
6 7
9 8

Entrée 2

2 2
9
9 8
1 2
5 6
6 7
1 4
3 5
8 3
3 4
7
1 2
4 2
6 1
3 5
3 4
7 6

Sortie 2

59
21

Détails d'implémentation

Le script fourni treedir_testing_tool.py peut vous aider à effectuer des tests locaux pour vérifier l'exactitude de votre programme et imprimer le processus d'interaction détaillé. Lors du test, veuillez placer ce script dans le même répertoire que votre exécutable compilé, puis exécutez la commande suivante dans le terminal :

python3 treedir_testing_tool.py [--quiet] <data_file> <program> <arguments>

Parmi eux : -q, --quiet est un paramètre optionnel. Après avoir utilisé ce paramètre, le script de test n'imprimera plus le processus d'interaction détaillé. data_file est le chemin du fichier d'entrée fourni au script de test. Ce fichier doit respecter le format suivant : La première ligne contient deux entiers non négatifs $T, seed$, représentant respectivement le nombre de groupes de test et la graine aléatoire utilisée pour mélanger l'ordre des tests et l'ordre des connexions dans l'arbre. Si $seed = 0$ est spécifié, cela signifie qu'aucun mélange n'est effectué. Le format de chaque groupe de test est exactement le même que le format d'entrée de la "première exécution" décrite précédemment. program est le chemin de votre exécutable compilé. arguments sont les arguments de ligne de commande supplémentaires transmis à cet exécutable.

Remarque

1. L'implémentation de la bibliothèque d'interaction du script de test n'est pas exactement la même que celle de l'évaluation réelle. Les résultats des tests locaux ne sont pas définitifs et ne sont fournis qu'à titre de référence pour la phase de débogage.
2. Le script de test ne vérifiera que la base du format des données dans data_file et ne vérifiera pas si elles satisfont légalement aux contraintes du problème (par exemple, il ne vérifiera pas si $s$ satisfait la contrainte $1 \le s \le 2^{n-1}$, et ne jugera pas si les lignes de flux lumineux peuvent former correctement un arbre).
3. Le script de test ne surveillera pas la consommation de temps et d'espace du programme et ne peut pas être utilisé pour tester si les contraintes d'espace du problème sont respectées.