Loading...
$N$개의 정점과 $M$개의 간선으로 이루어진 단순 그래프가 주어진다. 이 그래프가 평면 그래프인지 판별하라.
평면 그래프란 간선들이 평면 위에서 서로 교차하지 않도록 그릴 수 있는 그래프를 뜻한다. 오일러 공식과 평면 그래프의 필요 조건인 $E \le 3V - 6$을 활용하여 판별하라.
첫째 줄에 정점의 개수 $N$과 간선의 개수 $M$이 공백으로 구분되어 주어진다.
둘째 줄부터 $M$개의 줄에 걸쳐 각 간선을 이루는 두 정점의 번호 $u$와 $v$가 공백으로 구분되어 주어진다.
주어진 그래프가 평면 그래프이면 YES, 아니면 NO를 출력하라.
4 6
1 2
1 3
1 4
2 3
2 4
3 4
YES
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
NO