페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#7073
서브태스크

Lepeze 2초 1024MB

문제

Little Fran received a wooden frame in the shape of a regular polygon as a gift. As polygon has n vertices, he also received \frac{n(n-3)}{2} wooden sticks that match each possible diagonal. Vertices of the polygon are labelled 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 vertive 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 is 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!

“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, \dots , f_m be a sequence of operations that, when applied in given order, achieves wanted triangulation, thus representing one way of getting there. Let s_1, s_2, \dots , s_m be another such sequence. Two sequences are distinct if there exists an index i such that f_i \ne s_i .

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


입력

In the first line are integers n and q (4 ≤ n ≤ 2 \cdot 10^5, 1 ≤ q ≤ 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 ≤ x_i , y_i ≤ n), the labels of vertices that the i-th stick touches.

In each of the next q lines there is the integer t_i (1 ≤ t_i ≤ 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 ≤ a_i , b_i , c_i , d_i ≤ n) that signify an operation ((a_i , b_i),(c_i , d_i)) is being made at that moment. It is guaranteed that given operation can be realized.

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


출력

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


부분문제

번호 점수 조건
#111점

n ≤ 9, q ≤ 1\, 000

#215점

 x_i = 1, y_i = i + 2 for all i = 1, \dots , n - 3 and there are no events of type 1.

#327점

q = 1

#411점

 n, q ≤ 1\, 000

#536점

No additional constraints.


예제1

입력
43
13
21
11324
21
출력
01
11

Starting triangulation is already a “fan” triangulation in vertex 1, so little Fran must do no operations, which there is one way of doing so. After executing a given operation, there is now only one way to get it to the previous state and that is by applying operation ((2, 4),(1, 3)).


예제2

입력
54
13
35
21
22
11325
22
출력
11
21
11

Only sequence of operations for the first query: ((3, 5),(1, 4)).

Only sequence of operations for the second query: ((1, 3),(2, 5)),((3, 5),(2, 4)).

Only sequence of operations for the third query: ((3, 5),(2, 5)).


예제3

입력
93
15
17
24
25
57
79
21
12514
21
출력
412
36

출처

COCI 2023/2024 Contest #4 3번

역링크