测试数据来自 system/1372

作业已超过截止时间，您无法递交本题目。

送礼品

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　城市中有 \(N\) 个居民点，编号 \(1\sim N\)，有 \(M\) 条双向边，第 \(i\) 条道路连接居民点 \(U\) 和 \(V\) ，其长度是 1。其中礼品店位于1号居民点。

　　现在有K份礼品需要送达，其中第i份礼品是居住在居民点 \(X_i\) 的A，它想送一份新年礼物给居住在居民点 \(Y_i\) 的B，但是朋友A必须先到礼品店那里取礼物，然后再送给朋友B。

　　你的任务是计算每份礼品的朋友A至少需要走多远的路程？

【输入格式】

　　第 \(1\) 行：三个整数：\(N,M,K\)。
　　第 \(2..M+1\) 行：每行三个整数：\(U,V\)，描述一条道路的信息。
　　第 \(M+2..M+K+1\) 行：共 \(K\) 行，每行两个整数 \(X_i\) 和 \(Y_i\)，表示一份礼品住在 \(X_i\) 居民点的A送礼物给住在 \(Y_i\) 居民点的B。

【输出格式】

　　共 \(K\) 行，每行一个整数输出两个整数：分别是最短路程。

【输入输出样例】

　Input

6 7 3
1 2
5 4
3 1
6 1
3 4
1 4
3 2
2 4
5 6
3 6

　Output

2
3
2

【数据限制】

　　\(100\%\) 的数据满足，\(1≤K≤25000\)，\(2*K≤N≤50000\)，\(N-1≤M≤100000\)。

【来源】

　　Mr.he