To begin with, we'll make node ~1~ the root of the tree. For node ~u~ that is not a root, let ~p(u)~ denote its parent. Instead of directing the edges, let's imagine we're colouring them in two colours so that one colour denotes that the edge is directed from the child to the parent, and the other from the parent to the child. Let's observe two nodes ~a~ and ~b~. Let node ~c~ be their lowest common ancestor (LCA). Notice that there is a path from ~a~ to ~b~ or from ~b~ to ~a~ if and only if the following three conditions are met:

• All edges on the path from ~a~ to ~c~ are of the same colour
• All edges on the path from ~b~ to ~c~ are of the same colour
• If ~c~ is different from ~a~ and ~b~, then edges ~(a, p(a))~ and ~(b, p(b))~ are of different colours

Let's now construct a graph where the nodes denote the edges of the given tree in the following way. For each given pair ~(a_i, b_i)~ with LCA ~c_i~, we will add the following edges to the graph:

• The nodes that represent the adjacent edges on the path from ~a_i~ to ~c_i~ will be connected with a blue edge
• The nodes that represent the adjacent edges on the path from ~b_i~ to ~c_i~ will be connected with a blue edge
• If ~c_i~ is different from ~a_i~ and ~b_i~, the nodes that represent edges ~(a_i, p(a_i))~, ~(b_i, p(b_i))~ will be connected with a red edge

Now we want to know the number of possible ways to colour the nodes of this graph in two colours so that the nodes connected with a blue edge are of the same colour, and the ones connected with a red edge are of different colours. We can see that the connected components of the graph are mutually independent, so the solution is equal to the product of solutions by individual components. Furthermore, we can see that the colour of a node uniquely identifies the colours of all the other nodes in its component. Additionally, if we have a valid colouring scheme, it stays valid if we change the colour of all the nodes. This means that each component has ~0~ or ~2~ valid colouring schemes, i.e. we only need to determine whether such a colouring scheme exists. We can do this with a DFS algorithm, starting from an arbitrary node and spread recursively, changing the colour when we reach a red edge and taking care of possible colouring contradictions. If there are no contradictions in any of the components, the final solution will be ~2^k~, where ~k~ is the number of components, otherwise it is ~0~.

Now we are only left with constructing the aforementioned graph. A naive construction is of the complexity ~\mathcal O(MN)~ and wasn't fast enough for all the points. Notice that for each node ~x~ of the tree, except the root and its children, we need to determine whether the nodes that represent edges ~(x, p(x))~ and ~(p(x), p(p(x)))~ are connected with a blue edge. We can do this by using a recursive function ~connect(x)~ that returns the minimal depth of a node such that we have added blue edges on the path from that node to a node in the subtree of ~x~. If the value of ~connect(x)~ is smaller than the depth of ~p(x)~, then we add the blue edge, otherwise we don't. The value of ~connect(x)~ is calculated by taking into account its values for the children of ~x~ and also ~high[x]~ - the minimal depth of a node such that we have added blue edges on the path from that node to ~x~. We can get these values by, for each given pair ~(a_i, b_i)~ with LCA ~c_i~, we update the values ~high[a_i]~ and ~high[b_i]~ with the depth of node ~c_i~ if it is smaller than the values ~high[a_i]~, or ~high[b_i]~, so far.

The total time complexity of this solution is ~\mathcal O((M+N) \log N)~, and memory ~\mathcal O(N \log N + M)~.