#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000
#define MAXM 10000
#define min(a, b) ((a) < (b) ? (a) : (b))
int kon[MAXN], nasl[MAXM], // uložení grafu ve formě seznamu sousedů
    nahrad[MAXN], // nahrazení vrcholu číslem silně souvislé komponenty
    cislo[MAXN], nejnizsi[MAXN], aktualni, // proměnné pro Tarjana
    poc[MAXN], // počet hran vycházejících z vrcholu
    stack[MAXN], pos_stack, // zásobník a pozice jeho vrcholu
    instack[MAXN], // pole určující, jestli je vrchol v zásobníku 
    nasl2[MAXM], kon2[MAXN], poc2[MAXN], // kondenzovaný graf
    pocetSSK; // počet silně souvislých komponent

void tarjan(int v) {
    cislo[v] = aktualni; // očíslování vrcholu
    nejnizsi[v] = aktualni; // inicializace nejnižšího dosaženého
    aktualni++;
    stack[pos_stack++] = v; // přidej do zásobníku
    instack[v] = 1;
    int v2;
    for (int i = kon[v] - poc[v]; i < kon[v]; i++) { 
        v2 = nasl[i]; // následník
        if (cislo[v2] == -1) { // vrchol nenavšíven
            tarjan(v2);
            nejnizsi[v] = min(nejnizsi[v], nejnizsi[v2]);
        }
        else if (instack[v2]) nejnizsi[v] = min(nejnizsi[v], cislo[v2]); // vrchol je v zásobníku, není tedy ještě v žádné SSK
    }
    if (nejnizsi[v] == cislo[v]) { // nalezena SSK
        int j = 0;
        if (pocetSSK > 0) j = kon2[pocetSSK - 1];
        do { // odebírej vrcholy ze zásobníku
            if (pos_stack > 0) {
                 v2 = stack[--pos_stack];
                 instack[v2] = 0;
                 // přidej vrchol do SSK
                 nahrad[v2] = pocetSSK;
                 // nový seznam následníků
                 for (int i = kon[v2] - poc[v2]; i < kon[v2]; i++)
                    nasl2[j++] = nasl[i];
            }
        } while (v2 != v && pos_stack > 0);
        kon2[pocetSSK++] = j;
    }
}

int main(void) {
    int n, m;
    // načti vstup
    scanf("%d %d", &n, &m); // počet měst a kurýrů
    int h1[MAXM], h2[MAXM];
    // načti orientované hrany
    for (int i = 0; i < m; i++) {
        scanf("%d %d", h1 + i, h2 + i);
        poc[h1[i]]++; // zvyš počet hran vedoucích z vrcholu
    }
    kon[0] = 0;
    nahrad[0] = 1; nejnizsi[0] = cislo[0] = -1;
    for (int i = 1; i < n; i++) {
        kon[i] = kon[i - 1] + poc[i - 1];
        nahrad[i] = i; nejnizsi[i] = cislo[i] = -1; // inicializace
    }
    for (int i = 0; i < m; i++)    nasl[kon[h1[i]]++] = h2[i];   // vytvoř seznam následníků

    // Tarjanův algoritmus
    aktualni = 0; pocetSSK = 0; pos_stack = 0;  // init; zasobnik je prazdny
    for (int i = 0; i < n; i++)
        if (cislo[i] == -1)    // nalezen neočíslovaný vrchol
            tarjan(i);      // spusť prohledávání do hlouby
    
    if (pocetSSK == 1) {        // jen jedna silně souvislá komponenta
        printf("Existuje cesta mezi kazdymi dvema mesty alespon jednim smerem.\n");
        return 0;
    }
    
    // nejprve spočti počet hran vedoucích do vrcholů
    int v = 0;    // index aktuální SSK
    for (int i = 0; i < m; i++)    {
        while (i == kon2[v]) v++;
        if (nahrad[nasl2[i]] != v)  poc2[nahrad[nasl2[i]]]++; // pokud hrana vede jinam než do této SSK
    }
    // najdi SSK, do které nevede hrana
    int prvni = -1;
    for (int i = 0; i < pocetSSK; i++) {
        if (poc2[i] == 0) {    // do SSK nevede hrana
            if (prvni == -1) prvni = i;
            else {        // více SSK, do nichž nevede hrana
                printf("Neexistuje cesta alespon jednim smerem mezi kazdymi dvema mesty.\n");
                return 0;
            }
        } 
    }
    // prohledáváním do šířky najdi co nejdelší cestu
    int fronta[MAXN]; // fronta na prohledávání do šířky
    int navstiveno[MAXN]; // navstivili jsme uz SSK?
    int kon_fronta = 0, zac_fronta = 0;
    fronta[kon_fronta++] = prvni;
    navstiveno[prvni] = 1;
    while (zac_fronta < kon_fronta) {
        int v = fronta[zac_fronta++]; // odeber z fronty
        // projdi následníky
        for (int i = v > 0 ? kon2[v - 1] : 0; i < kon2[v]; i++) { 
            int a = nahrad[nasl2[i]]; // do jaké SSK jsme se dostali?
            if (a == v) continue; // jsme pořád v té samé SSK
            // přes jaký největší počet SSK se tam dostaneme?
            if (navstiveno[a] < navstiveno[v] + 1) {
                navstiveno[a] = navstiveno[v] + 1;
                if (navstiveno[a] == pocetSSK) { // máme SSK, do níž vede cesta přes všechny SSK
                    printf("Existuje cesta mezi kazdymi dvema mesty alespon jednim smerem.\n");
                    return 0;
                }
            }
            poc2[a]--; // odeber hranu
            if (poc2[a] == 0)  fronta[kon_fronta++] = a; // pokud už do SSK nevede žádná další hrana, zařadíme ji do fronty 
        } 
    }
    printf("Neexistuje cesta alespon jednim smerem mezi kazdymi dvema mesty.\n");
    return 0;
}