마우가 장인

문제

마우가 장인 현석이는 오늘도 오버워치에서 돌격 역할을 맡아 경쟁전을 준비한다. 현석이가 선택한 영웅은 당연히 마우가다.

오버워치에서는 영웅 사이의 상성이 중요하다. 특정 영웅을 상대하는 데 유리한 영웅을 그 영웅의 카운터라고 부른다. 아무리 마우가에 자신 있는 현석이라도, 회복을 막는 생체 수류탄을 던지는 아나를 만나면 좀처럼 힘을 쓰지 못한다.

하지만 상대 팀이 마우가의 카운터만 선택한다고 해서 현석이가 포기할 리 없다. 우리 팀의 공격 영웅과 지원 영웅이 상대를 견제해 주면 되기 때문이다. 현석이는 필요하다면 팀원들에게 다른 영웅을 선택해 달라고 부탁할 생각이다. 그러기 전에, 우선 현재 조합으로도 괜찮을지 확인해 보려고 한다.

현석이는 조합을 살펴보다가 같은 영웅끼리 맞붙는 상황도 떠올렸다. 자리야를 상대하려고 맞자리야를 선택하는 경우가 있지만, 같은 영웅이라는 이유만으로 언제나 서로의 카운터가 되는 것은 아니다. 현석이가 보기에는 모이라끼리 만나면 서로 쉽게 제압하지 못할 수도 있고, 캐서디(옛 이름 맥크리)끼리는 정확한 사격으로 서로를 위협할 수도 있다. 따라서 현석이는 자기 자신을 카운터할 수 있는지도 영웅마다 따로 기록하기로 했다.

이 문제에는 $1$번부터 $N$번까지 번호가 붙은 영웅이 있으며, $1$번 영웅은 마우가다. 현석이가 분석하는 조합에서는 각 팀원이 같은 영웅들을 선택할 수도 있고, 양 팀이 같은 영웅을 선택할 수도 있다.

현석이는 상대 팀의 각 영웅에 대해, 그 영웅의 카운터가 우리 팀에 한 명 이상 있으면 현재 조합으로 괜찮다고 생각한다. 우리 팀의 영웅 한 명이 상대 팀의 여러 영웅의 카운터여도 된다.

카운터 관계는 입력으로 주어지는 것만 인정한다. 영웅 $a$가 영웅 $b$의 카운터라고 해서 $b$가 $a$의 카운터인 것은 아니다. 같은 영웅끼리도 $(a, a)$가 주어졌을 때에만 $a$가 $a$의 카운터다. 또한 $a$가 $b$의 카운터이고 $b$가 $c$의 카운터여도, $a$가 $c$의 카운터인 것은 아니다. 실제 게임의 상성이나 역할 구분은 별도로 고려하지 않는다.

영웅 사이의 카운터 관계와 양 팀이 선택한 영웅이 주어질 때, 현재 조합이 현석이의 기준을 만족하는지 판단해 보자.

입력

첫째 줄에 영웅의 수 $N$과 카운터 관계의 수 $M$이 공백으로 구분되어 주어진다. $(5 \le N \le 100; 0 \le M \le N^2)$

다음 $M$개의 줄에 두 정수 $a_i$와 $b_i$가 공백으로 구분되어 주어진다. 이는 영웅 $a_i$가 영웅 $b_i$의 카운터라는 뜻이다. $(1 \le a_i, b_i \le N)$ $a_i=b_i$도 가능하며, 같은 순서쌍 $(a_i, b_i)$은 두 번 이상 주어지지 않는다.

다음 줄에 우리 팀이 선택한 영웅의 번호 $u_1, u_2, u_3, u_4, u_5$가 공백으로 구분되어 주어진다. 같은 번호가 여러 번 나올 수 있으며, 현석이가 선택한 영웅은 마우가이므로 $u_1=1$이다. $(1 \le u_i \le N)$

다음 줄에 상대 팀이 선택한 영웅의 번호 $v_1, v_2, v_3, v_4, v_5$가 공백으로 구분되어 주어진다. 같은 번호가 여러 번 나올 수 있다. $(1 \le v_i \le N)$

출력

현재 조합이 현석이의 기준을 만족하면 YES, 그렇지 않으면 NO를 출력한다.

예제 1

10 6
1 6
1 7
2 8
3 9
4 10
6 1
1 2 3 4 5
6 7 8 9 10

출력 1

YES

예제 2

10 6
1 6
1 7
2 8
3 9
10 4
6 1
1 2 3 4 5
6 7 8 9 10

출력 2

NO

예제 3

5 5
1 1
1 2
1 3
1 4
1 5
1 1 1 1 1
1 2 3 4 5

출력 3

YES

예제 4

5 4
1 2
1 3
1 4
1 5
1 1 1 1 1
1 2 3 4 5

출력 4

NO