Little Fran received a wooden frame in the shape of a regular polygon as a gift.
As polygon has \(n\) vertices, he also received ^{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 n\(on-ne\)ighboring 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, f2, . . . , 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, s2, . . . , s\(m\) be another such sequence. Two sequences are distinct if there exists an index \(i\) such that
\(f@@RISE_MATH_BLOCK_0@@i\).
As the number of such sequences can be huge, little Fran is only interested in its remainder modulo
\(10^{9} + 7\).

Subtask 1 (12 points): \(n \le 9\), \(q \le 1\,000\)

Subtask 2 (16 points): \(x\)\(i = 1\), y\(i = i + 2\) for all \(i = 1\), . . . , \(n - 3\) and there are no events of type 1.

Subtask 3 (30 points): \(q = 1\)

Subtask 4 (12 points): n, \(q \le 1\,000\)

Subtask 5 (40 points): No additional constraints.

In the first line are integeres \(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@@RISE_MATH_BLOCK_0@@i\), y\(i \le n\)), the labels of vertices that the \(i-th\)
stick touches.
In each of the next \(q\) lines there is the integer \(t@@RISE_MATH_BLOCK_1@@i \le 2\)) that represents the type of event.
If \(t@@RISE_MATH_BLOCK_2@@i\), b\(i\), c\(i\), d\(i\) (\(1 \le a@@RISE_MATH_BLOCK_3@@i\), b\(i\)), (\(c@@RISE_MATH_BLOCK_4@@i = 2\), it is followed by an integer \(x@@RISE_MATH_BLOCK_5@@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.

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.

생성자가 기록되지 않았습니다.

출처 COCI 2023/2024 Contest 4