The first line of the input contains two positive integers n
, m ≤
50,000) indicating the number of villages and events. Each of the next m
lines describes an event.There are three different events described in different format shown below:
- D x: The x-th village was destroyed.
- Q x: The Army commands requested the number of villages that x-th village was directly or indirectly connected with including itself.
- R: The village destroyed last was rebuilt.