Little Fran received a wooden frame in the shape of a regular polygon as a gift. As the polygon has ~n~ vertices, he also received ~\frac{n(n-3)}{2}~ wooden sticks that match each possible diagonal. Vertices of the polygon are labeled with integers from ~1~ to ~n~ in counterclockwise order. In the beginning, Fran arranged ~n-3~ sticks inside the frame in such a way that every stick touches two non-neighboring vertices of the frame, and no two sticks cross each other. In other words, he made a triangulation. As that was not interesting enough for him, he decided to play with this configuration by applying a particular operation that consists of two steps:

1. Remove a stick.
2. Add a new stick in such a way that we obtain a new triangulation.

We characterize the operation with an ordered pair of unordered pairs ~((a, b), (c, d))~ which signifies that little Fran removed a stick touching vertices ~a~ and ~b~, and added a stick touching vertices ~c~ and ~d~.

Fran loves hand fans so, while doing these operations, he sometimes asks himself:

How many operations are needed to transform this triangulation into a "fan" triangulation in vertex ~x~, and in how many ways is this achievable?

Since he is busy doing operations and having fun, he asks for your help!

A "fan" triangulation in vertex ~x~ is a triangulation where all diagonals have a common endpoint, namely vertex ~x~.

Let the number of needed operations be ~m~. Let ~f_1, f_2, \ldots , f_m~ be a sequence of operations that, when applied in the given order, achieves the wanted triangulation, thus representing one way of getting there. Let ~s_1, s_2, \ldots , s_m~ be another such sequence. Two sequences are distinct if there exists an index ~i~ such that ~f_i \neq s_i~.

As the number of such sequences can be huge, little Fran is only interested in its remainder modulo ~10^9 + 7~.

Input Specification

In the first line, there are integers ~n~ and ~q~ ~(4 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5)~, the number of vertices and the number of events.

In each of the next ~n-3~ lines, there are integers ~x_i, y_i~ ~(1 \le x_i, y_i \le n)~, the labels of the vertices that the ~i~-th stick touches.

In each of the next ~q~ lines, there is the integer ~t_i~ ~(1 \le t_i \le 2)~ that represents the type of event.

If ~t_i = 1~, it is followed by 4 integers ~a_i, b_i, c_i, d_i~ ~(1 \le a_i, b_i, c_i, d_i \le n)~ that signify an operation ~((a_i, b_i), (c_i, d_i))~ is being made at that moment. It is guaranteed that the given operation can be realized.

If ~t_i = 2~, it is followed by an integer ~x_i~ ~(1 \le x_i \le n)~, which means that little Fran is interested in data for the "fan" triangulation at vertex ~x_i~ in relation to the current triangulation.

Output Specification

For every event of type 2, in the order they came in the input, output two integers: the minimal number of operations needed and the number of ways to get to the target triangulation using the minimal number of operations.

Scoring

Subtask	Points	Constraints
1	12	~n \le 9, q \le 1\,000~
2	16	~x_i = 1, y_i = i+2~ for all ~i = 1, \ldots, n-3~ and there are no events of type 1.
3	30	~q = 1~
4	12	~n, q \le 1\,000~
5	40	No additional constraints.

Sample Input 1

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

Sample Output 1

0 1
1 1

Explanation for Sample 1

The starting triangulation is already a "fan" triangulation in vertex 1, so little Fran must do no operations, and there is one way of doing so.

After executing the given operation, there is now only one way to get it to the previous state and that is by applying the operation ~((2, 4), (1, 3))~.

Sample Input 2

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

Sample Output 2

1 1
2 1
1 1

Explanation for Sample 2

The only sequence of operations for the first query is ~((3, 5), (1, 4))~.

The only sequence of operations for the second query is ~((1, 3), (2, 5)), ((3, 5), (2, 4))~.

The only sequence of operations for the third query is ~((3, 5), (2, 5))~.

Sample Input 3

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

Sample Output 3

4 12
3 6