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 ≤ 10⁵) buildings, with M (1 ≤ M ≤ 10⁶) walkways running amongst them. The i-th walkway connects buildings A_i and B_i (1 ≤ A_i, B_i ≤ N, A_i ≠ 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 ≤ D ≤ 10⁶) 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 ≤ X_i, Y_i ≤ N, X_i ≠ 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 ≤ O_i ≤ 1000) 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 ≤ Z_i ≤ 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

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, A_i and B_i, for i = 1..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..K

Output

For each test case, output 1 integer, the total number of people escorted out of the compound, modulo 10⁹ + 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 10⁹ + 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)