Problem Description

Little Fran received a gift—a wooden frame in the shape of a regular polygon. Since the polygon has $n$ vertices, he also received $\frac{n(n-3)}{2}$ sticks that match each diagonal. The vertices of the polygon are labeled from $1$ to $n$ in counterclockwise order. Initially, Fran places $n-3$ sticks inside the frame such that each stick touches two non-adjacent vertices of the frame and no two sticks intersect. In other words, he creates a triangulation. Finding this not interesting enough, he decides to perform a specific operation to change this arrangement, which consists of two steps:

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

This operation is described by an ordered pair of unordered pairs $((a, b),(c, d))$, indicating that Fran removes the stick touching vertices $a$ and $b$ and adds a stick touching vertices $c$ and $d$.

Fran likes fans, so while performing these operations, he sometimes asks himself, "How many operations are needed to convert this triangulation into a 'fan' triangulation centered at vertex $x$, and in how many ways can this be achieved?"

A 'fan' triangulation centered at vertex $x$ is a triangulation where all diagonals have a common endpoint, which is vertex $x$.

Let the number of required operations be $m$. Let $f_1, f_2, \ldots, f_m$ be an operation sequence that, when performed in this order, achieves the desired triangulation. Let $s_1, s_2, \ldots, s_m$ be another such sequence. If there exists an index $i$ such that $f_i \neq s_i$, the two sequences are considered different.

Since the number of such sequences can be very large, Fran is only interested in the value modulo $10^9 + 7$.

Input Format

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

The next $n-3$ lines each contain two integers $x_i, y_i\ (1 \le x_i, y_i \le n)$, indicating the two vertices touched by the $i$-th stick.

The next $q$ lines each describe an event. The first integer is $t_i\ (1 \le t_i \le 2)$, indicating the type of event.

If $t_i = 1$, then there are four more integers $a_i, b_i, c_i, d_i\ (1 \le a_i, b_i, c_i, d_i \le n)$, representing an operation $((a_i, b_i),(c_i, d_i))$. It is guaranteed that the given operation can be performed.

If $t_i = 2$, then there is one more integer $x_i\ (1 \le x_i \le n)$, indicating that Fran is interested in the data related to the 'fan' triangulation at vertex $x_i$.

Output Format

For each event of type $2$, output two integers in the order they appear in the input: the minimum number of operations required and the number of ways to achieve the target triangulation using the minimum number of operations.

Sample Input and Output

Input Sample #1

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

Output Sample #1

0 1
1 1

Input Sample #2

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

Output Sample #2

1 1
2 1
1 1

Input Sample #3

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

Output Sample #3

4 12
3 6

Notes/Hints

Sample Explanation 1

The initial triangulation is already a 'fan' triangulation centered at vertex $1$, so Fran does not need to perform any operations, and there is one way to achieve this. After performing the given operation, there is only one way to restore it to the previous state, which is by performing the operation $((2, 4),(1, 3))$.

Sample Explanation 2

The first query corresponds to the unique operation sequence: $((3, 5),(1, 4))$.

The second query corresponds to the unique operation sequence: $((1, 3),(2, 5)),((3, 5),(2, 4))$.

The third query corresponds to the unique operation sequence: $((3, 5),(2, 5))$.

Subtasks

见题面 Input 部分

见题面 Output 部分