lepeze — COCI CONTEST_#4
Task type: batch | Time limit: 2 s | Memory limit: 512 MB | Difficulty: 24
Algorithms: polygon triangulation, graph theory, combinatorics, dynamic data structures

# Task Lepeze

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 *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 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:

![](_page_0_Picture_4.jpeg)

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!

"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*<sub>1</sub>, *f*<sub>2</sub>, ..., *f*<sub>m</sub> be a sequence of operations that, when applied in given order, achieves the wanted triangulation, thus representing one way of getting there. Let *s*<sub>1</sub>, *s*<sub>2</sub>, ..., *s*<sub>m</sub> be another such sequence. Two sequences are distinct if there exists an index *i* such that *f*<sub>i</sub> != *s*<sub>i</sub>.

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

## Input

In the first line are integers *n* and *q* (4 ≤ *n* ≤ 2 * 10<sup>5</sup>, 1 ≤ *q* ≤ 2 * 10<sup>5</sup>), the number of vertices and the number of events.

In each of the next *n* - 3 lines there are integers *x*<sub>i</sub>, *y*<sub>i</sub> (1 ≤ *x*<sub>i</sub>, *y*<sub>i</sub> ≤ *n*), the labels of vertices that the *i*-th stick touches.

In each of the next *q* lines there is the integer *t*<sub>i</sub> (1 ≤ *t*<sub>i</sub> ≤ 2) that represents the type of event.

If *t*<sub>i</sub> = 1, it is followed by 4 integers *a*<sub>i</sub>, *b*<sub>i</sub>, *c*<sub>i</sub>, *d*<sub>i</sub> (1 ≤ *a*<sub>i</sub>, *b*<sub>i</sub>, *c*<sub>i</sub>, *d*<sub>i</sub> ≤ *n*) that signify an operation ((*a*<sub>i</sub>, *b*<sub>i</sub>), (*c*<sub>i</sub>, *d*<sub>i</sub>)) is being made at that moment. It is guaranteed that the given operation can be realized.

If *t*<sub>i</sub> = 2, it is followed by an integer *x*<sub>i</sub> (1 ≤ *x*<sub>i</sub> ≤ *n*), which means that little Fran is interested in data for the "fan" triangulation at vertex *x*<sub>i</sub> in relation to the current triangulation.

## Output

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.

![](_page_1_Picture_0.jpeg)

## Scoring

| Subtask | Points | Constraints                                                                                                  |
| :------: | :----: | :----------------------------------------------------------------------------------------------------------- |
|     1    |   12   | *n* ≤ 9, *q* ≤ 1000                                                                                           |
|     2    |   16   | *x*<sub>i</sub> = 1, *y*<sub>i</sub> = *i* + 2 for all *i* = 1, ..., *n* - 3 and there are no events of type 1. |
|     3    |   30   | *q* = 1                                                                                                      |
|     4    |   12   | *n*, *q* ≤ 1000                                                                                              |
|     5    |   40   | No additional constraints.                                                                                   |

## Examples

| Input | Input       | Input |
| :---- | :---------- | :---- |
| 4 3   | 5 4         | 9 3   |
| 1 3   | 1 3         | 1 5   |
| 2 1   | 3 5         | 1 7   |
| 1 1 3 2 4 | 2 1         | 2 4   |
| 2 1   | 2 2         | 2 5   |
|       | 1 1 3 2 5   | 5 7   |
|       | 2 2         | 7 9   |
|       |             | 2 1   |
| Output | Output      | Output |
| 0 1   | 1 1         | 4 12  |
| 1 1   | 2 1         | 3 6   |
|       | 1 1 | 1 2 5 1 4 |
|       |             | 2 1   |

#### Clarification of the first example:

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)).

#### Clarification of the second example:

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)).

Starter code: