On a Distant Amazon
Time limit2sMemory limit256 MB
Given n women, construct a mother-daughter forest where exactly a women have at least one daughter and exactly b are someone's daughter, or report impossible.
- Level
Medium6 of 10
- Topics
- Graph, Greedy, Tree, Implementation
- Solved
- No attempts yet
Problem
Programmer Gosha likes to read fairy tales to his children at bedtime. One day the tale he decided to read began like this:
"In a distant village in the valley of the Amazon River lives a tribe in which there is not a single man. Four women live in this village: three mothers and three daughters."
Gosha's children found this passage suspicious, and he had to quickly explain how four people could include three mothers and three daughters at the same time.
Assuming that the tale may later describe other villages, Gosha wants to learn how to quickly construct an example of a tribe with exactly n women in which a of the women are the mother of someone in the tribe and b of the women are the daughter of someone in the tribe.
Help him quickly come up with an example of such a tribe for given n, a, and b.
Input
The first line contains an integer T (1 ≤ T ≤ 104), the number of test cases. Each of the next T lines contains three positive integers: n, a, and b. (1 ≤ n, a, b ≤ 105)
The sum of all values of n in the input does not exceed 105.
Output
For each of the T test cases, output "IMPOSSIBLE" if the required tribe does not exist. If the tribe exists, output a description of the tribe in n lines. Number all members of the tribe from 1 to n. In the i-th line, output first the number k, the number of daughters of the i-th woman, followed by k numbers, the indices of her daughters. Each woman can have at most one mother.
If there are several valid answers, output any of them. Naturally, a mother is always older than her daughter, so the tribe must allow a way to assign ages to all the women such that this rule holds.