欧艾大陆上有n 座城市，城市从1-n 编号，所有城市经由n-1 条无向道路互相连通，即n 座城市与n-1 条道路构成了一棵树。
每座城市的集市上都会出售宝石，总共有m 种不同的宝石，用1-m 编号。i 号城市的集市出售的是第w_i 种宝石，一种宝石可能会在多座城市的集市出售。
K 神有一个宝石收集器。这个宝石收集器能按照顺序收集至多c 颗宝石，其收集宝石的顺序为：P_1,P_2,...,P_c。更具体地，收集器需要先放入第P_1 种宝石，然后才能再放入第P_2 种宝石，之后再能放入第P_3 种宝石，以此类推。其中P_1,P_2,...,P_c 互不相等。
K 神到达一个城市后，如果该城市的集市上出售的宝石种类和当前收集器中需要放入的种类相同，则他可以在该城市的集市上购买一颗宝石并放入宝石收集器中；否则他只会路过该城市什么都不做。
现在K 神给了你q 次询问，每次给出起点s_i 与终点t_i，他想知道如果从s_i 号城市出发，沿最短路线走到t_i 号城市后，他的收集器中最多能收集到几个宝石？（在每次询问中，收集器内初始时没有任何宝石。起点与终点城市集市上的宝石可以尝试被收集）
