Problem
Trong ngục tối gồm các đường hầm M và các nút giao N, mỗi đường hầm kết nối một số hai nút giao. Vua chuột quyết định đặt một đèn giao thông trong mỗi đường hầm trước mỗi ngã tư. Viết chương trình tính toán có bao nhiêu đèn giao thông nên được lắp đặt tại mỗi ngã tư. Ngã tư được đánh số từ 1 đến N.
Đầu vào
Dòng đầu tiên chứa hai số N và M (\(0<N<=100\), \(0<=M<=N*(N-1)/2\) ). Các dòng M sau chứa hai số i và j (\(1<=i,j<=N\)) , điều đó có nghĩa là các giao lộ i và j được nối với nhau bằng một đường hầm.
Dấu ấn
In ra số N: số thứ kcó nghĩa là số đèn giao thông tại giao lộ thứ k.
Lưu ý
Chúng ta có thể giả sử rằng hai nút giao thông bất kỳ được nối với nhau bằng không quá một đường hầm. Không có đường hầm nào từ giao lộ i đến chính nó.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
7 10
5 1
3 2
7 1
5 2
7 4
6 5
6 4
7 5
2 1
5 3
|
3 3 2 2 5 2 3 |