背景

译自 Northwestern Europe Regional Contest (NWERC) 2022 Problem E。

原题许可协议为 CC BY-SA。

题目描述

你想为一个电脑游戏设计一个关卡。这个关卡可以描述为一张连通无向图，顶点编号为 $1$ 到 $n$。在游戏中，玩家角色会以均匀随机的方式被放置在这 $n$ 个顶点之一，目标是尽快到达位于顶点 $1$ 的出口。穿过一条边恰好需要 $1$ 秒。

关卡的难度由到达出口的平均最优时间决定。给定这个平均最优时间的目标值，请构造一个关卡，使得这个目标值恰好达到。

:::align{center}

:::

图：样例输出 3 的示意图，在该关卡中，到达顶点 $1$ 的平均最优时间为 $\frac{7}{4}$。

输入格式

输入包含一行两个互质整数 $a$ 和 $b$（$1 \leq a,b \leq 1000$），中间用字符 / 分隔，表示期望的到达出口平均最优时间为分数 $\frac{a}{b}$。

输出格式

如果不存在一张连通图，使得到达顶点 $1$ 的平均最优时间为 $\frac{a}{b}$，输出 impossible。

否则，按照以下格式输出任意一张满足要求的图：

• 两个整数 $n$ 和 $m$（$1 \leq n,m \leq 10^6$），表示顶点数和边数。
• 接下来输出 $m$ 对整数 $u$ 和 $v$（$1 \leq u,v \leq n$），表示顶点 $u$ 与顶点 $v$ 之间有一条边。

图可以包含自环和重边。题目保证：如果存在一张合法图，那么也存在一张满足 $1 \leq n,m \leq 10^6$ 的合法图。

如果有多个合法解，你可以输出任意一个。

1/2

2 1 
1 2 

1/3

impossible

7/4

8 12
1 2
1 3
2 3
2 4
3 5
3 6
4 5
5 6
4 7
5 7
4 8
6 8

提示

【数据范围与约定】

对于所有数据，满足 $1 \leq a,b \leq 1000$，$a$ 与 $b$ 互质；若存在合法图，则存在满足 $1 \leq n,m \leq 10^6$ 的合法图；允许自环与重边。