j02036. 朋友圈外传话 未做

班里有 $n$ 名同学，其中有 $m$ 对「死对头」互不传话；其余任意两人都愿意传话。消息从 1 号同学传到 $n$ 号同学，每传一手恰好 1 分钟，可经多人中转。求最少几分钟；若消息永远传不到，输出 -1。（等价于在「除死对头以外的完全图」上求 1 到 $n$ 的最短路。）

第一行两个整数 $n$ $m$；接下来 $m$ 行每行两个整数 $u$ $v$，表示一对死对头（保证 $u$$\ne$$v$，同一对至多出现一次）。

一行一个整数，最少分钟数或 -1。

• 30% 1$\le$$n$$\le$300（直接建补图 $O$($n^2$) 也能过）。
• 60% 1$\le$$n$$\le$3000。
• 100% 1$\le$$n$$\le$$2\times 10^5$，0$\le$$m$$\le$$1.6\times 10^5$，$1\le u,v\le n$。