Roots of a Tree

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
You are given a tree with N nodes, numbered from 1 to N. You need to handle the queiries of the following two types:
 + x y. Add a path going from the node x to the node y (or from y to x because it's actually irrelevant). We will never add the path that is already a present one.
  x y. Delete the path going from the node x to the node y. It is guaranteed that such path exists and after its last adding it haven't yet been deleted.
If we root the tree at the node t and for every present (added and not yet deleted) path, the least common ancestor of its endpoints is also one of the endpoints of this path, then we call the node t a possible root.
We ask you to output the product of all the possible roots' indexes after every query.
Input
The first line of input contains two single space separated integers N and M  the number of nodes in the tree and the number of queries respectively.
The following N1 lines contain pairs of integers denoting the edges of a tree. The pair X Y corresponds to the edge between the nodes X and Y.
Then there are M lines denoting the queries in the form described above.
Output
Output M lines. Output the product of all the possible roots' numbers modulo 10^{9}+7 after the performing of the ith query on the ith line. If there are no possible roots, output 1 on this line instead.
Constraints
 1 ≤ X, Y ≤ N
 1 ≤ x, y ≤ N
 1 ≤ N, M ≤ 100  42 points.
 1 ≤ N, M ≤ 10^{5}  58 points.
Example
Input: 5 4 1 2 2 3 3 4 4 5 + 1 3 + 3 5  1 3  3 5 Output: 60 15 30 120
Author:  xcwgf666 
Tester:  stzgd 
Editorial  http://discuss.codechef.com/problems/TROOT 
Tags  dfs, easymedium, ltime12, segmenttree, xcwgf666 
Date Added:  30042014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 