Facebook Hacker Cup 2014 Finals

Facebook Headquarters - a mysterious, intimidating place, full of magical code and trade secrets. If outsiders were ever to breach the walls of the compound, which are protected by a legion of security guards and, more importantly, security foxes, the entire company could well be brought to its knees!

Actually, wait, tours of the place are given regularly…

The compound consists of ~N~ ~(1 \le N \le 10^5)~ buildings, with ~M~ ~(1 \le M \le 10^6)~ walkways running amongst them. The ~i~-th walkway connects buildings ~A_i~ and ~B_i~ ~(1 \le A_i, B_i \le N, A_i \ne B_i)~, and no two buildings are directly connected by more than one walkway. There are no other ways to move from building to building.

Over a period of ~D~ ~(1 \le D \le 10^6)~ days, some events will occur at the Headquarters daily. One of two types of events will happen on the ~i~-th day, indicated by the value of the character ~E_i~. If ~E_i =~ T then a tour will take place — otherwise, ~E_i =~ S, and a security sweep of a building will take place.

If a tour is given on the ~i~-th day, visitors will enter the compound at building ~X_i~, and leave from building ~Y_i~ ~(1 \le X_i, Y_i \le N, X_i \ne Y_i)~. If it turns out that these two buildings are not actually connected by any sequence of walkways, then the tour will be cancelled, and the unfortunate visitors will be given Facebook T-shirts and promptly kicked out. Otherwise, a large number of groups of people will be led from building ~X_i~ to building ~Y_i~ along various routes. No route will involve travelling along the same walkway multiple times (even in different directions), but a route might revisit the same building repeatedly, including buildings ~X_i~ and ~Y_i~. Along the way, some visitors will inevitably get "lost", and fail to rejoin their tour group. How many of them will get away with this will depend on the security levels that day, but it's safe to say that, in total, ~O_i~ ~(1 \le O_i \le 1\,000)~ new outsiders will be left behind in each building which could possibly be part of any valid tour route from building ~X_i~ to building ~Y_i~. Good thing they'll no doubt have brought cameras to amuse themselves with while they wait to be found.

On the other hand, if a security sweep is conducted on the ~i~-th day, then the security guards (and foxes) will carefully search building ~Z_i~ ~(1 \le Z_i \le N)~ for any trespassers remaining from previous tours, who will be kindly escorted out of the Headquarters (after being given Facebook T-shirts for the road, of course).

Because this company likes to collect data about everything, you've been hired to record how many outsiders were found in each sweep. However, to make things more interesting, you'll instead simply write a program to predict these values based on the map of the compound and the schedule of events!

Input Specification

Line ~1~: ~1~ integer, ~T~ ~(1 \le T \le 20)~, the number of test cases.

For each test case:
Line ~1~: ~3~ integers, ~N~, ~M~, and ~D~.
Next ~M~ lines: ~2~ integers, ~A_i~ and ~B_i~, for ~i = 1 \dots M~.
Next ~D~ lines: ~1~ character, ~E_i~, followed by the three integers ~X_i~, ~Y_i~, and ~O_i~ if ~E_i =~ T, or the single integer ~Z_i~ if ~E_i =~ S, for ~i = 1 \dots K~.

Output Specification

For each test case, output ~1~ integer, the total number of people escorted out of the compound, modulo ~10^9 + 7~.

Sample Input

1
6 5 9
1 2
2 3
3 4
4 5
5 3
T 1 2 5
T 5 6 1000
S 2
S 6
T 2 3 1
T 5 3 14
S 1
S 2
S 4

Sample Output

26

Explanation of Sample

On the first day, a tour is given from building ~1~ to building ~2~. The only valid route consists of simply crossing the walkway between these two buildings. As such, by the end of the day, ~5~ outsiders are left hiding in each of buildings ~1~ and ~2~.

On the second day, the planned low-security tour unfortunately cannot take place, due to no routes existing between buildings ~5~ and ~6~. Facebook should probably hire some new tour planners, as well as architects.

On the following two days, security sweeps of buildings ~2~ and ~6~ are carried out, with ~5~ and ~0~ outsiders found and removed, respectively.

On the fifth day, a tour is given from building ~2~ to building ~3~. There are exactly three valid routes, passing through buildings ~2 \to 3~, ~2 \to 3 \to 4 \to 5 \to 3~, and ~2 \to 3 \to 5 \to 4 \to 3~. As such, one new outsider remains behind in each of buildings ~2~, ~3~, ~4~, and ~5~.

On the sixth day, a tour is given from building ~5~ to building ~3~. There are exactly two valid routes, passing through buildings ~5 \to 3~ and ~5 \to 4 \to 3~. As such, ~14~ new outsiders take up residence in each of buildings ~3~, ~4~, and ~5~.

Finally, security sweeps of buildings ~1~, ~2~, and ~4~ are conducted, evicting ~5~, ~1~, and ~15~ people, respectively. In total, then, ~5 + 0 + 5 + 1 + 15 = 26~ people will have been escorted out of the compound, which is still ~26~ when taken modulo ~10^9 + 7~. Following these events, buildings ~3~ and ~5~ still contain ~15~ outsiders, while the others contain none.