/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 7 点
問題文
青木先生は生徒の高橋君に、単純な無向グラフを作る宿題を与えました。
無向グラフが単純であるとは、グラフが下記の 2 つの条件をともに満たすことをいいます。
- 多重辺が存在しない。すなわち、任意の 2 つの頂点 u, v について、u と v を結ぶ辺の本数は高々 1 本である。
- 自己ループが存在しない。すなわち、「v と v 自身を結ぶ辺は存在しない」が任意の頂点 v について成り立つ。
高橋君は作った無向グラフ G を次の形式でノートに書いて青木先生に提出します。
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
ここで、N は G の頂点数、M は G の辺数であり、 i = 1, 2, \ldots, M について u_i, v_i は「 G の i 番目の辺が頂点 u_i と頂点 v_i を結ぶ」ことを表します。
青木先生は、高橋君が提出したノートが単純な無向グラフを正しく表現しているかを判定します。 具体的には、高橋君のノートが次の 2 つの条件をともに満たすかを判定します。
- すべての i = 1, 2, \ldots, M について、1 \leq u_i \leq N かつ 1 \leq v_i \leq N 。
- 表現される無向グラフは単純。
青木先生の立場で、高橋君が提出したノートが上記の 2 つの条件をともに満たすかを判定してください。
制約
- 1 \leq N, M \leq 2 \times 10^5
- 1 \leq u_i, v_i \leq 2 \times 10^5
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
出力
高橋君が提出したノートが問題文中の 2 つの条件をともに満たすとき Yes を、そうでないなら No を出力せよ。
入力例 1
3 3 1 2 2 3 3 4
出力例 1
No
N = 3 かつ v_3 = 4 であるため、1 \leq v_3 \leq N を満たしません。
よって、No を出力します。
入力例 2
2 2 1 2 2 1
出力例 2
No
表現される無向グラフは、頂点 1 と頂点 2 を結ぶ辺を 2 本持つため、単純ではありません。
よって、No を出力します。
入力例 3
1 1 1 1
出力例 3
No
表現される無向グラフは、頂点 1 と頂点 1 自身を結ぶ自己ループを持つため、単純ではありません。
よって、No を出力します。
入力例 4
5 4 1 3 3 4 4 1 2 5
出力例 4
Yes
Score : 7 points
Problem Statement
Mr. Aoki gave Takahashi, his student, an assignment that asked him to make a simple undirected graph.
An undirected graph is simple when both of the following conditions are satisfied.
- There are no multi-edges. That is, for any two vertices u and v, there is at most one edge connecting u and v.
- There are no self-loops. That is, for any vertex v, there is no edge connecting v and v itself.
Takahashi writes his undirected graph G in the following format in his notebook and submits it to his teacher.
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
Here, N and M are the numbers of vertices and edges in G, respectively, and u_i and v_i for each i = 1, 2, \ldots, M means that the i-th edge connects Vertex u_i and Vertex v_i.
Mr. Aoki will check whether Takahashi's writing correctly describes a simple undirected graph. More accurately, the teacher will check whether both of the following are satisfied.
- 1 \leq u_i \leq N and 1 \leq v_i \leq N, for every i = 1, 2, \ldots, M.
- The undirected graph described is simple.
Put yourself in Mr. Aoki's shoes and check whether Takahashi's writing satisfies both conditions above.
Constraints
- 1 \leq N, M \leq 2 \times 10^5
- 1 \leq u_i, v_i \leq 2 \times 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
Output
If Takahashi's writing satisfies both of the conditions in the Problem Statement, print Yes; otherwise, print No.
Sample Input 1
3 3 1 2 2 3 3 4
Sample Output 1
No
Here we have N = 3 and v_3 = 4, which is in violation of 1 \leq v_3 \leq N.
Therefore, No should be printed.
Sample Input 2
2 2 1 2 2 1
Sample Output 2
No
This undirected graph has two edges connecting Vertex 1 and Vertex 2 and thus is not simple.
Therefore, No should be printed.
Sample Input 3
1 1 1 1
Sample Output 3
No
This undirected graph has a self-loop connecting Vertex 1 and itself and thus is not simple.
Therefore, No should be printed.
Sample Input 4
5 4 1 3 3 4 4 1 2 5
Sample Output 4
Yes