==
Bineînţeles, acest algoritm nu este întotdeauna corect, deoarece distanţa calculată depinde de ordinea în care sunt procesaţi vecinii unui nod în timpul citirii.

De exemplu, dacă la construirea grafului se citeşte întâi muchia $(1 → 2)$ şi apoi muchia $(1 → 3)$, atunci când vecinii lui $1$ sunt prelucraţi, primul vecin va fi $2$, iar următorul va fi $3$.Aşadar, distanţa calculată cu primul algoritm de mai sus poate fi diferită, în funcţie de ordinea în care sunt adăugate muchiile de la citire. Prin urmare, pentru un graf dat, suntem curioşi pentru câte dintre cele **$M!$** permutări ale muchilor lui **$G$**, algoritmul DFS va da distanţa minimă.

De exemplu, dacă la construirea grafului se citeşte întâi muchia $(1 → 2)$ şi apoi muchia $(1 → 3)$, atunci când vecinii lui $1$ sunt prelucraţi, primul vecin va fi $2$, iar următorul va fi $3$. Aşadar, distanţa calculată cu primul algoritm de mai sus poate fi diferită, în funcţie de ordinea în care sunt adăugate muchiile de la citire. Prin urmare, pentru un graf dat, suntem curioşi pentru câte dintre cele **$M!$** permutări ale muchilor lui **$G$**, algoritmul DFS va da distanţa minimă.

h2. Date de intrare

* Se garantează că pentru teste în valoare de $25%$ din punctaj, $N <= 20, M ≤ 60$.
* Se garantează că pentru teste în valoare de $60%$ din punctaj, $N <= 1400, M ≤ 4000$.
* Se garantează că o muchie nu va apărea de două ori în fişierul de intrare.

* Se garantează că fiecare muchie aparţine cel puţin unui drum de la **$1$** la **$N$**.

* Se garantează că fiecare muchie aparţine cel puţin unui drum de la $1$ la $N$.

h2. Exemple