The world is an undirected connected graph of vertices and edges, and each edge is in at most one simple ring. So as well known, the graph can be described as a cactus.

There are graduating stutents in the world this time. For the -th student, his/her college, dream, and life are at vertex , , respectively. And for each student, he/she should go from his college vertex to life vertex as he/she is graduated. However, no one wants to abandon the dreams easily, so for the -th student, he/she wants to find a vertex that is possibly in the shortest path between and (there is at least one path that contains , that is from to and that has minimum possible number of edges), and possibly in the shortest path between and . If multiple valid vertices, choose the one with the maximum distance(the number of edges in the shortest path) to , if still multiple valid vertices, choose the one with the minimum index.

The first line contains three integers , denoting the number of vertices, the number of edges and the number of graduating students respectively.

Following m lines each contains two integers , denoting the edges in the graph.

Following q lines each contains three integers , denoting each student's college vertex, dream vertex and life vertex respectively.

It's guaranteed that no self-loops or multiple edges exist in the given graph and that the given graph forms a cactus.

Print q lines each containing two integers , denoting the chosen vertex and the distance between it and  respectively.

8 10 2
1 2
1 3
2 3
3 4
4 5
5 6
3 6
5 7
5 8
7 8
1 4 5
8 1 2

4 2
3 3

The graph looks like:

* For the first student, vertices  are valid choices and we choose  as the answer.
* For the second student, vertices  are valid choices and we choose  as the answer.