31680번 - Lepeze 서브태스크다국어

문제

Little Fran received a wooden frame in the shape of a regular polygon as a gift. As polygon has $n$ vertices, he also received $\frac{n(n-3)}{2}$ wooden sticks that match each possible diagonal. Vertices of the polygon are labelled with integers from 1ドル$ to $n$ in counterclockwise order. In the beginning, Fran arranged $n - 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))$ which signifies that little Fran removed a stick touching vertices $a$ and $b,ドル and added a stick touching vertices $c$ and $d$.

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 $x,ドル 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 $x$ is a triangulation where all diagonals have a common endpoint, namely vertex $x$.

Let the number of needed operations be $m$. Let $f_1, f_2, \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$ be another such sequence. Two sequences are distinct if there exists an index $i$ such that $f_i \ne s_i$ .

As the number of such sequences can be huge, little Fran is only interested in its remainder modulo 10ドル^9 + 7$.

입력

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.

출력

For every event of type 2ドル,ドル 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.

제한

서브태스크

힌트