Bajtysia et Bajteusz sont des voyageurs célèbres qui ont visité presque tous les recoins de Bajtocja. Ce pays se compose de $n$ villes, numérotées de $1$ à $n$, reliées par un réseau de routes à sens unique. Cependant, ils se sont lassés des méthodes de voyage traditionnelles – ils sont déjà allés partout où ils pouvaient se rendre.

Récemment, Bajtysia a acquis un ancien artefact magique : le Registre des Routes. Il permet la création de nouvelles routes à sens unique entre les villes. Il y a cependant un piège. La magie du registre est capricieuse et ne permet de créer une route entre deux villes que s'il est actuellement impossible de voyager de la première ville à la seconde en utilisant le réseau de routes existant (c'est-à-dire qu'il n'existe aucune séquence de routes menant de la première ville à la seconde ; il est toutefois possible qu'il existe une séquence de routes menant de la seconde ville à la première). Une tentative de créer une route entre des villes déjà reliées échouera et détruira le registre.

Pour Bajtysia et Bajteusz, c'est un défi merveilleux ! Ils ont immédiatement décidé qu'ils voulaient conjurer autant de nouvelles routes que possible.

Malheureusement, Bajtysia et Bajteusz sont trop occupés à planifier leur prochaine expédition pour résoudre ce problème par eux-mêmes. Aidez-les à planifier quelles routes doivent être créées une par une afin que leur nombre total soit aussi grand que possible.

Entrée

La première ligne de l'entrée contient deux entiers $n$ et $m$ ($1 \le n \le 1500$, $0 \le m \le n(n-1)$), représentant respectivement le nombre de villes et le nombre de routes à sens unique à Bajtocja. Les $m$ lignes suivantes contiennent les descriptions des routes. La $i$-ème de ces lignes (pour $1 \le i \le m$) contient deux entiers $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$), indiquant qu'il existe une route à sens unique de la ville $a_i$ vers la ville $b_i$. Les routes à sens unique décrites ne se répètent pas.

Sortie

Sur la première ligne de la sortie, imprimez un seul entier non négatif $k$ représentant le nombre maximum de routes à sens unique pouvant être créées de telle sorte que chaque route successive relie une paire de villes entre lesquelles il n'est pas possible de voyager actuellement. Les $k$ lignes suivantes doivent décrire les routes qui doivent être créées dans l'ordre. La $i$-ème de ces lignes (pour $1 \le i \le k$) doit contenir deux entiers $c_i, d_i$ représentant les villes entre lesquelles la $i$-ème route doit être créée. Au moment de la création de cette route, il ne doit pas être possible de voyager de la ville $c_i$ à la ville $d_i$ en utilisant les routes déjà existantes (c'est-à-dire à la fois les initiales et celles créées précédemment). S'il existe plusieurs solutions possibles, imprimez-en n'importe laquelle.

Exemples

Entrée 1

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

Sortie 1

3
4 1
6 4
7 6

Entrée 2

3 0

Sortie 2

5
3 1
3 2
2 1
2 3
1 2

Remarque

Explication de l'exemple : Dans le premier exemple, le réseau de routes initialement existant est illustré ci-dessous.

Il n'est pas possible de voyager de la ville 4 à la ville 1, donc une telle route peut être ajoutée pour obtenir le réseau de routes illustré ci-dessous.

Après avoir ajouté des routes de la ville 6 à la ville 4 et de la ville 7 à la ville 6, nous obtenons un réseau dans lequel il est possible de voyager entre chaque paire de villes. Aucune autre arête ne peut être ajoutée.

Sous-tâches

Si seule la première ligne de votre réponse est correcte, votre solution recevra 50 % des points pour ce test. Vous n'avez pas besoin d'imprimer les lignes suivantes pour recevoir ces points.