Statement

William is training for the marathon! Some running skills are always useful… who knows who may chase you in the future. William trains in the park near his newly found home, which is a connected graph composed by N intersections (numbered from 1 to N) and N-1 roads connecting two intersections each. Due to bad weather, some roads may be temporarily closed. William, however, has consulted the weather forecast and knows exactly which roads will be closed at any given moment. At the very beginning of his training, every road is open. Before training, William has prepared a timeline consisting of Q events of two types: (1) type 1: if the road from intersection x to intersection y is closed it will be reopened, if the road is open it will be closed; (2) type 2: William will train by running the path from the intersection x to the intersection y...