33706번 - 오름차순 최단 경로

문제

정점 $N$개와 간선 $M$개로 이루어진 방향 없는 그래프가 주어진다. 이 그래프의 간선의 비용은 아직 정해지지 않았다. 아래의 조건을 만족하도록 그래프의 간선의 비용을 정할 수 있는지 판별해 보자.

• 간선의 비용은 양의 정수여야 한다.
• 모든 $\left(i, j\right)$쌍에 대해서 $\left(1 \lt i \lt j\leq N\right),ドル 정점 1ドル$에서 정점 $i$로의 최단 경로의 비용이 정점 1ドル$에서 정점 $j$로의 최단 경로의 비용보다 작아야 한다.

최단 경로의 구체적인 정의는 아래 힌트에 나와 있다.

입력

첫째 줄에 정점의 개수 $N$과 간선의 개수 $M$이 공백으로 구분되어 주어진다. $(2\leq N\leq 200,円 000;$ 1ドル\leq M\leq 200,円 000)$

이어지는 $M$개의 줄에 정수 $a$와 $b$가 공백으로 구분되어 주어진다. 이는 정점 $a$와 정점 $b$를 연결하는 간선이 존재함을 의미한다. $\left(1\leq a \lt b\leq N\right)$

주어진 그래프의 모든 정점이 연결되어 있고, 중복된 간선이 주어지지 않음이 보장된다.

출력

주어진 조건을 만족하도록 그래프의 간선의 비용을 정해줄 수 있다면 YES를, 그렇지 않다면 NO를 출력한다.

제한

힌트

정점 $a$에서 정점 $b$로의 최단 경로란 정점 $a$에서 정점 $b$로 이동하는 경로 중 가장 짧은 경로를 의미합니다.

구체적으로 $V_1 = a, V_K = b$이고 $V_i$와 $V_{i+1}$를 연결하는 간선이 존재할 때, $V_i$와 $V_{i+1}$를 연결하는 간선의 비용의 합이 최소인 수열 $V$를 의미합니다. $\left(1\leq i\leq K-1\right)$

최단 경로의 비용이란 최단 경로에 사용된 간선의 비용의 합을 의미합니다.