题目描述

译自 COCI 2023/2024 Contest #4 T3「Lepeze」

小 Fran 收到了一个礼物——一个正多边形木制框架。由于多边形有 $n$ 个顶点，他还收到了 $\frac{n(n-3)}{2}$ 根与每条对角线相匹配的木棍。多边形的顶点按逆时针顺序标记为 $1$ 到 $n$。一开始，弗兰将 $n-3$ 根木棍放在框架内，以使每根木棍接触框架的两个不相邻顶点，并且没有两根木棍相交。换句话说，他做了一个三角剖分。由于这对他来说不够有趣，他决定进行特定的操作来改变这种放置方法，该操作由两个步骤组成：

1. 移除一根木棍。
2. 添加一根新的木棍，使得我们得到一个新的三角剖分。

我们用一个由无序对组成的有序对 $((a, b),(c, d))$ 来描述这个操作，表示小 Fran 移除了接触顶点 $a$ 和 $b$ 的木棍，并添加了接触顶点 $c$ 和 $d$ 的木棍。

弗兰喜欢扇子，所以在进行这些操作时，他有时会问自己：「将这个三角剖分转换为以顶点 $x$ 为『扇形』三角剖分需要多少次操作，并且有多少种方式可以实现？」

由于他忙于操作和娱乐，他请求你的帮助！

以顶点 $x$ 为中心的「扇形」三角剖分是一种三角剖分，其中所有的对角线都有一个共同的端点，即顶点 $x$。

设所需操作的数量为 $m$。设 $f_1,f_2,\ldots,f_m$ 是一个操作序列，满足按这一顺序操作可以实现满足条件的三角剖分。设 $s_1,s_2,\ldots,s_m$ 是另一种这样的序列。如果存在一个下标 $i$ 使得 $f_i \neq s_i$，则两个序列是不同的。

由于这样的序列数量可能非常大，小 Fran 只关心它对 $10^9 + 7$ 取模后的值。

输入格式

第一行两个整数 $n$ 和 $q$（$4 \le n \le 2 \cdot 10^5$，$1 \le q \le 2 \cdot 10^5$），表示顶点数和事件数。

接下来 $n-3$ 行，每行两个整数 $x_i,y_i$（$1 \le x_i,y_i \le n$），表示第 $i$ 根木棍接触的两个顶点。

接下来 $q$ 行，每行描述一个事件。第一个整数为 $t_i$（$1 \le t_i \le 2$），表示事件类别。

• 如果 $t_i=1$，则接下来还有四个整数 $a_i,b_i,c_i,d_i$（$1 \le a_i,b_i,c_i,d_i \le n$），表示一次 $((a_i,b_i),(c_i,d_i))$ 操作。保证给出的操作可以实现。
• 如果 $t_i=2$，则接下来一个整数 $x_i$（$1 \le x_i \le n$），表示小 Fran 对与目前顶点 $x_i$ 处的「扇形」三角剖分的数据感兴趣。

输出格式

对于每个类型为 $2$ 的事件，按照它们在输入中的顺序，输出两个整数：所需的最小操作数和使用最小操作数达到目标三角剖分的方式数量。

样例 1

输入

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

输出

$0$ $1$ $1$ $1$

说明

起始三角剖分已经是以顶点 $1$ 为中心的「扇形」三角剖分，所以小 Fran 不需要进行任何操作，有一种方式可以实现。在执行给定的操作后，将其恢复到先前状态只有一种方式，即进行操作 $((2, 4),(1, 3))$。

样例 2

输入

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

输出

$1$ $1$ $2$ $1$ $1$ $1$

说明

第一个询问对应的唯一操作序列：$((3,5),(1,4))$。

第二个询问对应的唯一操作序列：$((1,3),(2,5)),((3,5),(2,4))$。

第三个询问对应的唯一操作序列：$((3,5),(2,5))$。

样例 3

输入

$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$

数据范围与提示

详细子任务附加限制及分值如下表所示：

子任务编号	附加限制	分值
$1$	$n \le 9$，$q \le 1000$	$11$
$2$	对于所有 $i=1,\ldots,n-3$，满足 $x_i=1$，$y_i=i+2$，且没有 $t_i=1$ 的事件	$15$
$3$	$q=1$	$27$
$4$	$n,q \le 1000$	$11$
$5$	无附加限制	$36$