Breadth First Search (BFS)

#include <iostream>

#include <cstdio>

#include <vector>

#include <queue>

using namespace std;

#define siz 1000005

vector <int> vec[siz];

queue <int> q;

bool color[siz];

int cost[siz];

int node,edge;



void reset(){

    for(int i=0;i<=node;i++){

        color[i]=false;

        cost[i]=0;

        vec[i].clear();

    }

}



void BFS(int source, int destination){

    cost[source]=0;

    color[source]=1;

    q.push(source);



    while(!q.empty()){

        int u=q.front();

        q.pop();



        for(int i=0;i<vec[u].size();i++){

            int v=vec[u][i];

            if(!color[v]){

                color[v]=true;

                cost[v]=cost[u]+1;

                q.push(v);

            }

        }

    }



    printf("%d\n",cost[destination]);

}

int main()

{

    int u,v;

    //freopen("input.txt","r",stdin);

    while(scanf("%d%d",&node,&edge)==2){

        reset();



        for(int i=0;i<=edge;i++){

            scanf("%d%d",&u,&v);

            vec[u].push_back(v);

            vec[v].push_back(u);

        }



        BFS(1,node);

    }

    return 0;

}