题目描述
在宇宙一个不为人知的地方,有一个星球,上面有一个国家,只有数学家居住。
在这个国家有 个数学家,有趣的是,每个数学家都住在自己的城市,且城市间无道路相连,因为他们可以在线交流。当然,城市有从 到 的编号。
一位数学家决定用手机发论文,而手机将“不言而喻”自动更正成了“猜谜游戏”。
不久之后,这个国家就发现了猜谜游戏。他们想要见面一起玩,于是这个国家就开始了修路工程。
道路修建会持续 天。对于第 天,若 ,则 和 城市间会修一条路。
由于数学家们忙于建筑工作,请你来确定一对数学家最早什么时候能凑到一起玩。
输入格式
第一行有三个正整数 ,表示城市数量、修路持续天数、询问数量。
接下来 行,每行有两个正整数 ,表示询问 和 两个城市的数学家最早什么时候能在一起玩。
输出格式
输出 行,第 行有一个正整数,表示第 次询问的结果。
样例输入 #1
8 3 3 2 5 3 6 4 8
样例输出 #1
3 1 2
样例输入 #2
25 6 1 20 9
样例输出 #2
4
样例输入 #3
9999 2222 2 1025 2405 3154 8949
样例输出 #3
1980 2160
提示