[ITK22 Training] Duyệt bò

Xem PDF

Nộp bài


Điểm: 10 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 512M

Tác giả:
Dạng bài

Cho đồ thị vô hướng gồm \(N\) đỉnh và \(M\) cạnh, cạnh thứ \(i\) nối hai đỉnh \(u_i\) và \(v_i\). Một thành phần liên thông được gọi là xấu nếu số lượng đỉnh và cạnh chứa trong nó không bằng nhau. Một đồ thị được gọi là đẹp nếu nó không chứa thành phần liên thông xấu nào. Bạn hãy lập trình xác định xem đồ thị đã cho có đẹp không nhé!


Input

Dòng đầu chứa hai số nguyên \(N\) và \(M\). (\(1\leq N\leq 2\cdot 10^5\), \(0\leq M\leq 2\cdot 10^5\))

Dòng thứ \(i\) trong \(M\) dòng tiếp theo chứa hai số nguyên \(u_i\) và \(v_i\). (\(1\leq u_i \leq v_i\leq N\))


Output

In ra Yes nếu đồ thị đã cho là một đồ thị đẹp, ngược lại in ra No.


Ví dụ

Sample input 1
4 4
2 4
1 1
4 2
3 3
Sample output 1
Yes
Giải thích

Đồ thị đã cho có thể là một đa đồ thị. Có ba thành phần liên thông trong đồ thị này: thành phần đầu tiên chứa đỉnh \(1\), thành phần thứ hai chứa đỉnh \(2\) và đỉnh \(4\), thành phần thứ ba chứa đỉnh \(3\). Cả ba thành phần liên thông đều có số đinh bằng với số cạnh.

Sample input 2
5 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1
Sample output 2
No
Giải thích

Đồ thị gồm một thành phần liên thông duy nhất. Thành phần liên thông này có số đỉnh và số cạnh không bằng nhau:

Đồ thị đã cho