HolyK is the president of Chronomia Land. Chronomia Land consists of $$$n$$$ cities, labeled by the integers from $$$1$$$ to $$$n$$$. There are $$$n-1$$$ roads, where the $$$i$$$-th road connects cities $$$u_i$$$ and $$$v_i$$$. It is guaranteed that for any two cities, there is a path connecting them. In other words, Chronomia Land can be treated as a tree with $$$n$$$ vertices.

The distance between two cities $$$x$$$ and $$$y$$$, denoted by $$$\operatorname{dis}(x, y)$$$, is defined as the number of edges in the shortest path connecting these two cities. Specifically, we have $$$\operatorname{dis}(x, x) = 0$$$, as an empty path will meet the requirement.

As the anniversary of Chronomia Land draws near, HolyK is planning to show movies in selected cities to commemorate this special occasion. For the residents of city $$$x$$$, they can travel to city $$$y$$$ to see a movie if and only if city $$$y$$$ is showing movies, and $$$\operatorname{dis}(x, y) \leq 1$$$.

There are $$$m$$$ options for showing movies. The $$$i$$$-th option denotes that movies will be shown in the cities on the shortest path between $$$x_i$$$ and $$$y_i$$$.

Now HolyK wishes to make plans to show movies, and he wants more residents to be able to see movies. Therefore, more than one option can be enabled. He has a total of $$$q$$$ questions, and for the $$$i$$$-th question, he wants to know how many cities will be able to see the movie if all of the options numbered between $$$l_i$$$ and $$$r_i$$$ (inclusive) are enabled.

Handling all the tasks in Chronomia Land has made HolyK so tired that he no longer has the strength to answer these questions. Please help HolyK by answering all these questions.