Byteland is a small country, with cities connected by N-1 bidirectional roads. From each city there is just one way of reaching every other city using the road network, which causes severe traffic jams. For this reason several highways have been built; each highway connects some pair of cities.
By a route we mean a sequence of roads and/or highways. All cities on a route should be distinct. For each pair of cities x,y there exists exactly one route which does not use any highway; we call such a route the main route between x and y .
People going from a city x to a city y can either choose the main route or use some highway. In the latter case the route cannot intersect the main route except for the cities x and y and must contain exactly one highway.
Your task is to calculate the number of routes people can take between given pairs of cities.
给一棵n个点的树以及m条额外的双向边
q次询问，统计满足以下条件的u到v的路径：
恰经过一条额外的边
不经过树上u到v的路径上的边
