The squirrel nation is building a road network to transport acorns between their cities. They are scattered among
Over time,
- A squirrel will build more roads to connect some of their cities. Of course, the squirrels, having recently discovered time travel, will sometimes go back in time and build the roads a different way. Specifically, the
squirrel will decide to time travel to the same timeline as another squirrel , where , and build a new road in that timeline between cities and . - A squirrel will time travel back to the same timeline as another squirrel
, where , start in a specific city , and eat all the acorns in the city with the largest number of acorns that is reachable from city (including city ). If there are multiple cities with the largest number of acorns, then the squirrel will pick one arbitrarily. - A squirrel will time travel back to the same timeline as another squirrel
, where , start in a specific city , and add acorns to each city reachable from city (including city ).
Note that each squirrel creates a new timeline, so future actions cannot affect past actions. When a squirrel
You are asked to record the number of acorns eaten after each type
Constraints
For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.
For all subtasks:
Subtask 1 [13%]
Subtask 2 [14%]
There will be no actions of type
Subtask 3 [20%]
Subtask 4 [20%]
There will be no actions of type
Subtask 5 [33%]
No additional constraints.
Input Specification
The first line of input contains
The next line contains
The next
The
1 j_i' a_i' b_i'
indicating that squirrel performs a type action by time traveling back to the same timeline as squirrel , creating a new timeline, and building a new road between cities and .2 j_i' a_i'
indicating that squirrel performs a type action by time traveling back to the same timeline as squirrel , creating a new timeline, and eating all acorns from the city with the largest number of acorns that is reachable from city (including city ). If there are multiple cities with the largest number of acorns, the squirrel will pick one arbitrarily.3 j_i' a_i' c_i'
indicating that squirrel performs a type action by time traveling back to the same timeline as squirrel , creating a new timeline, and adding acorns to each city reachable from city (including city ).
For all squirrels, if
Output Specification
This problem is graded with an identical
checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n
character and that there are no trailing spaces.
After each type
Sample Input 1
2 3
1 2
2 0 2
1 3 3 0
2 0 0
Sample Input 1 Decrypted
For your convenience, below is a version of Sample Input 1 that is NOT encrypted. Note that all of the actual test files will be encrypted in the format specified above.
2 3
1 2
2 0 2
1 1 1 2
2 2 2
Sample Output 1
2
1
Sample Explanation 1
Squirrel
Squirrel
Squirrel
Sample Input 2
3 7
1 2 1
1 0 1 2
2 1 2
3 2 1 0
1 1 0 1
2 6 0
2 3 1
2 4 0
Sample Input 2 Decrypted
For your convenience, below is a version of Sample Input 2 that is NOT encrypted. Note that all of the actual test files will be encrypted in the format specified above.
3 7
1 2 1
1 0 1 2
2 1 2
3 0 3 2
1 3 2 3
2 4 2
2 0 2
2 6 2
Sample Output 2
2
3
2
0
Sample Explanation 2
Squirrel
Squirrel
Squirrel
Squirrel
Squirrel
Squirrel
Squirrel
Comments