$B$ 끼 $B$ 끼 $A$ 끼 $A$ 끼 수열 찾기

시간 제한1초메모리 제한1024 MB

요약

A, B, N이 주어질 때 차이가 A 또는 B인 두 수의 쌍을 각각 정확히 한 번씩 인접하게 이어 붙인 수열을 구하고, 없으면 -1을 출력합니다.

난이도: 보통10점 중 6점
유형: 그래프, 구현
정답자: 아직 제출이 없습니다

문제

양의 정수 $A$ , $B$ , $N$ 이 주어진다. 집합 $S$ 를 다음과 같이 정의한다.

$S := \left\{ (x, y) \in \mathbb{Z}^2 \ \middle|\ y - x \in \{A, B\} \land 1 \le x < y \le N \right\}$

다음 조건을 만족하는 수열 $P$ 를 $B$ 끼 $B$ 끼 $A$ 끼 $A$ 끼 수열이라고 한다.

$1$ 이상 $N$ 이하의 모든 정수가 $P$ 에 한 개 이상 있으며, $P$ 는 $1$ 이상 $N$ 이하의 정수로만 구성된다.
모든 $1 \le i < |P|$ $1 \leq i < ∣ P ∣$ 에 대하여 $Q_i := (\min(P_i, P_{i+1}), \max(P_i, P_{i+1}))$ $Q_{i} := (min (P_{i}, P_{i + 1}), max (P_{i}, P_{i + 1}))$ 라고 하면 다음을 만족한다.
- $Q_i \in S$
- 모든 $s \in S$ 에 대하여 $Q_i = s$ 인 $i$ 가 존재한다.
- $i \ne j$ 이면 $Q_i \ne Q_j$ 이다.

$B$ 끼 $B$ 끼 $A$ 끼 $A$ 끼 수열이 존재하면 가능한 수열을 아무거나 하나 출력하고, 존재하지 않으면 -1을 출력한다. 수열은 수를 순서대로 나열한 것이어서 순서가 중요하고 같은 원소가 중복될 수 있다. 집합은 원소가 포함되는지만 따지므로 순서가 없고 같은 원소는 최대 한 번 포함된다.

입력

첫 번째 줄에 정수 $A$ , $B$ , $N$ ( $1 \le A, B, N \le 10^5$ )이 공백으로 구분되어 주어진다.

출력

$B$ 끼 $B$ 끼 $A$ 끼 $A$ 끼 수열이 있으면 첫 번째 줄에 수열의 길이를 출력한다. 없으면 -1을 출력한다.

수열이 존재하면 두 번째 줄에 수열의 수들을 차례대로 공백으로 구분하여 출력한다.

예제2

예제 1
입력
```
2 3 7
```
예상 출력
```
10
3 1 4 2 5 3 6 4 7 5
```
예제 2
입력
```
1 3 10
```
예상 출력
```
-1
```