题目描述

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

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

输入格式

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

接下来 $m$ 行，每行两个整数 $x,y$，表示 $x$ 号点和 $y$ 号点之间有一条边。

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

输出格式

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

3 2 2
1 2
2 3
1 2
1 3

1
2

数据规模

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