有$n$个城市，每个城市有两个传送点，第$i$个城市的传送点能让你传送到$a_i, b_i$这两个城市。

你想知道，从每个城市到达另一个城市，最少需要传送多少次？你需要回答$q$次询问。

输入格式

第一行，一个整数$n, q$。

接下来$n$行，每行两个整数$a_i, b_i$。

接下来$q$行，每行两个整数$u, v$，表示你要回答从$u$点到达$v$点需要传送多少次。

输出格式

输出$q$行，表示答案。如果不可到达，输出-1。

样例输入

5 5
5 4
5 4
3 1
1 5
3 1
3 5
3 1
1 2
1 1
5 4

样例输出

2
1
-1
0
2

数据规模

对于所有数据，保证$1\leq n\leq 10^3, 1\leq a_i, b_i \leq n, 1\leq q\leq 10^5$。