그래프의 정점 집합을 두 집합으로 나누었을 때, 같은 집합에 속한 두 정점 사이에는 간선이 존재하지 않도록 나눌 수 있는 그래프를 이분 그래프(Bipartite Graph)라고 한다.

다르게 말하면, 모든 간선의 두 끝점이 서로 다른 집합에 속하도록 정점들을 두 집합으로 나눌 수 있어야 한다.

무방향 그래프가 주어졌을 때, 이 그래프가 이분 그래프인지 판별하는 프로그램을 작성하시오.

그래프는 여러 개의 연결 요소로 나뉘어 있을 수 있으며, 간선과 연결되지 않은 정점도 존재할 수 있다.

입력

첫째 줄에 정점의 수 \(V\)와 간선의 수 \(E\)가 공백으로 구분되어 주어진다.

이어지는 \(E\)개의 줄에는 간선으로 연결된 두 정점 \(u\)와 \(v\)가 공백으로 구분되어 주어진다.

출력

주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 출력한다.

제한 사항

• \(1 \le V \le 1,000\)
• \(0 \le E \le \frac{V(V-1)}{2}\)
• 정점에는 \(1\)부터 \(V\)까지 번호가 매겨져 있다.
• 모든 간선은 방향이 없는 무방향 간선이다.
• 셀프 루프는 없다.
• 같은 두 정점을 연결하는 간선은 최대 한 개만 존재한다.
• 그래프는 연결되어 있지 않을 수 있다.

예제 입력 1

4 4
1 2
2 3
3 4
4 1

예제 출력 1

YES

예제 설명 1

정점 \(1,3\)을 한 집합에 넣고 정점 \(2,4\)를 다른 집합에 넣을 수 있으므로 이 그래프는 이분 그래프이다.

예제 입력 2

3 3
1 2
2 3
3 1

예제 출력 2

NO

예제 설명 2

세 정점이 사이클을 이룬다. 정점 \(1\)과 \(2\)를 서로 다른 집합에 넣고, 정점 \(2\)와 \(3\)도 서로 다른 집합에 넣으면 정점 \(1\)과 \(3\)은 같은 집합에 속하게 된다. 하지만 정점 \(1\)과 \(3\) 사이에도 간선이 있으므로 조건을 만족할 수 없다.