题目描述

给你一张 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 ≤ ? ≤ 20000 , 0 ≤ ? ≤ 100000 , 1 ≤ ? ≤ 10 , 1 ≤ ? , ? , ? , ? ≤ ? , ? ≠ ? , 0 ≤ ? ≤ 1 2≤n≤20000,0≤m≤100000,1≤k≤10,1≤x,y,u,v≤n,x  =y,0≤z≤1。

最好用链表或双端队列，能做出来就行。

谢谢