Background

Translated from COCI 2023/2024 Contest #4 T3 “Lepeze”.

Problem Description

Little Fran received a gift — a regular polygon wooden frame. Since the polygon has $n$ vertices, he also received $\frac{n(n-3)}{2}$ wooden sticks, one for each diagonal. The vertices of the polygon are labeled from $1$ to $n$ in counterclockwise order. At the beginning, Fran places $n-3$ sticks inside the frame so that each stick touches two non-adjacent vertices of the frame, and no two sticks intersect. In other words, he makes a triangulation. Since this is not interesting enough for him, he decided to perform a specific operation to change the placement, consisting of two steps:

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

We describe this operation by an ordered pair of unordered pairs $((a, b),(c, d))$, meaning that Fran removed the stick touching vertices $a$ and $b$, and added the stick touching vertices $c$ and $d$.

Fran likes fans, so while performing these operations, he sometimes asks himself: “How many operations are needed to transform this triangulation into a ‘fan’ triangulation centered at vertex $x$, and in how many ways can it be done?”

Since he is busy operating and having fun, he asks for your help.

A “fan” triangulation centered at vertex $x$ is a triangulation in which all diagonals share a common endpoint, namely vertex $x$.

Let the required number of operations be $m$. Let $f_1,f_2,\ldots,f_m$ be a sequence of operations such that performing them in this order results in a triangulation that satisfies the requirement. 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$, then the two sequences are different.

Since the number of such sequences can be very large, Fran only cares about its 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)$, denoting the number of vertices and the number of events.

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

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

If $t_i=1$, then four more integers $a_i,b_i,c_i,d_i$ $(1\le a_i,b_i,c_i,d_i\le n)$ follow, describing one operation $((a_i,b_i),(c_i,d_i))$. It is guaranteed that the given operation is feasible.

If $t_i=2$, then one integer $x_i$ $(1\le x_i\le n)$ follows, meaning that Fran is interested in the data for the “fan” triangulation centered at vertex $x_i$ in the current state.

Output Format

For each event of type $2$, in the order they appear in the input, output two integers: the minimum number of operations required, and the number of ways to reach the target triangulation using the minimum 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

Hint

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 do it. After performing the given operation, there is only one way to restore it to the previous state, namely 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,4))$.

Subtasks

Translated by ChatGPT 5