Facebook Hacker Cup 2014 Finals

Tours

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 ≤ N ≤ 105) buildings, with M (1 ≤ M ≤ 106) walkways running amongst them. The i-th walkway connects buildings Ai and Bi (1 ≤ Ai, BiN, AiBi), 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 ≤ D ≤ 106) 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 Ei. If Ei = "T" then a tour will take place – otherwise, Ei = "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 Xi, and leave from building Yi (1 ≤ Xi, YiN, XiYi). 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 Xi to building Yi 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 Xi and Yi. 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, Oi (1 ≤ Oi ≤ 1000) new outsiders will be left behind in each building which could possibly be part of any valid tour route from building Xi to building Yi. 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 Zi (1 ≤ ZiN) 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

Line 1: 1 integer, T (1 ≤ T ≤ 20), the number of test cases

For each test case:
Line 1: 3 integers, N, M, and D
Next M lines: 2 integers, Ai and Bi, for i = 1..M
Next D lines: 1 character, Ei, followed by the three integers Xi, Yi, and Oi if Ei = "T", or the single integer Zi if Ei = "S", for i = 1..K

Output

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

Sample Input

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-3, 2-3-4-5-3, and 2-3-5-4-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-3 and 5-4-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 109 + 7. Following these events, buildings 3 and 5 still contain 15 outsiders, while the others contain none.

All Submissions
Best Solutions


Point Value: 50
Time Limit: 10.00s
Memory Limit: 64M
Added: Jul 08, 2014
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...