Codeforces-The Two Routes Solution

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;


public class Thetworoutes {

static int distance[];
static boolean visited[];
public static void main(String[] args)
{
MyScannerttr sc=new MyScannerttr();
int n=sc.nextInt();
int m=sc.nextInt();
List<Integer> r[]= new ArrayList[n];
List<Integer> b[]= new ArrayList[n];
int i,j;
visited=new boolean[n];
distance=new int[n];
for(i=0;i<n;i++)
{
r[i]=new ArrayList<Integer>();
b[i]=new ArrayList<Integer>();
}
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
b[i].add(j);
b[j].add(i);
}
}

for(i=0;i<m;i++)
{
int s=sc.nextInt()-1;
int d=sc.nextInt()-1;
r[s].add(d);
r[d].add(s);
b[s].remove((Integer)d);
b[d].remove((Integer)s);
}

Arrays.fill(distance,-1);
if(r[0].contains(n-1))
{
bfs(b);
}
else
{
bfs(r);
}
System.out.println(distance[n-1]);

}
static void bfs(List<Integer> a[])
{
distance[0]=0;
Queue<Integer> queue=new LinkedList<Integer>();
queue.add(0);
int u;
visited[0]=true;
while(!queue.isEmpty())
{
u=queue.poll();

for(Integer v:a[u])
{
if(visited[v]==false){
distance[v]=distance[u]+1;
visited[v]=true;
queue.add(v);
}
}
}
}

}
class MyScannerttr
{
BufferedReader br;
StringTokenizer st;
MyScannerttr()
{
br=new BufferedReader(new InputStreamReader(System.in));
}
String next()
{

while(st==null || !st.hasMoreTokens())
{
try
{
st=new StringTokenizer(br.readLine());
}
catch(Exception e)
{
e.printStackTrace();
}
}
return st.nextToken();

}
int nextInt()
{
return Integer.parseInt(next());
}
long nextLong()
{
return Long.parseLong(next());
}
double nextDouble()
{
return Double.parseDouble(next());
}
String nextLine()
{
String str="";
try
{
str=br.readLine();
}
catch(Exception e)
{
e.printStackTrace();
}
return str;

}
}