Yet Another Tree Problem 2

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

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

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

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

$X \ Y \ L$

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

$\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}$

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

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

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

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