Cô bé Fran nhận được một chiếc khung gỗ có hình đa giác đều làm quà. Vì đa giác có ~n~ đỉnh nên anh ta cũng nhận được ~\frac{n(n-3)}{2}~ que gỗ tương ứng với mỗi đường chéo có thể có. Các đỉnh của đa giác được dán nhãn các số nguyên từ ~1~ đến ~n~ theo thứ tự ngược chiều kim đồng hồ. Lúc đầu, Fran sắp xếp ~n − 3~ que bên trong khung sao cho mỗi thanh chạm vào hai đỉnh không liền kề của khung và không có hai thanh nào giao nhau. Nói cách khác, anh ta đã tạo ra tam giác. Vì điều đó chưa đủ thú vị đối với anh ấy nên anh ấy quyết định thử nghiệm với cấu hình này bằng cách áp dụng một thao tác cụ thể bao gồm hai bước:

1. Loại bỏ một que.

2. Thêm một que theo cách chúng ta có được một tam giác.

Chúng ta mô tả một thao tác bằng một cặp có thứ tự gồm các cặp không có thứ tự ~((a,b),(c,d))~ biểu thị rằng cô bé Fran đã loại bỏ một que nối các đỉnh ~a~ và ~b~, đồng thời thêm một que nối các đỉnh ~c~ và ~d~.

Fran rất yêu thích những chiếc quạt tay nên khi thực hiện những thao tác này, đôi khi anh tự hỏi: “Cần bao nhiêu thao tác để biến tam giác này thành tam giác “quạt” ở đỉnh ~x~, và có bao nhiêu cách thực hiện được điều này?”.

Vì anh ấy bận làm việc và vui chơi nên anh ấy nhờ bạn giúp đỡ!

Tam giác “quạt” ở đỉnh ~x~ là tam giác trong đó tất cả các đường chéo có một đầu mút chung, đó là đỉnh ~x~.

Gọi số thao tác cần thực hiện là ~m~. Cho ~f_1, f_2, ... , f_m~ là một chuỗi các thao tác mà khi thực hiện theo thứ tự nhất định sẽ đạt được tam giác mong muốn, do đó thể hiện một cách để đạt được điều đó. Cho ~s_1, s_2, ... , s_m~ là một chuỗi khác như vậy. Hai dãy phân biệt nếu tồn tại chỉ số ~i~ sao cho ~f_i \neq s_i~.

Vì số lượng các chuỗi như vậy có thể rất lớn nên cô bé Fran chỉ quan tâm đến kết quả sau khi lấy phần dư của phép chia với số ~10^9+7~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ (~4 \leq n \leq 2 \times 10^5, 1 \leq q \leq 2 \times 10^5~) là số đỉnh và số sự kiện.
• Mỗi dòng trong ~n-3~ dòng tiếp theo là hai số nguyên ~x_i~, ~y_i~ (~1 \leq x_i, y_i \leq n~) là nhãn của hai đỉnh mà que nối.
• Mỗi dòng trong ~q~ tiếp theo là số nguyên ~t_i~ (~1 \leq t_i \leq 2~) thể hiện loại sự kiện:

~\space\space\space\space\space\space\space\space\space\circ~ Nếu ~t_i = 1~, theo sau đó là bốn số nguyên ~a_i, b_i, c_i, d_i~ (~1 \leq a_i, b_i, c_i, d_i \leq n~) mô tả thao tác ~((a_i, b_i), (c_i, d_i))~ được thực hiện.

~\space\space\space\space\space\space\space\space\space\circ~ Nếu ~t_i = 2~, theo sau đó là số nguyên ~x_i~ (~1 \leq x_i \leq n~) mô tả câu hỏi của Fran.

Output

Với mỗi sự kiện loại ~2~, theo thứ tự đầu vào, đưa ra hai số nguyên, số thao tác ít nhất và số cách như vậy để đạt được tam giác theo yêu cầu.

Scoring

1. ~n \leq 9, q \leq 10^3~ (12 điểm)

2. ~x_i = 1, y_i = i+2 \space \forall i =1,2,...,n-3~ và không có sự kiện loại ~1~ (16 điểm)

3. ~q=1~ (30 điểm)

4. ~n,q\leq 10^3~ (12 điểm)

5. Không có ràng buộc gì thêm (40 điểm)

Sample Input 1

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

Sample Output 1

0 1
1 1

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

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

Explanation

• Ở ví dụ đầu tiên, ban đầu có tam giác "quạt" ở đỉnh 1, nên Fran không cần thao tác gì cả, được tính là ~1~ cách. Xong khi thực hiện thao tác ~((1,3),(2,4))~, chỉ có một cách duy nhất để đạt được tam giác "quạt" ở đỉnh 1 là thực hiện thao tác ~((2,4),(1,3))~.
• Ở ví dụ thứ hai:

~\space\space\space\space\space\space\space\space\space\circ~ Dãy thao tác duy nhất cho sự kiện thứ nhất: ~((3,5),(1,4))~.

~\space\space\space\space\space\space\space\space\space\circ~ Dãy thao tác duy nhất cho sự kiện thứ hai: ~((1,3),(2,5)), ((3,5),(2,4))~.

~\space\space\space\space\space\space\space\space\space\circ~ Dãy thao tác duy nhất cho sự kiện thứ tư: ~((3,5),(2,5))~.