小弗兰收到一个正多边形形状的木框作为礼物。由于多边形有 $n$ 个顶点，他还收到了 $\frac{n(n-3)}{2}$ 根木棍，每根木棍对应一条可能的对角线。多边形的顶点按逆时针方向标有从 $1$ 到 $n$ 的整数。起初，弗兰在框架内放置了 $n-3$ 根木棍，使得每根木棍连接框架的两个非相邻顶点，且没有任何两根木棍相交。换句话说，他完成了一个三角剖分。由于这对他来说不够有趣，他决定通过执行一个包含两个步骤的特定操作来摆弄这个配置：

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

我们将该操作描述为一个无序对的有序对 $((a, b), (c, d))$，表示小弗兰移除了连接顶点 $a$ 和 $b$ 的木棍，并添加了连接顶点 $c$ 和 $d$ 的木棍。

弗兰喜欢折扇，因此在进行这些操作时，他有时会问自己：“将当前的三角剖分转换为顶点 $x$ 的‘扇形’三角剖分需要多少次操作，以及有多少种实现方式？”

既然他忙于操作并乐在其中，他请求你的帮助！

顶点 $x$ 的“扇形”三角剖分是指所有对角线都有一个公共端点，即顶点 $x$ 的三角剖分。

设所需的操作次数为 $m$。设 $f_1, f_2, \dots, f_m$ 是一个操作序列，当按给定顺序应用时，可以达到想要的三角剖分，从而代表了实现目标的一种方式。设 $s_1, s_2, \dots, s_m$ 是另一个这样的序列。如果存在一个索引 $i$ 使得 $f_i \neq s_i$，则两个序列是不同的。

由于这样的序列数量可能非常巨大，小弗兰只对它们对 $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$，后面跟着 $4$ 个整数 $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$)，表示小弗兰对相对于当前三角剖分的顶点 $x_i$ 的“扇形”三角剖分数据感兴趣。

输出格式

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

子任务

样例

样例输入 1

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

样例输出 1

0 1
1 1

样例输入 2

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

样例输出 2

1 1
2 1
1 1

样例输入 3

9 3
1 5
1 7
2 4
2 5
5 7
7 9
2 1
1 2 5 1 4
2 1

样例输出 3

4 12
3 6

说明

第一个样例的说明： 初始三角剖分已经是顶点 $1$ 的“扇形”三角剖分，所以小弗兰不需要进行任何操作，有一种实现方式。执行给定的操作后，现在只有一种方法可以将其恢复到之前的状态，即应用操作 $((2, 4), (1, 3))$。

第二个样例的说明： 第一个查询的唯一操作序列：$((3, 5), (1, 4))$。 第二个查询的唯一操作序列：$((1, 3), (2, 5)), ((3, 5), (2, 4))$。 第三个查询的唯一操作序列：$((3, 5), (2, 5))$。