P17053 [NWERC 2022] ETA

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.