화물 적재

시간 제한3초메모리 제한512 MB

요약

서로 충돌하는 두 캡슐은 같은 칸에 넣을 수 없을 때, 용량이 L과 R인 두 칸에 N개의 캡슐을 모두 나눠 넣을 수 있는지 판정한다.

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

문제

서로 다른 위험 화학 물질이 든 캡슐 $N$ 개를 항공기 한 대로 운송한다. 항공기에는 캡슐 $L$ 개가 들어가는 왼쪽 화물칸과 캡슐 $R$ 개가 들어가는 오른쪽 화물칸이 있다.

안전 규정에 따라 일부 캡슐 쌍은 같은 화물칸에 함께 실을 수 없다. 한쪽에서 물질이 새어 나와 다른 쪽과 반응할 위험이 있기 때문이다. 캡슐은 하나도 남기지 않고 두 화물칸 중 정확히 한 곳에 실어야 한다.

모든 캡슐을 항공기에 실을 수 있는지 판정하라.

입력

첫째 줄에 정수 네 개 $L$ , $R$ , $N$ , $C$ 가 주어진다. $L$ ( $0 \le L \le 2000$ )은 왼쪽 화물칸의 용량, $R$ ( $0 \le R \le 2000$ )은 오른쪽 화물칸의 용량, $N$ ( $0 \le N \le 2000$ )은 캡슐의 개수, $C$ ( $0 \le C \le 200000$ )는 충돌 쌍의 개수이다.

다음 $C$ 개 줄에는 충돌 정보가 한 줄에 하나씩 주어진다. 각 줄은 정수 두 개 $X$ 와 $Y$ ( $0 \le X \le N-1$ , $0 \le Y \le N-1$ , $X \ne Y$ )로 이루어지며, 캡슐 $X$ 와 캡슐 $Y$ 를 같은 화물칸에 실을 수 없다는 뜻이다. 충돌하는 캡슐 쌍은 입력에 한 번씩만 나온다. 캡슐의 번호는 $0$ 부터 $N-1$ 까지이다.

출력

모든 캡슐을 항공기에 실을 수 있으면 Yes를, 그렇지 않으면 No를 출력한다.

예제5

예제 1
입력
```
0 0 0 0
```
예상 출력
```
Yes
```
예제 2
입력
```
3 3 3 3
0 1
1 2
2 0
```
예상 출력
```
No
```
예제 3
입력
```
3 3 6 4
0 1
0 2
3 4
3 5
```
예상 출력
```
Yes
```
예제 4
입력
```
1 1 3 0
```
예상 출력
```
No
```
예제 5
입력
```
5 7 0 0
```
예상 출력
```
Yes
```