레페제

꼬마 프란은 정다각형 모양의 나무 틀을 선물로 받았다. 다각형의 꼭짓점이 $n$개이므로, 가능한 대각선마다 하나씩 맞는 나무 막대 $\frac{n(n-3)}{2}$개도 함께 받았다. 꼭짓점에는 반시계 방향으로 1부터 $n$까지 번호가 붙어 있다.

프란은 처음에 틀 안에 막대 $n-3$개를 놓았다. 각 막대는 이웃하지 않은 두 꼭짓점을 잇고, 어떤 두 막대도 서로 교차하지 않는다. 즉, 막대들이 삼각분할을 이룬다.

프란은 다음 두 단계로 이루어진 연산으로 이 배치를 바꾸며 논다.

1. 막대 하나를 제거한다.
2. 새 막대를 하나 추가해서 새로운 삼각분할을 만든다.

연산은 순서쌍 $((a, b),(c, d))$로 나타낸다. 이는 꼭짓점 $a$와 $b$를 잇는 막대를 제거하고, 꼭짓점 $c$와 $d$를 잇는 막대를 추가했다는 뜻이다.

프란은 현재 삼각분할을 꼭짓점 $x$에 대한 부채 삼각분할로 바꾸려면 연산이 몇 번 필요한지, 그리고 그렇게 하는 방법이 몇 가지인지 궁금해한다. 꼭짓점 $x$에 대한 부채 삼각분할은 모든 대각선이 공통 끝점 $x$를 갖는 삼각분할이다.

필요한 최소 연산 횟수를 $m$이라고 하자. $m$번의 연산으로 목표 분할에 도달하는 연산 수열 $f_1, f_2, \dots, f_m$과 $s_1, s_2, \dots, s_m$을 생각한다. 어떤 인덱스 $i$에 대해 $f_i \ne 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$개 줄에는 $i$번째 막대가 잇는 꼭짓점 번호 $x_i$와 $y_i$가 주어진다 ($1 \le x_i, y_i \le n$).

다음 $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$)가 이어지며, 현재 삼각분할에 대해 꼭짓점 $x_i$에 대한 부채 삼각분할의 정보를 구한다.

$t_i = 2$인 이벤트마다 입력 순서대로 한 줄에 두 정수를 출력한다. 첫 번째는 필요한 최소 연산 횟수이고, 두 번째는 그 횟수로 목표 삼각분할에 도달하는 방법의 수를 $10^9 + 7$로 나눈 나머지이다.