{"raw_statement":[{"iden":"background","content":"**译自 [COCI 2023/2024 Contest #4](https://hsin.hr/coci/archive/2023_2024) T3「[Lepeze](https://hsin.hr/coci/archive/2023_2024/contest4_tasks.pdf)」**"},{"iden":"statement","content":"小 Fran 收到了一个礼物——一个正多边形木制框架。由于多边形有 $n$ 个顶点，他还收到了 $\\frac{n(n-3)}{2}$ 根与每条对角线相匹配的木棍。多边形的顶点按逆时针顺序标记为 $1$ 到 $n$。一开始，弗兰将 $n-3$ 根木棍放在框架内，以使每根木棍接触框架的两个不相邻顶点，并且没有两根木棍相交。换句话说，他做了一个三角剖分。由于这对他来说不够有趣，他决定进行特定的操作来改变这种放置方法，该操作由两个步骤组成：\n\n1. 移除一根木棍。\n2. 添加一根新的木棍，使得我们得到一个新的三角剖分。\n\n我们用一个由无序对组成的有序对 $((a, b),(c, d))$ 来描述这个操作，表示小 Fran 移除了接触顶点 $a$ 和 $b$ 的木棍，并添加了接触顶点 $c$ 和 $d$ 的木棍。\n\n弗兰喜欢扇子，所以在进行这些操作时，他有时会问自己：「将这个三角剖分转换为以顶点 $x$ 为『扇形』三角剖分需要多少次操作，并且有多少种方式可以实现？」\n\n由于他忙于操作和娱乐，他请求你的帮助！\n\n以顶点 $x$ 为中心的「扇形」三角剖分是一种三角剖分，其中所有的对角线都有一个共同的端点，即顶点 $x$。\n\n设所需操作的数量为 $m$。设 $f_1,f_2,\\ldots ,f_m$ 是一个操作序列，满足按这一顺序操作可以实现满足条件的三角剖分。设 $s_1,s_2,\\ldots ,s_m$ 是另一种这样的序列。如果存在一个下标 $i$ 使得 $f_i\\neq s_i$，则两个序列是不同的。\n\n由于这样的序列数量可能非常大，小 Fran 只关心它对 $10^9 + 7$ 取模后的值。"},{"iden":"input","content":"第一行两个整数 $n$ 和 $q\\ (4\\le n\\le 2\\cdot 10^5,1\\le q\\le 2\\cdot 10^5)$，表示顶点数和事件数。\n\n接下来 $n-3$ 行，每行两个整数 $x_i,y_i\\ (1\\le x_i,y_i\\le n)$，表示第 $i$ 根木棍接触的两个顶点。\n\n接下来 $q$ 行，每行描述一个事件。第一个整数为 $t_i\\ (1\\le t_i\\le 2)$，表示事件类别。\n\n如果 $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))$ 操作。保证给出的操作可以实现。\n\n如果 $t_i=2$，则接下来一个整数 $x_i\\ (1\\le x_i\\le n)$，表示小 Fran 对与目前顶点 $x_i$​ 处的「扇形」三角剖分的数据感兴趣。"},{"iden":"output","content":"对于每个类型为 $2$ 的事件，按照它们在输入中的顺序，输出两个整数：所需的最小操作数和使用最小操作数达到目标三角剖分的方式数量。"},{"iden":"note","content":"### 样例解释 1\n\n起始三角剖分已经是以顶点 $1$ 为中心的「扇形」三角剖分，所以小 Fran 不需要进行任何操作，有一种方式可以实现。在执行给定的操作后，将其恢复到先前状态只有一种方式，即进行操作 $((2, 4),(1, 3))$。\n\n### 样例解释 2\n\n第一个询问对应的唯一操作序列：$((3,5),(1,4))$。\n\n第二个询问对应的唯一操作序列：$((1,3),(2,5)),((3,5),(2,4))$。\n\n第三个询问对应的唯一操作序列：$((3,5),(2,4))$。\n\n### 子任务\n\n| 子任务编号 |                           附加限制                           | 分值 |\n| :--------: | :----------------------------------------------------------: | :--: |\n|    $1$     |                     $n\\le 9,q\\le 1\\ 000$                     | $12$ |\n|    $2$     | 对于所有 $i=1,\\ldots,n-3$，满足 $x_i=1,y_i=i+2$，且没有 $t_i=1$ 的事件 | $16$ |\n|    $3$     |                            $q=1$                             | $30$ |\n|    $4$     |                       $n,q\\le 1\\ 000$                        | $12$ |\n|    $5$     |                          无附加限制                          | $40$ |"}],"translated_statement":null,"sample_group":[["4 3\n1 3\n2 1\n1 1 3 2 4\n2 1\n","0 1\n1 1\n"],["5 4\n1 3\n3 5\n2 1\n2 2\n1 1 3 2 5\n2 2\n","1 1\n2 1\n1 1\n"],["9 3\n1 5\n1 7\n2 4\n2 5\n5 7\n7 9\n2 1\n1 2 5 1 4\n2 1\n","4 12\n3 6\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}