King Graff, the ruler of the land of Feerie, feels that he is not quite rich enough. As such, he would like to impose travel tolls on his people! After all, why should they get to walk around his kingdom for free?
Feerie consists of towns (numbered ), and roads. The -th road runs between distinct towns and , in both directions. Every pair of towns is connected by exactly one path of connected roads. Currently, all travel is free, but King Graff is interested in charging for passage through certain towns.
He is planning to have a meeting with the royal computer scientist -
that would be you. The meeting will last
minutes, and in the -th minute, one of two things will occur,
described by . If T
, Graff will proclaim that town
shall henceforth cost dollars
to pass through, and you'll update the map accordingly. Otherwise, if
Q
, he will ask you how much a trip from town to a
different town would currently cost a commoner, in order to
gauge the effectiveness of his tolls - and you had better answer
quickly! Note that neither the starting nor the ending town's tolls are
included in a trip's cost, as they are not passed through. Note also
that a town's toll may be modified by Graff multiple times throughout
the meeting, in which case the most recent modification at any point
will stand.
Input Specification
Line 1: 1 integer,
Next lines: 2 integers, and , for
Next line: 1 integer,
Next lines: 1 character, , and 2 integers, and
, for
Output Specification
lines (where is the number of questions asked by King Graff): 1 integer, the cost of the -th trip asked for (in dollars), for
Sample Input
4
1 3
2 3
4 3
6
Q 1 4
T 3 5
Q 4 2
Q 3 1
T 3 1
Q 1 2
Sample Output
0
5
0
1
Explanation of Sample
The map of Feerie is illustrated below:
The first trip asked for by King Graff goes through towns .
Since town 3 has no toll at that point, the trip's cost is 0.
The second trip goes through towns and has a cost of 5, due to
the new toll on town 3.
The third trip goes through towns , passing through no towns and so
costing nothing.
The final trip goes through towns and costs only 1, as town
3's toll is reduced by then.
Comments