Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VOSNET - Social Network

Social Network - Một cụm từ chắc ai trong chúng ta đều biết ! Một mạng xã hội sẽ gồm nhiều tài khoản (được biết như những người trong một xã hội) và các mối quan hệ giữa chúng (như sự quen biết giữa con người với con người).

Chúng ta hãy cùng làm một "nghiên cứu" nho nhỏ về mạng xã hội. Mạng sẽ gồm N tài khoản (để đơn giản đặt tên từ 1 đến N) và M cặp quan hệ (U,V) cho biết U và V quen biết nhau.

Theo dự đoán, cứ trung bình một tháng, một người sẽ quen hết tất cả những người có quen với bạn của người đó. Nói cách khác nếu:

  • A quen với B, B quen với C;
  • A không quen với C

Thì sau một tháng A sẽ quen với C, và một mối quan hệ mới (A,C) được tạo thành !

Sẽ đến 1 tháng, mà sẽ không có mối quan hệ mới nào được tạo thành (và sự phát triển của mạng xã hội sẽ tạm dừng, nếu không kích thích tạo thêm tài khoản mới, quan hệ mới) - người ta gọi tháng đó là tháng bão hòa.

Cứ sau mỗi tháng, người ta sẽ thống kê số mối quan hệ mới được tạo thành. Dựa vào dự đoán ở trên, bạn hãy tính toán những con số quan trọng cho đó đến khi tháng bão hòa bắt đầu.

Input

  • Dòng đầu tiên gồm 2 số N và M;
  • M dòng tiếp theo, mỗi dòng gồm cặp số biểu diễn quan hệ (U,V);

Output

  • Một dòng duy nhất chứa 1 dãy số, số thứ i từ trái sang sẽ biểu diễn số mối quan hệ mới được tạo thành trong tháng thứ i (tất nhiên số cuối cùng sẽ là 0 - biểu diễn tháng bão hòa);

Example

Input:
6 6
1 2
2 3
3 4
4 6
2 5
5 6

Output: 7 2 0

Giải thích:
Các mối quan hệ mới theo mỗi tháng:
1. (1,3), (1,5), (2,4), (2,6), (3,5), (3,6), (4,5);
2. (1,4), (1,6);
3. Không tạo mới;

Giới hạn

  • N ≤ 3000, M ≤ 6000;
  • 20% số dữ liệu có N ≤ 100;

Được gửi lên bởi:Alex & Friends
Ngày:2013-12-07
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VOS Round 23 - Tranhu Thái Huy

hide comments
2017-11-01 16:44:30
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI: http://yeulaptrinh.pw/1347/vosnet-spoj/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.