Hide

Spider Fashion

/problems/codesprintla20.spiderfashion/file/statement/en/img-0001.jpg
Brown Yellow Blak Cross Orb Weaver Spider. Photo by Pixabay

Spiderdad is dressing up Spiderdaughter for UCLA’s SpiderCon in Ackerman Grand Ballroom. He has to choose from $n$ colors shoes (colors $1$ to $n$) and $m$ colors (colors $1$ to $m$) of socks. You can assume Spiderdaughter has an infinite supply of each color.

Spiderdaughter’s fashion sense requires that that no leg should have sock and shoe of the same color. SpiderCon rules require that no two adjacent shoes (i.e. shoes on adjacent legs) and no two adjacent socks have the same color.

Output a valid outfit, or that no valid outfit exists.

Note: Spiderdaughter, being a spider, has $8$ legs. However, on some years, she receives an extra leg on Christmas for being a good spider. So, in conclusion, the spider can have $8$ or $9$ legs. Also, recall from grade school that the legs of a spider are not arranged in a straight line, but in a circular fashion around the body :)

Input

The only line of the input contains three space separated integers $l$ ($8$ or $9$), $n$ ($1 \leq n \leq 10^6 $), and $m$ ($1 \leq m \leq 10^6 $).

Output

Output $-1$ if there is no valid outfit. Otherwise, the output consists of 3 lines: Line 1: The first line of output consists of a single integer $c$, the total number of colors used. Line 2: $l$ space separated integers representing the choices of shoe colors for each leg in order. Each integer $i$ in this list must be in the range ($1 \leq i \leq n$). Line 3: $l$ space separated integers representing the choices of sock colors for each leg in order. Each integer $i$ in this list must be in the range ($1 \leq i \leq m$).

Sample Input 1 Sample Output 1
8 4 5
5
4 1 3 1 4 3 2 1
3 2 1 2 1 5 4 5
Sample Input 2 Sample Output 2
8 1 5
-1
CPU Time limit 1 second
Memory limit 1024 MB
Author
Nikil Roashan Selvam
Source CodeSprintLA 2020 (UCLA ACM-ICPC)
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in