Kết nối

Xem PDF

Điểm: 400 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

\(n\) người trong một cuộc thi, họ hoàn toàn không quen nhau.

Cuộc thi diễn ra trong \(n\) giờ, và trong quãng thời gian đó, cứ mỗi giờ thứ \(i\) thì game bắt đầu lại từ đầu, và lại có một yêu cầu mới được đặt ra: \(i-1\) yêu cầu trước phải thỏa mãn, và người thứ \(x_i\) và người thứ \(y_i\) phải quen nhau.

Hai người \(x, y\) được gọi là quen nhau nếu họ trực tiếp làm quen với nhau, hoặc có một dãy \(p_1 = x, p_2, p_3, \dots, p_k = y\) mà với mọi \(i < k\) thì người \(p_i\) quen người \(p_{i+1}\).

Bạn là thành viên ban tổ chức, với nhiệm vụ là sau mỗi giờ, bạn phải sắp xếp lại các cặp người quen trực tiếp, sao toàn bộ cho các điều kiện tới thời điểm đó đều thỏa mãn.

Sau mỗi giờ từ giờ thứ nhất tới giờ thứ \(n\), hãy cho biết số người quen trực tiếp nhiều nhất mà một người có thể quen tại thời điểm đó là bao nhiêu.

Input

  • Dòng đầu tiên chứa hai số \(n, d\). \((2 \le n \le 2 \times 10^5, 1 \le d \le n-1)\)
  • \(d\) dòng sau, dòng thứ \(i\) chứa hai số \(x_i, y_i\) biểu thị hai người chưa quen với nhau trước giờ thứ \(i\).

Output

In ra \(d\) dòng, dòng thứ \(i\) biểu thị đáp án sau giờ thứ \(i\).

Scoring

  • Subtask 1 (40%): \(n \le 2 \times 10^3\)
  • Subtask 2 (60%): \(n \le 2 \times 10^5\)

Example

Test 1

Input

7 6
1 2
3 4
2 4
7 6
6 5
1 7

Output

1
1
3
3
3
6

Test 2

Input

10 8
1 2
2 3
3 4
1 4
6 7
8 9
8 10
1 4

Output

1
2
3
4
5
5
6
8


Bình luận


  • 0
    huyhau6a2    5:18 p.m. 2 Tháng 6, 2022

    Đọc đề... chả hiểu gì hết. Ai giải thích hộ mình được không ạ


    • 0
      lmqzzz    11:34 p.m. 2 Tháng 6, 2022

      bạn nên học về DSU ( Disjoint Set Union ) thì bạn sẽ hiểu đề hơn đấy.

      1 bình luận nữa