U477750 地图

我们认为一个无自环连通图有 $n$ 条有向边和 $m$ 条无向边组成称之为地图。

已知有 $n$ 个点 $m$ 条边的地图，规定 $0$ 表示有向边， $1$ 表示无向边。给予 $q$ 次询问，求问从顶点 $x$ 到 $y$ 的最短路径。

共 $1+n+m+q$ 。 第 $1$ 行，输入 $n，m，q$ 。 接下来 $m$ 行，输入 $u，v$，以及判断是否为有无向边，规定 $0$ 表示有向边， $1$ 表示无向边。 接下来 $q$ 行，输入顶点 $x,y$ ，求问从顶点 $x$ 到 $y$ 的最短路径。

输出 $q$ 行，表示从顶点 $x$ 到 $y$ 的最短路径。

对于样例：  如图所示。 对于 $100\%$ 的数据，保证 $0 \leqslant n \leqslant 300， 0 \leqslant m \leqslant 3000 ，0 \leqslant q \leqslant 500 $ 。