有$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$。