代码：

#include<bits/stdc++.h>
using namespace std;
int d[3][2]={{1,-1},{1,1},{2,0}},n;
bool vis[1000005];
struct node{
    int pos;
    int step;
};
int bfs(){
    queue<node>q;
    node start;
    start.pos=1;
    start.step=0;
    q.push(start);
    vis[1]=true;
    while(!q.empty()){
        start.pos=q.front().pos;
        start.step=q.front().step;
        q.pop();
        if(start.pos==n)return start.step;
        for(int i=0;i<3;i++){
            node point;
            point.pos=start.pos*d[i][0]+d[i][1];
            point.step=start.step+1;
            if(point.pos<=n)
                if(!vis[point.pos]){
                    q.push(point);
                    vis[point.pos]=true;
                }
        }
    }
}
int main(){
    scanf("%d",&n);
    printf("%d",bfs());
    return 0;
}