시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 55 6 6 31.579%

문제

상근이는 지금 사악한 토끼들에게 위협받고 있다. 다행히도 상근이는 젊은 시절 편의점 아르바이트로 어마어마한 돈을 모은 덕분에 집에 초고성능 감시카메라를 설치할 수가 있다. 이 카메라는 매우 섬세하게 영상을 분석하여 몇 개의 점과 선으로 이루어진 영상을 전송해 준다. 하지만, 이 점과 선들로는 지금 집에 토끼가 들어왔는지 안전한지의 여부를 명확히 구분할 수가 없기 때문에 상근이는 마음 놓고 잠을 잘 수가 없다.

상근이는 두 가지 사실을 알고 있다. 모든 토끼는 네 개의 발을 갖고 있으며, 그 네 개의 발을 잇는 몸통으로 이루어져 있다는 것이다.

이제 상근이를 위해 감시 카메라가 포착한 영상에 토끼가 있을 가능성이 있는지를 판정하는 프로그램을 작성해주도록 하자.

입력

입력은 여러 테스트 케이스로 이루어져 있다.

테스트 케이스의 첫 줄에는 두 정수 n과 m이 공백으로 구분되어 주어진다. (0 ≤ n ≤ 10 000, 0 ≤ m ≤ 20 000)

n은 영상에 등장한 점의 갯수이며, m은 선의 갯수이다.

다음 m줄엔 두 정수 x와 y가 주어진다. (1 ≤ x, y ≤ n)

이는 x번째 점과 y번째 점을 직접 잇는 선분이 존재한다는 의미이다.

모든 테스트 케이스에 대해 어떤 두 점도 두 개 이상의 선분으로 연결되어 있지 않으며, 어떤 점도 자기 자신과 연결되어 있지 않다.

출력

각각의 입력에 대해, 만일 토끼가 존재할 가능성이 있다면 "YES" 를, 토끼가 없다면 "NO" 를 출력하면 된다. 만일 영상이 연결되어 있는 상태를 유지하며 몇 개의 점과 선을 제거하고 정확히 4개의 발을 가진 몸통을 만들 수 있다면, 토끼는 존재할 수 있다.

영상이 연결되어 있다는 것은 모든 두 점이 하나 혹은 그 이상의 선을 통해 연결되어 있다는 것을 의미하며, 발이라는 것은 정확히 하나의 다른 점과만 연결되며 단 하나의 선분으로 직접 연결되어 있는 한 점을 의미한다.

예제 입력

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

예제 출력

NO
YES

힌트