Problem
Terdapat n bucu dalam graf tidak terarah, tetapi ia tidak mempunyai tepi. m tepi ditambahkan secara beransur-ansur pada graf.
Selepas setiap penambahan tepi, anda perlu mengetahui bilangan komponen yang disambungkan.
Graf boleh mempunyai gelung dan berbilang tepi.
Input:
Baris pertama mengandungi dua nombor - n dan m (1 <= n <= 300000, 0 <= m <= 500000) - bilangan bucu graf dan bilangan tepi yang ditambah.
Garis m seterusnya mengandungi dua nombor u, v (1 <= u, v <= n) - ia bermaksud bahawa tepi (u, v) telah ditambahkan pada graf.
Output:
Selepas setiap penambahan tepi, cetak bilangan komponen graf yang disambungkan.
|
Masukkan |
Output |
|
3 2
1 2
2 3
|
2
1 |
|
36
1 1
2 2
3 3
1 1
2 2
1 2
|
3
3
3
3
3
2
|
(c) Ibrahim Ahmad, 2018