这些城市是根据人口数量的升序排列的，依次编号为 0 到 N-1 。每条道路连接两个不同的城市，并且可以双向通行。由这些道路，你能从任意一个城市到另外任意一个城市。
你是一个狼人。你有两种形态：人形和狼形。在每个行程开始的时候，你是人形。在每个行程结束的时候，你必须是狼形。在行程中，你必须要变身（从人形变成狼形）恰好一次，而且只能在某个城市内（包括可能是在 S_i 或 E_i 内）变身。
你的任务是，对每一次行程，判定是否有可能在满足上述限制的前提下，由城市 S_i 走到城市 E_i 。你的路线可以有任意长度。
注意， M 和 Q 是数组的长度，它们的值可以按照“注意事项”中的相关说明而取得。
而对于行程 1 及 2 ，你不可能完成在指定城市间的行程。
在压缩附件包中的文件 sample-01-in.txt 和 sample-01-out.txt 对应于本例。这个包中还包含 另外一对输入/输出样例文件。
你可以通过道路由任意一个城市去另外任意一个城市。
（34 分） M=N-1 且每个城市最多与两条路相连（所有城市是以一条直线的形式连起来）
评测程序示例将按照以下格式读入输入数据:
评测程序示例将以如下格式把 check_validity 的返回值打印出来: