Mô tả và yêu cầu

Bậc của đỉnh
Trong Lý thuyết đồ thị, bậc của một đỉnh v là số cạnh liên thuộc với v (trong đó, khuyên
được tính hai lần). Bậc của v được ký hiệu là deg(v). Trong một đồ thị có hướng, bậc trong
của đỉnh v là số cung kết thúc tại v, còn bậc ngoài là số cung xuất phát từ v. Bậc trong và
bậc ngoài của v được ký hiệu là deg+(v) và deg-(v). Do đó, deg(v)= deg+(v) + deg-(v). Đỉnh
v với deg(v)=0 được gọi là đỉnh cô lập. Đỉnh v có deg(v)=1 được gọi là lá. Nếu mỗi đỉnh
của đồ thị đều có bậc bằng nhau và bằng k thì đồ thị được gọi là đồ thị chính quy bậc k và
đồ thị được coi là có bậc bằng k. Đỉnh v có deg+(v)=0 được gọi là đỉnh phát, đỉnh có deg-
(v)=0 là đỉnh thu.
Yêu cầu: Cho đồ thị vô hướng G có n đỉnh và m cạnh, hãy tìm bậc của tất cả các đỉnh của
đồ thị.
Dữ liệu: Vào từ file văn bản BAC.INP gồm
• Dòng 1 chứa 2 số nguyên n, m (1 ≤ n ≤ 1000; 1 ≤ m ≤ 5000);
• m dòng tiếp theo, mỗi dòng chứa 2 số nguyên i, j mô tả một cạnh của đồ thị G (1 ≤
i, j ≤ n).
Kết quả: Ghi ra file văn bản BAC.OUT chứa n dòng, mỗi dòng thứ i chứa bậc của đỉnh
thứ i (deg(i)). Ví dụ:
BAC.INP BAC.OUT
6 11 4
1 2 4
1 4 3
1 5 4
1 6 4
2 3 3
2 5
2 6
3 4
3 5
4 5
4 6