题目描述

小 R 与小 W 在玩游戏。

他们有一个 边数为 $n$ 的凸多边形，顶点按逆时针依次编号为 $1, 2, 3, \dots, n$。
最初凸多边形中有 $n$ 条线段，即多边形的 $n$ 条边。
用有序数对 $(a, b)$（其中 $a < b$）表示端点分别为顶点 $a, b$ 的线段。

---

游戏准备阶段

在游戏开始前，小 W 进行若干次操作：
每次选择两个互异顶点，连一条线段，且该线段 不与已有线段重合或相交（仅公共端点不算相交）。
直到无法继续连线，得到状态 $S_0$。
此时 $S_0$ 包含的线段为多边形的边与小 W 添加的线段，它们将多边形划分为若干个三角形区域。

对于任意一个三角形，其顶点为 $i, j, k$（$i < j < k$），给这个三角形一个 标号 $j$。
这样每个三角形被标上 $2, 3, \dots, n-1$ 中的一个数，且没有标号相同的两个三角形。

---

旋转操作

定义「旋转」操作：
选定四个顶点 $a, b, c, d$，满足
$1 \le a < b < c < d \le n$
且它们两两之间共有 $5$ 条线段：
$(a,b),\ (b,c),\ (c,d),\ (a,d),\ (a,c)$
然后 删去线段 $(a,c)$，并 连上线段 $(b,d)$。
用有序数对 $(a, c)$ 唯一表示该次「旋转」，称为 $(a,c)$ 旋转。
旋转后多边形中依然不存在相交的线段。

---

游戏过程

小 W 将初始状态 $S_0$（或由其旋转一次得到的新状态）展示给小 R。
游戏开始后，小 R 每次可对当前状态进行一次「旋转」。
有限次旋转后，会得到一个无法继续旋转的状态，游戏结束。
将每次旋转对应的有序数对按顺序写下，得到该轮游戏的 操作方案。

---

题目任务

小 W 以 $S_0$ 为基础，产生了 $m$ 个新状态：
第 $i$ 个状态 $S_i$ 为对 $S_0$ 进行一次 $(a_i, c_i)$ 旋转后得到的状态。

你需要帮助小 R 求出：

• 分别以 $S_0, S_1, \dots, S_m$ 作为初始状态时，完成游戏所需的 最少旋转次数。
• 如果 $W = 1$，还需要求出 最少旋转次数的不同操作方案数（对 $10^9+7$ 取模）。

---

输入格式

• 第一行：整数 $W$（$0$ 或 $1$），表示是否需要输出方案数。
• 第二行：正整数 $n$，表示凸多边形边数。
• 接下来 $n-3$ 行：每行两个正整数 $x, y$，表示小 W 在 $S_0$ 中连的一条线段（保证合法）。
• 接下来一行：整数 $m$，表示新状态个数。
• 接下来 $m$ 行：每行两个整数 $a, b$，表示对 $S_0$ 进行 $(a, b)$ 旋转得到 $S_i$。

---

输出格式

输出共 $m+1$ 行：

• 若 $W = 0$，每行一个整数，表示 $S_{i-1}$ 的最少旋转次数。
• 若 $W = 1$，每行两个整数：最少旋转次数、方案数（取模后）。

---

样例 $1$

输入

1
6
1 3
1 5
3 5
1
1 3

输出

3 2
3 1

解释

• 以 $S_0$ 为初始状态：最少旋转次数 $3$，方案数 $2$。
• 以 $S_1$ 为初始状态：最少旋转次数 $3$，方案数 $1$。

---

样例 $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

输出

8 210
7 210
8 70
8 105
8 140

---

数据范围

测试点编号	$W$	$n$	$m$
$1$–$10$	$0$ 或 $1$	较小
$11$–$20$		$\le 10^5$

对于所有数据：
$3 \le n \le 10^5,\quad 0 \le m \le 10^5$