题目描述

You want to design a level for a computer game. The level can be described as a connected undirected graph with vertices numbered from $1$ to $n$. In the game, the player's character is dropped at one of the $n$ vertices uniformly at random and their goal is to reach the exit located at vertex $1$ as quickly as possible. Traversing an edge takes exactly $1$ second.

The difficulty of the level is determined by the average optimal time to reach the exit. Given a target value for this average optimal time, construct a level so that this target value is reached.

:::align{center}

:::

Figure: Illustration of Sample Output 3, a level where the average optimal time to reach vertex $1$ is $\frac{7}{4}$.

输入格式

The input consists of one line with two coprime integers $a$ and $b$ ($1 \leq a,b \leq 1000$) separated by a /, giving the desired average optimal time to reach the exit as the fraction $\frac{a}{b}$.

输出格式

If no connected graph with the average optimal time $\frac{a}{b}$ to reach vertex $1$ exists, output impossible. Otherwise, output one such graph in the following format:

• Two integers $n$ and $m$ ($1 \leq n,m \leq 10^6$), the number of vertices and the number of edges.
• $m$ pairs of integers $u$ and $v$ ($1 \leq u,v \leq n$), indicating an edge between vertices $u$ and $v$.

The graph may include self loops and parallel edges. You are given that if there exists a valid graph, then there also exists one with $1 \leq n,m \leq 10^6$.

If there are multiple valid solutions, you may output any one of them.

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