Description

1967年，美国著名社会心理学家米尔格伦（Stanley Milgram ）通过一系列连锁信件实验验证了“六度分隔”理论（Six Degrees of Separation），简单来说就是：你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人，你就能够认识任何一个陌生人，朋友关系构成了人与人之间相互联系的纽带。“六度分隔”理论一经提出，就受到全球学术界的广泛关注，它也是社交网络服务（SNS）的基础理论之一。
　　请使用合理的数据结构和算法编写程序，验证“六度分隔”理论，要求必须能处理超过1000万对以上的朋友关系对。具体是找出指定的两个用户的分割度（如果两个用户是朋友关系则分隔度为1，如果两个用户不可达则分隔度为-1）。

Input

第一个为朋友关系对n(1<=n<=300000)。一行数据由两个用户编号组成，用制表符(\t)分隔，表示这两个用户是朋友关系。第二输入查询,数百行左右，一行数据由两个用户编号组成，用制表符(\t)分隔。

Output

每行输出一个查询结果，格式为：用户1编号 用户2编号 两者的分隔度（用制表符分隔）。

Sample Input

7
1001	1003
1100	1001
1003	1105
1001	1208
1230	1001
1005	1208
1300	1301
4
1001	1005
1005	1230
1003	1208
1001	1301

Sample Output

1001	1005	2
1005	1230	3
1003	1208	2
1001	1301	-1

HINT

Source

NBU OJ