Problem D
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. See Figure 1 for an example.
Input
The input consists of:

One line with two coprime integers $a$ and $b$ ($1 \le a,b \le 1000$) separated by a ‘/’, giving the desired average optimal time to reach the exit as the fraction $\frac{a}{b}$.
Output
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 \le n, m \le 10^6$), the number of vertices and the number of edges.

$m$ pairs of integers $u$ and $v$ ($1 \le u,v \le 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 \le n, m \le 10^6$.
If there are multiple valid solutions, you may output any one of them.
Sample Input 1  Sample Output 1 

1/2 
2 1 1 2 
Sample Input 2  Sample Output 2 

1/3 
impossible 
Sample Input 3  Sample Output 3 

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 