给定一个n个点m条边的有向图，图中可能存在重边和自环。

所有边的长度都是1，点的编号为1~n。

请你求出1号点到n号点的最短距离，如果从1号点无法走到n号点，输出-1。

输入格式

第一行包含两个整数n和m。

接下来m行，每行包含两个整数a和b，表示存在一条从a走到b的长度为1的边。

输出格式

输出一个整数，表示1号点到n号点的最短距离。

数据范围

1≤n,m≤105

输入样例：

4 5
1 2
2 3
3 4
1 3
1 4

输出样例：

1

Go 代码

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)

const N = 100010

var n, m int  // n 个点,m 条边
var h [N]int  // n 个链表的链表头
var e [N]int  // 每个节点的值-存储所有的边
var ne [N]int // 每个节点的 next 指针
var idx int
var q [N]int // 队列
var d [N]int // 距离

func main() {
//  file, _ := os.Open("./1.txt")
//  defer file.Close()
//  new(file)
    new(os.Stdin)

    tmp := readLine()
    n, m = tmp[0], tmp[1] // n 个点,m 条边
    for i := 0; i < N; i++ {
        h[i] = -1 // 链表初始化，头节点指向 -1
        d[i] = -1 // 初始化距离，-1 表示没有被遍历过
    }

    for i := 0; i < m; i++ { // 读入所有边
        x := readLine()
        add(x[0], x[1]) // 插入每条边，有向图
    }
    fmt.Println(bfs())
}

// 插入一条 a 指向 b 的边
func add(a, b int) {
    // a 所在的邻接表中插入节点 b
    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    idx++
}
func bfs() int {
    q := []int{1} // 定义队列第一个元素就是起点 1
    d[1] = 0      // 第一个点被遍历过赋值为 0

    for len(q) > 0 { // 队列不空
        t := q[0]                           // 取出队头元素
        q = q[1:]                           // 弹出队头元素
        for i := h[t]; i != -1; i = ne[i] { // 扩展当前这个点
            j := e[i]       // j 表示当前到的点
            if d[j] == -1 { // 如果 j 这个点没有被遍历过
                d[j] = d[t] + 1  // 扩展下 j 这个点，到达 j 点的距离
                q = append(q, j) // j 这个点加入到队列
            }
        }
    }
    return d[n]
}

var scanner *bufio.Scanner

func new(reader io.Reader) {
    scanner = bufio.NewScanner(reader)
    bs := make([]byte, 20000*1024)
    scanner.Buffer(bs, len(bs))
}
func readLine() []int {
    scanner.Scan()
    line := strings.Split(scanner.Text(), " ")
    res := make([]int, len(line))
    for i, l := range line {
        res[i], _ = strconv.Atoi(l)
    }
    return res
}