시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB93191442.424%

문제

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

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

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

입력

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

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

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

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

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

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

출력

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

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

예제 입력 1

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

예제 출력 1

NO
YES
W3sicHJvYmxlbV9pZCI6IjkyNzUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxYTBcdWIwN2NcdWM2NDAgXHVjMGMxXHVhZGZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjOWMwXHVhZTA4IFx1YzBhY1x1YzU0NVx1ZDU1YyBcdWQxYTBcdWIwN2NcdWI0ZTRcdWM1ZDBcdWFjOGMgXHVjNzA0XHVkNjExXHViYzFiXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViMmU0XHVkNTg5XHVkNzg4XHViM2M0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM4MGFcdWM3NDAgXHVjMmRjXHVjODA4IFx1ZDNiOFx1Yzc1OFx1YzgxMCBcdWM1NDRcdWI5NzRcdWJjMTRcdWM3NzRcdWQyYjhcdWI4NWMgXHVjNWI0XHViOWM4XHVjNWI0XHViOWM4XHVkNTVjIFx1YjNjOFx1Yzc0NCBcdWJhYThcdWM3NDAgXHViMzU1XHViZDg0XHVjNWQwIFx1YzlkMVx1YzVkMCBcdWNkMDhcdWFjZTBcdWMxMzFcdWIyYTUmbmJzcDtcdWFjMTBcdWMyZGNcdWNlNzRcdWJhNTRcdWI3N2NcdWI5N2MgXHVjMTI0XHVjZTU4XHVkNTYwIFx1YzIxOFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCZuYnNwO1x1Y2U3NFx1YmE1NFx1Yjc3Y1x1YjI5NCBcdWI5ZTRcdWM2YjAgXHVjMTJjXHVjMTM4XHVkNTU4XHVhYzhjIFx1YzYwMVx1YzBjMVx1Yzc0NCBcdWJkODRcdWMxMWRcdWQ1NThcdWM1ZWMgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWM4MTBcdWFjZmMgXHVjMTIwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWM2MDFcdWMwYzFcdWM3NDQgXHVjODA0XHVjMWExXHVkNTc0IFx1YzkwMFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWM3NzQgXHVjODEwXHVhY2ZjIFx1YzEyMFx1YjRlNFx1Yjg1Y1x1YjI5NCBcdWM5YzBcdWFlMDggXHVjOWQxXHVjNWQwJm5ic3A7XHVkMWEwXHViMDdjXHVhYzAwIFx1YjRlNFx1YzViNFx1YzY1NFx1YjI5NFx1YzljMCBcdWM1NDhcdWM4MDRcdWQ1NWNcdWM5YzBcdWM3NTggXHVjNWVjXHViZDgwXHViOTdjJm5ic3A7XHViYTg1XHVkNjU1XHVkNzg4IFx1YWQ2Y1x1YmQ4NFx1ZDU2MCBcdWMyMThcdWFjMDAgXHVjNWM2XHVhZTMwJm5ic3A7XHViNTRjXHViYjM4XHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWI5YzhcdWM3NGMgXHViMTkzXHVhY2UwIFx1YzdhMFx1Yzc0NCBcdWM3OTggXHVjMjE4XHVhYzAwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjQ1MCBcdWFjMDBcdWM5YzAmbmJzcDtcdWMwYWNcdWMyZTRcdWM3NDQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViYWE4XHViNGUwIFx1ZDFhMFx1YjA3Y1x1YjI5NCBcdWIxMjQgXHVhYzFjXHVjNzU4IFx1YmMxY1x1Yzc0NCBcdWFjMTZcdWFjZTAgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWFkZjggXHViMTI0IFx1YWMxY1x1Yzc1OCBcdWJjMWNcdWM3NDQgXHVjNzg3XHViMjk0IFx1YmFiOFx1ZDFiNVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjODFjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yjk3YyBcdWM3MDRcdWQ1NzQgXHVhYzEwXHVjMmRjIFx1Y2U3NFx1YmE1NFx1Yjc3Y1x1YWMwMCBcdWQzZWNcdWNjMjlcdWQ1NWMgXHVjNjAxXHVjMGMxXHVjNWQwIFx1ZDFhMFx1YjA3Y1x1YWMwMCBcdWM3ODhcdWM3NDQgXHVhYzAwXHViMmE1XHVjMTMxXHVjNzc0IFx1Yzc4OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWQzMTBcdWM4MTVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU3NFx1YzhmY1x1YjNjNFx1Yjg1ZCBcdWQ1NThcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCZuYnNwO1x1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCBuXHVhY2ZjIG1cdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgbiAmbGU7IDEwIDAwMCwgMCAmbGU7IG0gJmxlOyAyMCAwMDApPFwvcD5cclxuXHJcbjxwPm5cdWM3NDAgXHVjNjAxXHVjMGMxXHVjNWQwIFx1YjRmMVx1YzdhNVx1ZDU1YyBcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViYTcwLCBtXHVjNzQwIFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBtXHVjOTA0XHVjNWQ0IFx1YjQ1MCBcdWM4MTVcdWMyMTggeFx1YzY0MCB5XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMSAmbGU7IHgsIHkgJmxlOyBuKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWIyOTQgeFx1YmM4OFx1YzlmOCBcdWM4MTBcdWFjZmMgeVx1YmM4OFx1YzlmOCBcdWM4MTBcdWM3NDQgXHVjOWMxXHVjODExJm5ic3A7XHVjNzg3XHViMjk0IFx1YzEyMFx1YmQ4NFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTRcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQmbmJzcDtcdWM1YjRcdWI1YTQgXHViNDUwIFx1YzgxMFx1YjNjNCBcdWI0NTAgXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWMxMjBcdWJkODRcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAsIFx1YzViNFx1YjVhNCBcdWM4MTBcdWIzYzQgXHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1YWNmYyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjNzg1XHViODI1XHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHViOWNjXHVjNzdjIFx1ZDFhMFx1YjA3Y1x1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NjAgXHVhYzAwXHViMmE1XHVjMTMxXHVjNzc0IFx1Yzc4OFx1YjJlNFx1YmE3NCAmcXVvdDtZRVMmcXVvdDsgXHViOTdjLCBcdWQxYTBcdWIwN2NcdWFjMDAgXHVjNWM2XHViMmU0XHViYTc0ICZxdW90O05PJnF1b3Q7IFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LiBcdWI5Y2NcdWM3N2MgXHVjNjAxXHVjMGMxXHVjNzc0IFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjMGMxXHVkMGRjXHViOTdjIFx1YzcyMFx1YzljMFx1ZDU1OFx1YmE3MCZuYnNwO1x1YmE4NyBcdWFjMWNcdWM3NTggXHVjODEwXHVhY2ZjIFx1YzEyMFx1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NThcdWFjZTAgXHVjODE1XHVkNjU1XHVkNzg4IDRcdWFjMWNcdWM3NTggXHViYzFjXHVjNzQ0IFx1YWMwMFx1YzljNCBcdWJhYjhcdWQxYjVcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1ZDFhMFx1YjA3Y1x1YjI5NCBcdWM4NzRcdWM3YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjAxXHVjMGMxXHVjNzc0IFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YmFhOFx1YjRlMCBcdWI0NTAgXHVjODEwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWQ2MzlcdWM3NDAgXHVhZGY4IFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWMxMjBcdWM3NDQgXHVkMWI1XHVkNTc0IFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YmE3MCwgXHViYzFjXHVjNzc0XHViNzdjXHViMjk0IFx1YWM4M1x1Yzc0MCZuYnNwO1x1YzgxNVx1ZDY1NVx1ZDc4OCBcdWQ1NThcdWIwOThcdWM3NTggXHViMmU0XHViOTc4IFx1YzgxMFx1YWNmY1x1YjljYyBcdWM1ZjBcdWFjYjBcdWI0MThcdWJhNzAgXHViMmU4IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWMxMjBcdWJkODRcdWM3M2NcdWI4NWMgXHVjOWMxXHVjODExIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVkNTVjIFx1YzgxMFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiOTI3NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZ1cnJ5IE51aXNhbmNlIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBvcmRlciB0byBwcm90ZWN0IGhpbXNlbGYgZnJvbSBldmlsIGJ1bm5pZXMsIEZyZWRkeSBkZWNpZGVkIHRvIGluc3RhbGwgYW4gYXV0b21hdGljIHN5c3RlbSB0byBkZXRlY3QgdGhlbSBpbiBwaWN0dXJlcyBmcm9tIHN1cnZlaWxsYW5jZSBjYW1lcmFzLiBTb3BoaXN0aWNhdGVkIHNvZnR3YXJlIGRldGVjdHMgaW1wb3J0YW50IHBvaW50cyBpbiB0aGUgcGljdHVyZSBhbmQgbGluZXMgYmV0d2VlbiB0aGVtLiBVbmZvcnR1bmF0ZWx5LCB0aGUgdGVycmFpbiBpbiB0aGUgcGljdHVyZXMgaXMgcXVpdGUgdmFyaWVkIGFuZCBsb3Qgb2YgdGhlIHBvaW50cyBhbmQgbGluZXMgYXJlIGFjdHVhbGx5IG5vdCBidW5uaWVzLjxcL3A+XHJcblxyXG48cD5Zb3UgaGF2ZSBtYWRlIHRoZSBmb2xsb3dpbmcgb2JzZXJ2YXRpb246IEVhY2ggYnVubnkgaGFzIGZvdXIgcGF3cyBhbmQgYSBib2R5IGpvaW5pbmcgdGhlbS4gQmFzZWQgb24gdGhpcyBvYnNlcnZhdGlvbiwgd3JpdGUgYSBwcm9ncmFtIHRvIGRlY2lkZSB3aGV0aGVyIGEgZ2l2ZW4gcGljdHVyZSBjYW4gcG9zc2libHkgY29udGFpbiBhIGJ1bm55LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIHNldmVyYWwgdGVzdCBjYXNlcy4gVGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBuIGFuZCBtICgwICZsZTsgbiAmbGU7IDEwIDAwMCwgMCAmbGU7IG0gJmxlOyAyMCAwMDApLCBnaXZpbmcgdGhlIG51bWJlciBvZiBwb2ludHMgYW5kIGxpbmVzIGluIHRoZSBpbWFnZSwgcmVzcGVjdGl2ZWx5LiBFYWNoIG9mIHRoZSBtIGZvbGxvd2luZyBsaW5lcyBjb250YWlucyB0d28gZGlzdGluY3QgaW50ZWdlcnMgeCBhbmQgeSAoMSAmbGU7IHgsIHkgJmxlOyBuKSwgaW5kaWNhdGluZyB0aGF0IHRoZSBwb2ludHMgeCBhbmQgeSBhcmUgZGlyZWN0bHkgam9pbmVkIGJ5IGEgbGluZS4gWW91IG1heSBhc3N1bWUgdGhhdCBlYWNoIHBhaXIgb2YgcG9pbnRzIGlzIGpvaW5lZCBieSBhdCBtb3N0IG9uZSBkaXJlY3QgbGluZSBhbmQgdGhhdCBubyBwb2ludCBpcyBkaXJlY3RseSBqb2luZWQgd2l0aCBpdHNlbGYuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggaW5wdXQgaW5zdGFuY2UsIG91dHB1dCAmbGRxdW87WUVTJnJkcXVvOyBpZiB0aGUgcGljdHVyZSBjYW4gY29udGFpbiBhIGJ1bm55LCBhbmQgJmxkcXVvO05PJnJkcXVvOyBvdGhlcndpc2UuIFRoZSBwaWN0dXJlIGNhbiBjb250YWluIGEgYnVubnkgaWYgaXQgaXMgcG9zc2libGUgdG8gcmVtb3ZlIHNvbWUgb2YgdGhlIHBvaW50cyBhbmQgbGluZXMgc28gdGhhdCB0aGUgcmVzdWx0aW5nIGltYWdlIGlzIGNvbm5lY3RlZCBhbmQgaGFzIGV4YWN0bHkgNCBwYXdzLjxcL3A+XHJcblxyXG48cD5UaGUgaW1hZ2UgaXMgc2FpZCB0byBiZSBjb25uZWN0ZWQgaWYgKGFuZCBvbmx5IGlmKSBlYWNoIHR3byBwb2ludHMgYXJlIGpvaW5lZCB3aXRoIGVhY2ggb3RoZXIgYnkgb25lIG9yIG1vcmUgc3VjY2Vzc2l2ZSBsaW5lcy4gQSBwYXcgaXMgYSBwb2ludCB3aGljaCBpcyBkaXJlY3RseSBqb2luZWQgd2l0aCBleGFjdGx5IG9uZSBvdGhlciBwb2ludC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d