Description

Format

Input

Output

输出 q 行，每行一个正整数依次表示每个询问的答案。特别的，若不需要跨过任何一条边即可到达，请输出 0；若不存在合法的曲线，请输出 −1。

Samples

9 12
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
1 2 10
2 3 10
3 6 10
6 9 10
9 8 10
8 7 10
7 4 10
4 1 10
2 5 3
5 8 2
5 6 4
4 5 1
3
1.5 1.5 2.5 2.5
1.5 2.5 2.5 1.5
0.5 0.5 1.5 1.5

2
3
-1

Limitation