In the first line are integers n and q (4 ≤ n ≤ 2 \cdot 10^5, 1 ≤ q ≤ 2 \cdot 10^5), the number of vertices and the number of events.

In each of the next n - 3 lines there are integers x_i, y_i (1 ≤ x_i , y_i ≤ n), the labels of vertices that the i-th stick touches.

In each of the next q lines there is the integer t_i (1 ≤ t_i ≤ 2) that represents the type of event.

If t_i = 1, it is followed by 4 integers a_i, b_i, c_i, d_i (1 ≤ a_i , b_i , c_i , d_i ≤ n) that signify an operation ((a_i , b_i),(c_i , d_i)) is being made at that moment. It is guaranteed that given operation can be realized.

If t_i = 2, it is followed by an integer x_i (1 ≤ x_i ≤ n), which means that little Fran is interested in data for the “fan” triangulation at vertex x_i in relation to the current triangulation.

#7073 upload - done - how_to_reg - call_split Subtask

Lepeze timer 2s memory 1024MB

#7073
Subtask

Lepeze 2s 1024MB