Ceci est un problème de type « output-only ». Notez que vous devez tout de même envoyer un code qui affiche la sortie, et non un fichier texte.

Un 3-coloriage valide d'un graphe est une assignation de couleurs (nombres) de l'ensemble $\{1, 2, 3\}$ à chacun des $n$ sommets, telle que pour toute arête $(u, v)$ du graphe, les sommets $u$ et $v$ aient une couleur différente. Il existe au plus $3^n$ tels coloriages pour un graphe à $n$ sommets.

Vous travaillez dans une entreprise et aspirez à devenir un spécialiste de la création de graphes possédant un nombre donné de 3-coloriages. Un jour, vous apprenez que vous recevrez le soir même une commande pour produire un graphe ayant exactement $6k$ 3-coloriages. Vous ne connaissez pas la valeur exacte de $k$, seulement que $1 \le k \le 500$.

Vous ne voulez pas attendre la valeur spécifique de $k$ pour commencer à créer le graphe. Par conséquent, vous construisez au préalable un graphe avec au plus 19 sommets. Ensuite, après avoir appris la valeur particulière de $k$, vous êtes autorisé à ajouter au plus 17 arêtes au graphe pour obtenir le graphe requis ayant exactement $6k$ 3-coloriages.

Pouvez-vous le faire ?

Entrée

Il n'y a pas d'entrée pour ce problème.

Sortie

Affichez d'abord $n$ et $m$ ($1 \le n \le 19$, $1 \le m \le \frac{n(n-1)}{2}$) — le nombre de sommets et d'arêtes du graphe initial (celui construit au préalable). Ensuite, affichez $m$ lignes de la forme $(u, v)$ — les arêtes du graphe.

Ensuite, pour chaque $k$ de 1 à 500, effectuez ce qui suit :

Affichez $e$ — le nombre d'arêtes que vous ajouterez pour ce $k$ particulier ($1 \le e \le 17$). Ensuite, affichez $e$ lignes de la forme $(u, v)$ — les arêtes que vous ajouterez à votre graphe.

Il ne peut y avoir de boucles, et pour chaque $k$, toutes les $m + e$ arêtes que vous utilisez doivent être distinctes deux à deux. Le nombre de 3-coloriages du graphe pour un $k$ particulier doit être exactement $6k$.

Exemples

Entrée 1

-

Sortie 1

3 2
1 2
2 3
1
1 3
0

Remarque

L'exemple de sortie est donné à titre indicatif. Il contient la sortie pour $k = 1, 2$.