Face Recognition Algorithm

시간 제한2초메모리 제한512 MB

요약

연결된 그래프의 평면 직선 임베딩이 주어질 때, 바깥면을 포함한 모든 면이 정확히 세 변으로 둘러싸여 있는지 판정한다.

난이도: 어려움10점 중 8점
유형: 기하, 그래프, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

평면 위에 n개의 점을 찍고 이 점들을 잇는 m개의 선분을 그렸다. 어떤 선분도 양 끝점이 아닌 점을 지나지 않으며, 두 선분은 공통 끝점 외의 점에서 만나지 않는다. 또한 한 점에서 선분만 따라 이동하면 다른 모든 점에 도달할 수 있다. n개의 점은 모두 서로 다른 위치에 있다.

그렇다. 이는 정점 n개와 간선 m개를 가진 연결 그래프의 평면 매장이다. 여러분의 임무는 이 그래프의 모든 면이, 바깥면을 포함하여, 삼각형인지 확인하는 것이다. 어떤 면이 삼각형이라는 것은 정확히 3개의 간선으로 둘러싸여 있다는 뜻이다. 어떤 간선의 양쪽이 모두 같은 면에 속하면, 그 간선은 두 번 센다.

최고를 향해 나아가라! 여러분의 알고리즘이 가질 수 있는 최선의 복잡도보다 못한 것은 허용하지 마라.

입력

첫째 줄에 두 정수 n과 m이 주어진다 (3 ≤ n ≤ 105, n − 1 ≤ m ≤ 3 · 105). 각각 점의 개수와 선분의 개수이다.

다음 n개의 줄에는 점의 좌표가 주어진다. 모든 좌표의 절댓값은 109를 넘지 않는다. n개의 점은 모두 서로 다른 위치에 있다.

다음 m개의 줄에는 두 정수 u와 v가 주어진다 (1 ≤ u, v ≤ n, u ≠ v). 이는 선분으로 연결된 두 점의 번호이다. 같은 두 점을 잇는 선분은 두 개 이상 주어지지 않는다.

입력은 모든 간선을 직선 선분으로 그린 연결 그래프의 올바른 평면 매장을 나타낸다.

출력

주어진 그래프의 모든 면이, 바깥면을 포함하여, 삼각형이면 “YES”를, 아니면 “NO”를 출력한다.

예제5

예제 1
입력
```
3 3
0 0
1 0
0 1
1 2
2 3
3 1
```
예상 출력
```
YES
```
예제 2
입력
```
4 4
0 0
3 0
0 3
1 1
1 2
2 3
3 1
1 4
```
예상 출력
```
NO
```

예제 3

입력

예상 출력

YES

예제 4

입력

예상 출력

NO

예제 5
입력
```
4 3
0 0
0 1
1 1
1 2
1 2
2 3
3 4
```
예상 출력
```
NO
```