题目背景

译自 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$ 的事件，按照它们在输入中的顺序，输出两个整数：所需的最小操作数和使用最小操作数达到目标三角剖分的方式数量。

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

提示

样例解释 1

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

样例解释 2

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

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

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

子任务

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