Lepeze

Little Fran received a wooden frame in the shape of a regular polygon as a gift. The polygon has $n$ vertices, so he also received $\frac{n(n-3)}{2}$ wooden sticks, one for each possible diagonal. The vertices are labelled with integers from 1 to $n$ in counterclockwise order.

At the start, Fran placed $n-3$ sticks inside the frame. Each stick touches two non-neighboring vertices, and no two sticks cross. In other words, the sticks form a triangulation.

Fran likes to change this configuration with an operation made of two steps:

1. Remove a stick.
2. Add a new stick so that the result is a new triangulation.

An operation is written as an ordered pair of unordered pairs $((a, b),(c, d))$, which means Fran removed the stick touching vertices $a$ and $b$ and added a stick touching vertices $c$ and $d$.

Fran sometimes asks how many operations it takes to turn the current triangulation into a fan triangulation at vertex $x$, and how many ways there are to do it. A fan triangulation at vertex $x$ is one in which all diagonals share the common endpoint $x$.

Let $m$ be the minimal number of operations. Let $f_1, f_2, \dots, f_m$ and $s_1, s_2, \dots, s_m$ be two sequences of operations that reach the target in $m$ steps. The sequences are different if $f_i \ne s_i$ for some index $i$. Count these sequences modulo $10^9 + 7$.

The first line contains integers $n$ and $q$ ($4 \le n \le 2 \cdot 10^5$, $1 \le q \le 2 \cdot 10^5$), the number of vertices and the number of events.

Each of the next $n-3$ lines contains integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$), the labels of the vertices touched by the $i$-th stick.

Each of the next $q$ lines starts with an integer $t_i$ ($1 \le t_i \le 2$), the event type. If $t_i = 1$, four integers $a_i, b_i, c_i, d_i$ ($1 \le a_i, b_i, c_i, d_i \le n$) follow, and the operation $((a_i, b_i),(c_i, d_i))$ is performed at that moment. The operation is guaranteed to be valid. If $t_i = 2$, one integer $x_i$ ($1 \le x_i \le n$) follows, and you must report the data for the fan triangulation at vertex $x_i$ for the current triangulation.

For every event of type 2, in input order, print two integers on one line: the minimal number of operations, and the number of ways to reach the target triangulation with that many operations, modulo $10^9 + 7$.