从 \(1\) 出发染色不好处理，考虑从 \(n\) 出发进行染色，尽可能让每一条路不可经过，这样也是最大化其他点到 \(n\) 的最短路。
如果当前为 \(u\)，点 \(v\) 和 \(u\) 有边，如果只有一种颜色的边，那么这条路是可以禁止经过的，将 \(v\) 设置成与边不同的颜色。如果有不同颜色的边，那么 \(v\) 的颜色无论怎么染色都以到达 \(u\)。
从 \(n\) 开始进行反向 BFS 。
当第一遍历到未染色的点 \(x\)，将点 \(x\) 设为与边不同的颜色。如果遍历到染色的点，并且染色的点与边颜色相同，说明此点无法避开，加入到队列中，更新到 \(n\) 的最短路，直到 \(1\) 入队。
时间复杂度为 \(\mathcal{O}(n + m)\)。
代码不放。