题目描述

给你一张 $n$ 个点 $m$ 条边的简单无向图，点的编号为 1 到 $n$，每条边的长度要不是 0 要不是 1。

现在有 $k$ 组询问，每组询问我们想知道两个点 $u,v$ 的距离。

输入格式

第一行三个整数 $n,m,k$ 分别表示图的点数、边数和询问数。

接下来 $m$ 行，每行三个整数 $x,y,z$，表示 $x$ 号点和 $y$ 号点之间有一条长度为 $z$ 的边。

接下来 $k$ 行，每行两个整数 $u,v$ 表示一组询问。

输出格式

输出共 $k$ 行，对于每一组询问，输出一行一个数表示两个点的距离，如果两个点不连通，输出 -1。

4 4 1
1 2 0
1 3 1
2 4 1
3 4 1
1 4

1

数据规模

对于所有数据，保证 $2≤n≤20000,0≤m≤100000,1≤k≤10,1≤x,y,u,v≤n,x≠y,0≤z≤1$。