Thành phần liên thông

Bạn được cung cấp một đồ thị vô hướng có \(n\) đỉnh và \(m\) cạnh. Đồ thị không chứa đa cạnh hay vòng tự sinh. Các đỉnh được đánh số từ \(1\) đến \(n\).

Nhiệm vụ của bạn là tìm các thành phần liên thông trong đồ thị bù của đồ thị đã cho.

Đồ thị bù của đồ thị \(G = (V, E)\) là đồ thị \(\overline{G} = (V, \overline{E})\) sao cho với mỗi cặp đỉnh phân biệt \(u\) và \(v\):

• Nếu có cạnh \((u, v)\) trong \(G\) thì không có cạnh đó trong \(\overline{G}\);
• Nếu không có cạnh \((u, v)\) trong \(G\) thì có cạnh đó trong \(\overline{G}\).

Input

Dòng đầu chứa hai số nguyên \(n\) và \(m\) \((1 \le n \le 10^6,\ 0 \le m \le 5 \cdot 10^5)\) — số đỉnh và số cạnh trong đồ thị ban đầu.

Mỗi dòng trong số \(m\) dòng tiếp theo chứa hai số nguyên \(u\) và \(v\) \((1 \le u, v \le n,\ u \ne v)\), mô tả một cạnh trong đồ thị.

Đảm bảo rằng không có cạnh nào xuất hiện nhiều hơn một lần.

Output

In ra một dòng đầu tiên chứa một số nguyên \(k\) — số thành phần liên thông trong đồ thị bù.

Scoring

Bài được chia thành các subtask:

• Subtask 1 (30 điểm): \(n \le 2\,000\), \(m \le 2\,000\).
• Subtask 2 (40 điểm): \(n \le 10^5\), \(m \le 10^5\).
• Subtask 3 (30 điểm): Không có giới hạn thêm.