Description

Here are the details. Under Satania’s overwhelming influence, the world is divided into several regions, with some pairs of regions connected by edges. To take back the pineapple buns, Satania further partitions these regions into several domains, each domain consisting of some regions. Satania occupies some of these domains and uses them as bases to attack the lackey. To successfully reclaim all pineapple buns, Satania decides that the domains she occupies must satisfy the following properties:

1. To ensure timely support among allies, for any two vertices that lie in different domains among the domains she occupies, there must be an edge between them.

2. To attack flexibly, for any vertex in any of her domains and any vertex in any domain occupied by the lackey, there must be an edge between them.

Of course, the lackey is not idle either. To humiliate Satania, the lackey also chooses some domains. These domains satisfy the same property as Satania’s choices: for any two vertices that lie in different domains among the lackey’s domains, there must be an edge between them. Moreover, the lackey’s domains are the complement of Satania’s domains (together they cover all domains, and they are disjoint). A person may occupy zero domains.

Satania believes that the more scattered the domains, the higher her chance of victory. She wants to split the regions into as many domains as possible. What is the maximum number of domains, and how many regions does each domain contain?

If you tell Satania the answer, she will gather the largest domain to attack the lackey and ultimately fail.

Input Format

• The first line contains two integers $n$ and $m$, the number of regions and the number of edges.
• Each of the next $m$ lines contains two integers $a$, $b$, indicating that there is an edge between $a$ and $b$.
• There are no self-loops and no multiple edges.

Output Format

• On the first line, output an integer $s$, the maximum possible number of domains.
• On the second line, output $s$ integers in nondecreasing order, where each number is the size (number of regions) of one domain.

3 2
1 2
2 3

2
1 2

Hint

Sample explanation: The maximum is two domains. Regions $1$ and $3$ form one domain, and region $2$ forms one domain. Please read the statement carefully together with the sample.

Constraints:

• For $40\%$ of the testdata, $n \le 10^3$, $m \le 5 \times 10^5$.
• For $100\%$ of the testdata, $n \le 10^5$, $m \le 2 \times 10^6$.

Translated by ChatGPT 5