给一张 $n\,(3\le n\le 10^5)$ 个点 $m\,(2\le m\le 2\times 10^5)$ 条边的无向连通图，以及三个正整数 $a,b,c$，保证 $a+b+c=n$。你需要对每个点染成三种颜色中的一种，使得这三种颜色的点的个数分别为 $a,b,c$，且有两种颜色的点构成两个联、连通块。可能无解。

有一张 $n$ 个点 $m$ 条边的无向图，第 $i$ 条边开通的条件是你已经走过了 $d_i$ 条边，问 $1\to n$ 至少需要走多少条边，或输出无解。$n\le m\le 150,\,0\le d_i\le 10^9$。

题目大意

给定一张无向图，要求把边染成黑白两色，要求所有白色边构成的子图没有环，且所有黑色边构成的子图没有环。

多组询问，输出是否有解。

$n\le 500,m\le 2n,T\le 10$。

听说zkw线段树优化dijkstra跑得很快呢，洛谷最优解都是用这个的。

然后我就自己打了一发。

确实快了许多，但还是被最优解吊着打……

但至少能过bzoj3040。