P10230 [COCI 2023/2024 #4] Lepeze

**译自 [COCI 2023/2024 Contest #4](https://hsin.hr/coci/archive/2023_2024) T3「[Lepeze](https://hsin.hr/coci/archive/2023_2024/contest4_tasks.pdf)」**

小 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 起始三角剖分已经是以顶点 $1$ 为中心的「扇形」三角剖分，所以小 Fran 不需要进行任何操作，有一种方式可以实现。在执行给定的操作后，将其恢复到先前状态只有一种方式，即进行操作 $((2, 4),(1, 3))$。 ### 样例解释 2 第一个询问对应的唯一操作序列：$((3,5),(1,4))$。 第二个询问对应的唯一操作序列：$((1,3),(2,5)),((3,5),(2,4))$。 第三个询问对应的唯一操作序列：$((3,5),(2,4))$。 ### 子任务 | 子任务编号 | 附加限制 | 分值 | | :--------: | :----------------------------------------------------------: | :--: | | $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$ |