## COCI '23 Contest 4 #3 Lepeze

View as PDF

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem types

Little Fran received a wooden frame in the shape of a regular polygon as a gift. As the polygon has vertices, he also received wooden sticks that match each possible diagonal. Vertices of the polygon are labeled with integers from to in counterclockwise order. In the beginning, Fran arranged 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 which signifies that little Fran removed a stick touching vertices and , and added a stick touching vertices and .

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 , 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 is a triangulation where all diagonals have a common endpoint, namely vertex .

Let the number of needed operations be . Let be a sequence of operations that, when applied in the given order, achieves the wanted triangulation, thus representing one way of getting there. Let be another such sequence. Two sequences are distinct if there exists an index such that .

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

#### Input Specification

In the first line, there are integers and , the number of vertices and the number of events.

In each of the next lines, there are integers , the labels of the vertices that the -th stick touches.

In each of the next lines, there is the integer that represents the type of event.

If , it is followed by 4 integers that signify an operation is being made at that moment. It is guaranteed that the given operation can be realized.

If , it is followed by an integer , which means that little Fran is interested in data for the "fan" triangulation at vertex 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
2 16 for all and there are no events of type 1.
3 30
4 12
5 40 No additional constraints.

4 3
1 3
2 1
1 1 3 2 4
2 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 .

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

1 1
2 1
1 1

#### Explanation for Sample 2

The only sequence of operations for the first query is .

The only sequence of operations for the second query is .

The only sequence of operations for the third query is .

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

4 12
3 6

## Comments

There are no comments at the moment.