시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 93 | 19 | 14 | 42.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개의 발을 가진 몸통을 만들 수 있다면, 토끼는 존재할 수 있다.
영상이 연결되어 있다는 것은 모든 두 점이 하나 혹은 그 이상의 선을 통해 연결되어 있다는 것을 의미하며, 발이라는 것은 정확히 하나의 다른 점과만 연결되며 단 하나의 선분으로 직접 연결되어 있는 한 점을 의미한다.
2 1 1 2 5 4 1 2 1 3 1 4 1 5
NO YES
ICPC > Regionals > Europe > Central European Regional Contest > CTU Open Contest > CTU Open Contest 2013 N번