本题改编自 IOI 2018 狼人，要求输出可达路径的方案数，而非仅仅判断可行性。
原题见 Luogu P4899。本题为完整程序题，请提交完整代码。
在日本的茨城县内共有 个城市和 条道路。这些城市是根据人口数量的升序排列的，依次编号为 到 。每条道路连接两个不同的城市，并且可以双向通行。由这些道路，你能从任意一个城市到另外任意一个城市。
你计划了 个行程，分别编号为 至 。第 个行程是从城市 到城市 。
你是一个狼人。你有两种形态：人形和狼形。在每个行程开始的时候，你是人形。在每个行程结束的时候，你必须是狼形。在行程中，你必须要变身（从人形变成狼形）恰好一次，而且只能在某个城市内（包括可能是在 或 内）变身。
狼人的生活并不容易。当你是人形时，你必须避开人少的城市，而当你是狼形时，你必须避开人多的城市。对于每一次行程 ，都有两个阈值 和 ，用以表示哪些城市必须要避开。准确地说，当你是人形时，你必须避开城市 ；而当你是狼形时，则必须避开城市 。这就是说，在行程 中，你必须在城市 中的其中一个城市内变身。
你的任务是，对每一次行程，计算在满足上述限制的前提下，有多少个不同的城市可以作为变身点，使得从 到 的路径存在。如果不存在任何可行路径，则回答 。
注意：变身点必须位于闭区间 内，且存在一条从 到该点的路径（仅经过 的点）和一条从该点到 的路径（仅经过 的点）。路径可以有任意长度。
