시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 8 2 2 25.000%

문제

We need to ship N capsules containing different potentially hazardous chemicals using an aircraft. The aircraft has one cargo compartment on the left with free space for L capsules and one cargo compartment on the right with free space for R capsules. According to the safety regulations, some capsules conflict with each other and cannot be loaded into the same cargo compartment (in case there is leakage and reaction). Given this information, your job is to determine whether all the capsules can be loaded into the aircraft.

입력

The input starts with a line containing four integers L, R, N and C, where L (0 ≤ L ≤ 2 000) is the capacity of the left cargo compartment, R (0 ≤ R ≤ 2 000) is the capacity of the right cargo compartment, N (0 ≤ N ≤ 2 000) is the number of capsules and C (0 ≤ C ≤ 200 000) is the number of conflicts.

The next C lines describe the conflicts. Each of these lines contain two integers X (0 ≤ X ≤ N − 1) and Y (0 ≤ Y ≤ N − 1 and X ≠ Y ) representing a pair of capsules that conflict with each other. Each pair of capsules that conflict only appear once in the input. The capsules are numbered from 0 to N − 1.

출력

Display Yes if all the capsules can be loaded into the aircraft and display No otherwise.

예제 입력 1

0 0 0 0

예제 출력 1

Yes

예제 입력 2

3 3 3 3
0 1
1 2
2 0

예제 출력 2

No

예제 입력 3

3 3 6 4
0 1
0 2
3 4
3 5

예제 출력 3

Yes

힌트