한붓그리기는 그래프가 주어져있을 때, 동일한 선분을 지나지 않고 모든 선분을 지나가는 놀이이다.

하지만 한붓그리기의 규칙을 바꾸어서 주어진 선분 중에 여러번 지나가는 것이 허용되는 선분이 있을 때의 경우를 생각해보자. 이제 이러한 규칙에서 어떠한 그래프가 주어져있을 때, 한붓그리기가 가능한지 불가능한지를 알아보자.

입력

• 첫 번째 줄에는 전체 꼭지점의 수 N 이 주어진다. (꼭지점의 번호는 순서대로 1 번부터 N 번까지 이다.)
• 두 번째 줄에는 전체 선분의 수 M 이 주어진다.
• 다음 M 개의 줄에 걸쳐서 점 A 와 점 B 를 잇는 선분이 두 점의 번호로 주어진다.
• 그 다음 줄에는 여러 번 지나가는 것이 허용되는 선분의 수 P 가 주어진다.
• 다음 P 개의 줄에 걸쳐서 앞에서 주어진 선분 중 여러 번 지나가는 것이 허용되는 선분이 두 점의 번호로 주어진다.

출력

• 만약 주어진 그래프가 한붓그리기가 가능한 그래프라면 YES 를 출력한다.
• 만약 주어진 그래프가 한붓그리기가 불가능한 그래프라면 NO 를 출력한다.

입출력 예시

입력 

4
6
1 2
1 3
1 4
2 3
2 4
3 4
1
1 2

출력

YES

입출력 예시 보충설명

3-4-2-3-1-2-1-4 경로를 따라가면 모든 선분을 지날 수 있다.

출처: KangJ