Lepeze

문제

Little Fran received a wooden frame in the shape of a regular polygon as a gift. As polygon has $nn$ vertices, he also received $\frac{n(n-3)}{2}\backslash frac\{n(n-3)\}\{2\}$ wooden sticks that match each possible diagonal. Vertices of the polygon are labelled with integers from $11$ to $nn$ in counterclockwise order. In the beginning, Fran arranged $n-3n\; -\; 3$ sticks inside the frame in such a way that every stick touches two non-neighboring vertive of the frame, and no two sticks cross each other. In other words, he made a triangulation. As that was not interesting enough for him, he decided to play with this configuration by applying a particular operation that consists of two steps:

1. Remove a stick.
2. Add a new stick in such a way that we obtain a new triangulation.

We characterize the operation with an ordered pair of unordered pairs $((a,b),(c,d))((a,\; b),(c,\; d))$ which signifies that little Fran removed a stick touching vertices $aa$ and $bb$, and added a stick touching vertices $cc$ and $dd$.

Fran loves hand fans so, while doing these operations, he sometimes asks himself: “How many operations is needed to transform this triangulation into a “fan” triangulation in vertex $xx$, and, in how many ways is this achievable?”.

Since he is busy doing operations and having fun, he asks for your help!

“Fan” triangulation in vertex $xx$ is a triangulation where all diagonals have a common endpoint, namely vertex $xx$.

Let the number of needed operations be $mm$. Let $f_1,f_2,\dots ,f_{m}f\_1,\; f\_2,\; \backslash dots\; ,\; f\_m$ be a sequence of operations that, when applied in given order, achieves wanted triangulation, thus representing one way of getting there. Let $s_1,s_2,\dots ,s_{m}s\_1,\; s\_2,\; \backslash dots\; ,\; s\_m$ be another such sequence. Two sequences are distinct if there exists an index $ii$ such that $f_i\mathrm{\ne }{s}_{i}f\_i\; \backslash ne\; s\_i$ .

As the number of such sequences can be huge, little Fran is only interested in its remainder modulo ${10}^9+710^9\; +\; 7$.

입력

In the first line are integers $nn$ and $qq$ (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-3n\; -\; 3$ lines there are integers $x_{i}x\_i$, $y_{i}y\_i$ (1 ≤ x_i , y_i ≤ n), the labels of vertices that the $ii$-th stick touches.

In each of the next $qq$ lines there is the integer $t_{i}t\_i$ (1 ≤ t_i ≤ 2) that represents the type of event.

If $t_i=1t\_i\; =\; 1$, it is followed by $44$ integers $a_{i}a\_i$, $b_{i}b\_i$, $c_{i}c\_i$, $d_{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))((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=2t\_i\; =\; 2$, it is followed by an integer $x_{i}x\_i$ (1 ≤ x_i ≤ n), which means that little Fran is interested in data for the “fan” triangulation at vertex $x_{i}x\_i$ in relation to the current triangulation.

출력

For every event of type $22$, in order they came in input, output two integers, minimal number of operations needed and number of ways to get to the target triangulation using minimal number of operations.

4 3
1 3
2 1
1 1 3 2 4
2 1

0 1
1 1

5 4
1 3
3 5
2 1
2 2
1 1 3 2 5
2 2

1 1
2 1
1 1

9 3
1 5
1 7
2 4
2 5
5 7
7 9
2 1
1 2 5 1 4
2 1

4 12
3 6