Problem Description

Xiao R and Xiao W are playing a game.

They have a convex polygon with \( n \) sides, with its vertices labeled in counterclockwise order as \( 1, 2, 3, \cdots, n \). Initially, the polygon has \( n \) segments, which are the \( n \) sides of the polygon. Here, we represent a segment with endpoints at vertices \( a \) and \( b \) (where \( a < b \)) as an ordered pair \( (a, b) \).

Before the game starts, Xiao W performs some operations. Each operation involves selecting two distinct vertices of the polygon, connecting them with a segment, ensuring that the new segment does not overlap or intersect with any existing segments (sharing a common endpoint does not count as intersection).

He repeats this process until no more segments can be added, resulting in state \( s_0 \). \( s_0 \) includes the polygon's sides and the segments added by Xiao W. It is easy to see that these segments divide the polygon into triangular regions. For any triangle with vertices \( i, j, k \) (where \( i < j < k \)), we can assign it a label \( j \). Thus, each triangle is labeled with a number from \( 2, 3, \cdots, n-1 \), and no two triangles have the same label.

Xiao W defines a "rotation" operation: For the current state, select four vertices \( a, b, c, d \) such that \( 1 \leq a < b < c < d \leq n \) and there are exactly five segments between them—\( (a, b), (b, c), (c, d), (a, d), (a, c) \). Then, remove segment \( (a, c) \) and add segment \( (b, d) \). This "rotation" can be uniquely represented by the ordered pair \( (a, c) \). We call this rotation \( (a, c) \). Clearly, after each "rotation" operation, the polygon still does not contain any intersecting segments.

When Xiao W presents a state as the initial state of the game to Xiao R, the game begins. During the game, Xiao R can perform "rotation" operations on the current state. After a finite number of "rotation" operations, Xiao R will reach a state where no more "rotation" operations can be performed, ending the game. The sequence of ordered pairs corresponding to each "rotation" operation, in the order they were performed, constitutes the game's operation scheme.

To increase the difficulty, Xiao W generates \( m \) new states based on \( s_0 \). The \( i \)-th state \( s_i \) is obtained by performing a "rotation" operation on \( s_0 \). You need to help Xiao R determine the minimum number of "rotation" operations required to complete the game when starting from each of \( s_0, s_1, \cdots, s_m \), and sometimes also the number of distinct operation schemes with the minimum number of "rotation" operations, modulo \( 1e9+7 \).

Input Format

The first line contains an integer \( W \), indicating Xiao W's mood. If \( W \) is \( 0 \), you only need to find the minimum number of "rotation" operations. If \( W \) is \( 1 \), you also need to find the number of distinct operation schemes with the minimum number of "rotation" operations.

The second line contains a positive integer \( n \), representing the number of sides of the convex polygon.

The next \( n-3 \) lines each contain two positive integers \( x, y \), representing a segment added by Xiao W in \( s_0 \), with endpoints at vertices \( x \) and \( y \). It is guaranteed that this segment does not overlap or intersect with any existing segments.

The next line contains an integer \( m \), representing the number of new states generated by Xiao W based on \( s_0 \).

The next \( m \) lines each contain two integers. If the \( i \)-th line contains \( a, b \), it means that \( s_i \) is obtained by performing the \( (a, b) \) "rotation" on \( s_0 \).

Output Format

Output \( m+1 \) lines.

If \( W \) is \( 0 \), each line should contain an integer. The \( i \)-th (\( i = 1, 2, \cdots, m, m+1 \)) line should output the minimum number of "rotation" operations required when starting from \( S_{i-1} \).

If \( W \) is \( 1 \), each line should contain two integers. The \( i \)-th (\( i = 1, 2, \cdots, m, m+1 \)) line should output the minimum number of "rotation" operations and the number of distinct operation schemes with the minimum number of "rotation" operations, modulo \( 1e9+7 \), when starting from \( S_{i-1} \).

Sample Input and Output

Sample Input #1

1
6
1 3
1 5
3 5
1
1 3

Sample Output #1

3 2
3 1

Sample Input #2

1
12
1 10
1 6
1 3
3 6
3 5
6 10
6 8
8 10
10 12
4
1 10
1 3
6 8
1 6

Sample Output #2

8 210
7 210
8 70
8 105
8 140

见题面 Input 部分

见题面 Output 部分