#46 tree

Statement

KO EN

양의 정수 $X, Y, L$ 이 주어진다. 다음 조건을 모두 만족하는 트리가 존재하는지 판단하고, 존재한다면 하나를 구성하여라. 루트의 깊이는 $0$ 으로 정의한다.

트리는 $X + Y$ 개의 정점으로 이루어져 있으며, 각 정점에는 $1, 2, \cdots, X + Y$ 의 번호가 하나씩 붙어 있다.
루트는 $1$ 번 정점이다.
깊이가 홀수인 정점의 개수는 $X$ 이다.
깊이가 짝수인 정점의 개수는 $Y$ 이다.
차수가 $1$ 인 정점의 개수는 $L$ 이다.

트리를 정확히 구성하지 못하더라도 존재 여부를 올바르게 판별하면 $30\%$ 의 점수를 받을 수 있다. 자세한 내용은 Scoring 섹션을 참고하라.

Input

입력은 다음과 같은 형식으로 주어진다.

$X \ Y \ L$

Output

트리가 존재하는 경우 다음과 같은 형식으로 출력하라.

$\text{YES}$ $U_1 \ V_1$ $U_2 \ V_2$ $\vdots$ $U_{X+Y-1} \ V_{X+Y-1}$

여기서 $(U_i, V_i)$ 는 트리의 $i$ ( $1 \leq i \leq X + Y - 1$ )번째 간선을 의미하며, 다음 조건을 만족해야 한다.

$1 \leq U_i \leq X + Y$ ( $1 \leq i \leq X + Y - 1$ ).
$1 \leq V_i \leq X + Y$ ( $1 \leq i \leq X + Y - 1$ ).
$U_i \neq V_i$ ( $1 \leq i \leq X + Y - 1$ ).

트리가 존재하지 않는 경우 다음과 같은 형식으로 출력하라.

$\text{NO}$

Constraints

$1 \leq X \leq 100 \ 000$ .
$1 \leq Y \leq 100 \ 000$ .
$1 \leq L \leq X + Y$ .

Subtasks

#	Score	Constraints
1	3	$X = 1$ .
2	3	$Y = 1$ .
3	4	$X = 2$ .
4	4	$Y = 2$ .
5	3	$L = 1$ .
6	4	$L = 2$ .
7	5	$X = Y$ .
8	5	$X = Y - 1$ .
9	5	$L \geq X + Y - 2$ .
10	18	조건을 만족하는 트리가 존재함이 보장된다.
11	20	$X \leq 1 \ 000, Y \leq 1 \ 000$ .
12	26	추가적인 제약조건이 없다.

Scoring

각 테스트케이스의 점수는 다음과 같이 부여된다.

존재 여부 판별이 올바르지 않으면 $0$ 점.
존재 여부 판별은 올바르지만 답이 YES인 경우 트리가 올바르지 않으면 해당 서브태스크 배점의 $30\%$ (트리를 출력하지 않아도 된다.)
판별 여부와 트리가 모두 올바르면 해당 서브태스크 배점의 $100\%$ .

각 서브태스크의 점수는 해당 서브태스크에 속한 모든 테스트케이스의 점수 중 최솟값이다.

Samples

Sample 1

Input

1 1 1

Output

NO

이 예제는 서브태스크 1, 2, 5, 7, 11, 12의 조건을 만족한다.

Sample 2

Input

2 2 2

Output

YES
2
3
4

이 예제는 서브태스크 3, 4, 6, 7, 9, 10, 11, 12의 조건을 만족한다.

Sample 3

Input

2 3 2

Output

YES
2
3
4
5

이 예제는 서브태스크 3, 6, 8, 10, 11, 12의 조건을 만족한다.

Sample 4

Input

3 3 4

Output

YES
2
3
4
5
6

이 예제는 서브태스크 7, 9, 10, 11, 12의 조건을 만족한다.

Sample 5

Input

5 2 2

Output

NO

이 예제는 서브태스크 4, 6, 11, 12의 조건을 만족한다.

Yet Another Tree Problem 2

Statement

Input

Output

Constraints

Subtasks

Scoring

Samples