#include <iostream>
#include<fstream>
#include<vector>
#include<deque>
using namespace std;
vector<int> v[11];
void addedge();
int main(){
    int cont=0;
    int visitato[11];
    for(int i=0;i<11;i++)
        visitato[i]=0;
    addedge();
    deque<int> d;
    d.push_back(0);
    int corrente=0;
    int nododaraggiungere;
    cin>>nododaraggiungere;
    int r=0;
    int u=1;
    while(d.size()!=0&&corrente!=nododaraggiungere){
        corrente=d[0];
        d.pop_front();
        if(visitato[corrente]==0){
            r++;
            visitato[corrente]=1;
            for(auto i:v[corrente]){
                if(visitato[i]==0)
                    d.push_back(i);
            }
        }
        if(r>=u&&corrente!=nododaraggiungere){
            cont++;
            r=0;
            u=d.size();
        }
    }
    cout<<endl<<cont;
   return 0;
}

void addedge(){
    v[0].push_back(1);
    v[0].push_back(2);
    v[2].push_back(0);
    v[1].push_back(0);
    v[1].push_back(3);
    v[3].push_back(1);
    v[2].push_back(6);
    v[2].push_back(5);
    v[2].push_back(4);
    v[4].push_back(2);
    v[5].push_back(2);
    v[6].push_back(2);
    v[3].push_back(7);
    v[3].push_back(8);
    v[3].push_back(9);
    v[7].push_back(3);
    v[8].push_back(3);
    v[9].push_back(3);
    v[5].push_back(10);
    v[10].push_back(5);
}