Problem H
Flæðasmíði
Languages
en
is
The summer is being used to do all kinds of maintenance and the utilities are no exception. There are $n$ sources of water that have been found that need to be connected to $m$ customers. Each source provides exactly $1 \mathrm{L/s}$, and conveniently enough, the pipes can transport exactly $1 \mathrm{L/s}$. But all customers must receive an equal amount of water, otherwise people will get upset which is no good. In order to balance the flow, we can connect the pipes to special joints. Each joint can have up to two inputs and up to two outputs. For each joint, the flow coming into it is always equal to the flow going out of it. Additionally, the joints make sure that, if they have two outputs, the flow out of the two outputs is equal. The pipes are also equipped with valves so if one goes from joint $A$ to joint $B$ water will only flow in that direction and not back. Now a plan has to be made regarding how to connect joints and pipes so each customer gets $\frac{n}{m} \mathrm{L/s}$. Care must be taken to make sure no pipe has to handle more than $1 \mathrm{L/s}$. However, the joints can handle as much water as gets pumped into them. The sources are numbered $1, 2, \dots , n$ and the customers are numbered $n + 1, n + 2, \dots , n + m$. The funding is quite limited, so the total number of joints can be at most $50\, 000$. The total number of pipes can also be at most $50\, 000$. Lastly, the customers can not have outputs.
Input
The input contains two integers $n$, the number of sources, and $m$, the number of customers, where $1 \leq n \leq m \leq 1\, 000$.
Output
The first line of the output should contain the two integers $V$, the number of joints, sources and customers included, and $E$, the number of pipes between them. The new joints are then numbered $n + m + 1, n + m + 2, \dots , V$. Then $E$ lines follow, each describing one pipe. The $i$-th line should contain two integers $A_ i$ and $B_ i$, representing that your solution includes a pipe from joint $A_ i$ to joint $B_ i$.
If there are multiple solutions, you may output any of them.
Sample Input 1 | Sample Output 1 |
---|---|
1 2 |
3 2 1 2 1 3 |
Sample Input 2 | Sample Output 2 |
---|---|
1 5 |
11 12 1 7 1 8 7 1 7 9 8 10 8 11 9 1 9 2 10 3 10 4 11 5 11 6 |
Sample Input 3 | Sample Output 3 |
---|---|
3 5 |
15 19 1 9 1 8 2 7 2 6 3 5 3 4 9 10 9 11 10 12 10 15 11 13 11 14 12 15 12 4 13 5 13 6 14 7 14 8 15 9 |