여행

김 씨는 여행사에서 일한다. 해외에 있는 한 고객이 여행 계획을 세워 달라고 부탁했다. 이 고객은 꽃이 활짝 핀 유명한 길 두 개를 꼭 지나가고 싶어 한다. 여행은 다음과 같이 진행된다. 고객은 어떤 도시로 비행기를 타고 들어와 차를 빌린 뒤, 경로를 따라 운전하고, 출발한 바로 그 도시로 돌아온다. 고객은 같은 도시를 두 번 지나거나 같은 길을 두 번 지나는 것을 싫어하고, 통행료를 받는 유료 도로도 절대 지나고 싶어 하지 않는다. 경로에 포함되는 도시의 수는 상관없다. 이 모든 조건을 만족하는 여행 계획을 세울 수 있는지 판별하는 프로그램을 작성하라.

예를 들어 그림 1의 지도를 보자. 원은 도시를, 두 원을 잇는 선은 두 도시 사이의 길을 나타낸다. 굵은 선 두 개는 고객이 지나고 싶어 하는 유명한 길이고, 점선은 유료 도로이다.

그림 1

그림 1(a)에서는 1 → 2 → 4 → 5 → 3 → 1 이나 2 → 3 → 5 → 4 → 2 와 같은 계획을 세울 수 있다. 그림 1(b)에서는 조건을 만족하는 계획을 세울 수 없다.

지도와 유명한 길 두 개, 그리고 유료 도로들이 주어질 때, 조건을 만족하는 여행 계획이 존재하는지 판별하라.

입력의 첫 줄에는 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

첫 줄에는 두 정수 $N$과 $M$이 주어진다 ($5 \le N \le 1000$). 각각 도시의 수와 길의 수를 뜻한다. 이어지는 $M$개의 줄에는 각각 두 정수가 주어지며, 길로 직접 연결된 두 도시를 나타낸다. 그다음 두 줄에는 각각 고객이 지나고 싶어 하는 길(유명한 길 두 개)이 한 줄에 하나씩 주어진다. 그다음 줄에는 유료 도로의 수 $F$가 주어지고 ($0 \le F \le M$), 이어지는 $F$개의 줄에 각각 유료 도로가 하나씩 주어진다.

도시는 $1$번부터 $N$번까지 번호가 매겨져 있다. 두 도시 사이에는 길이 최대 한 개만 있다. 유명한 길 두 개는 유료 도로가 아니다.

각 테스트 케이스마다 한 줄을 출력한다. 조건을 만족하는 여행 계획이 존재하면 YES를, 그렇지 않으면 NO를 출력한다.