Contexte

Après avoir terminé une discussion fastidieuse sur la recherche et la relecture, le sujet de la discussion s'est progressivement tourné vers les interactions sociales quotidiennes. Xiao T a partagé avec enthousiasme une découverte intéressante : sur une plateforme sociale couramment utilisée, les relations de suivi entre les utilisateurs sont strictement unidirectionnelles, c'est-à-dire qu'il n'existe pas de cas où deux utilisateurs se suivent mutuellement.

Ce phénomène curieux a immédiatement suscité une discussion. Xiao S a profité de l'occasion pour extraire certaines données statistiques du réseau, collectant le nombre de suivis et d'abonnés de chaque utilisateur. Malheureusement, lors de la transmission des données, elle en a accidentellement perdu une partie, ne laissant qu'un ensemble composé de plusieurs entiers positifs. Xiao S a découvert que pour chaque élément de l'ensemble, il est toujours possible de trouver au moins un utilisateur dont le nombre de suivis ou le nombre d'abonnés est exactement égal à cet élément.

Comme la structure complète des suivis de la plateforme est confidentielle, le réseau social spécifique est inconnu. Afin de vérifier la plausibilité de ces données résiduelles, tout le monde a pris du papier et un crayon pour tenter de reconstruire un réseau conforme aux conditions. Pour ajouter un peu de plaisir et de compétitivité, ils ont même lancé un petit concours pour voir qui pourrait construire le réseau social avec le nombre total de suivis le plus faible.

Sur cette plateforme sociale, il y a $n$ utilisateurs. Xiao S a collecté un ensemble de nombres de taille $m$, $\{c_1, \dots, c_m\}$. Selon ces informations, un réseau de suivi possible peut être modélisé par un graphe orienté $G = (V, E)$ satisfaisant les conditions suivantes :

• Il contient $n$ utilisateurs, soit l'ensemble des sommets $V = \{1, 2, \dots, n\}$ ;
• Il n'existe pas d'utilisateur se suivant lui-même ou de suivi répété, c'est-à-dire que le graphe $G$ ne contient ni boucle ni arête multiple ;
• Toutes les relations de suivi sont strictement unidirectionnelles, c'est-à-dire que pour toute arête orientée $(u, v) \in E$, on a $(v, u) \notin E$ ;
• Pour chaque élément $c_i$ de l'ensemble ($1 \le i \le m$), il existe au moins un sommet dans le graphe $G$ dont le degré sortant (correspondant au nombre de suivis) ou le degré entrant (correspondant au nombre d'abonnés) est exactement égal à $c_i$.

Vous devez, à partir des informations collectées par Xiao S, reconstruire un réseau de suivi avec un nombre total de suivis minimal (c'est-à-dire un graphe $G$ avec le nombre minimal d'arêtes).

Entrée

La première ligne de l'entrée contient un entier non négatif $o \in \{0, 1\}$, représentant le paramètre de sortie.

La deuxième ligne de l'entrée contient deux entiers positifs $n, m$ ($1 \le m < n \le 10^6$), représentant le nombre d'utilisateurs et la taille de l'ensemble collecté par Xiao S. Il est garanti que si $o = 0$, alors $n \le 2 \times 10^3$.

La troisième ligne de l'entrée contient $m$ entiers positifs distincts deux à deux $c_1, c_2, \dots, c_m$ ($1 \le c_i \le n - 1$), représentant les éléments de l'ensemble collecté par Xiao S.

Sortie

Affichez sur une ligne un entier positif $k$, représentant le nombre minimal total de suivis parmi tous les réseaux de suivi possibles.

Si $o = 0$, affichez ensuite $k$ lignes, chaque ligne contenant deux entiers positifs $u, v$ ($1 \le u, v \le n$), indiquant que l'utilisateur $u$ suit l'utilisateur $v$, soit $(u, v) \in E$.

Exemples

Entrée 1

0
5 4
3 1 4 2

Sortie 1

7
3 2
4 1
3 4
4 5
3 5
4 2
3 1