fork download
  1. N, M = [ int(x) for x in input().split() ]
  2.  
  3. train = [ [ False for b in range(N) ] for a in range(N) ]
  4. for m in range(M):
  5. a, b = [ int(x)-1 for x in input().split() ]
  6. train[a][b] = train[b][a] = True
  7. if train[0][N-1]: train = [ [ not train[a][b] for b in range(N) ] for a in range(N) ]
  8.  
  9. dist = [ N+1 for n in range(N) ]
  10. dist[0] = 0
  11. from queue import Queue
  12. Q = Queue()
  13. Q.put(0)
  14. while not Q.empty():
  15. kde = Q.get()
  16. for kam in range(N):
  17. if train[kde][kam]:
  18. if dist[kam] > dist[kde]+1:
  19. dist[kam] = dist[kde]+1
  20. Q.put(kam)
  21.  
  22. print( -1 if dist[N-1]==N+1 else dist[N-1] )
Success #stdin #stdout 0.04s 10360KB
stdin
4 2
1 3
3 4
stdout
2