import java.util.*;

public class Reitinhaku {
    static ArrayList<Integer>[] verkko;
    static int[] muisti;

    static void lisaaKaari(int a, int b) {
        verkko[b].add(a);
    }
    
    static int lyhinReitti(int solmu) {
        if (solmu == 1) return 0;
        if (muisti[solmu] != -1) return muisti[solmu];
        int paras = 999999999;
        for (int edellinen : verkko[solmu]) {
            int uusi = lyhinReitti(edellinen)+1;
            if (uusi < paras) paras = uusi;
        }
        muisti[solmu] = paras;
        return paras;
    }

    static int pisinReitti(int solmu) {
        if (solmu == 1) return 0;
        if (muisti[solmu] != -1) return muisti[solmu];
        int paras = -999999999;
        for (int edellinen : verkko[solmu]) {
            int uusi = pisinReitti(edellinen)+1;
            if (uusi > paras) paras = uusi;
        }
        muisti[solmu] = paras;
        return paras;
    }    
    
    public static void main(String[] args) {
        // reitin etsiminen suunnatussa syklittömässä verkossa
        //     2---->3
        //    /       \
        //   1         7       lyhin pituus: 3
        //    \       /        pisin pituus: 4
        //     4->5->6
        /*int n = 7;
        verkko = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) {
            verkko[i] = new ArrayList<>();
        }
        muisti = new int[n+1];
        lisaaKaari(1,2);
        lisaaKaari(2,3);
        lisaaKaari(3,7);
        lisaaKaari(1,4);
        lisaaKaari(4,5);
        lisaaKaari(5,6);
        lisaaKaari(6,7);
        for (int i = 1; i <= n; i++) muisti[i] = -1;
        System.out.println(lyhinReitti(7)); // 3
        for (int i = 1; i <= n; i++) muisti[i] = -1;
        System.out.println(pisinReitti(7)); // 4
        */

        // tässä verkossa on sykli, joten algoritmi ei toimi
        //     8<----9
        //     v     ^
        //     2---->3
        //    /       \
        //   1         7
        //    \       /
        //     4<-5<-6
        /*int n = 9;
        verkko = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) {
            verkko[i] = new ArrayList<>();
        }
        muisti = new int[n+1];
        lisaaKaari(1,2);
        lisaaKaari(2,3);
        lisaaKaari(3,7);
        lisaaKaari(4,1);
        lisaaKaari(5,4);
        lisaaKaari(6,5);
        lisaaKaari(7,6);
        lisaaKaari(3,9);
        lisaaKaari(9,8);
        lisaaKaari(8,2);
        for (int i = 1; i <= n; i++) muisti[i] = -1;
        System.out.println(lyhinReitti(7)); // ???
        for (int i = 1; i <= n; i++) muisti[i] = -1;
        System.out.println(pisinReitti(7)); // ???
        */
        
        // vaikean syötteen tekeminen algoritmille
        // 1 -> 2 -> 3 -> ... -> n         2^(n-1)
        //   *2   *2   *2
        /*
        int n = 100;
        verkko = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) {
            verkko[i] = new ArrayList<>();
        }
        muisti = new int[n+1];
        for (int i = 1; i <= n; i++) muisti[i] = -1;
        for (int i = 1; i <= n-1; i++) {
            lisaaKaari(i,i+1);
            lisaaKaari(i,i+1);
        }
        System.out.println(lyhinReitti(n)); // n-1
        */
    }
}