P4833 Satania's Archnemesis

"Trick or treat!" It’s Halloween. Vignette, Satania, and Raphiel knock on Gabriel’s door—but as expected, Gabriel is playing online games. Truly decadent. "What is it? So annoying." Gabriel looks at them with obvious disgust. "Gabriel, at least come out and have some fun. Staying home gaming every day will rot your brain," Vignette says first. "Huh? I go out every day. When I go to buy instant noodles, I take a stroll around the building downstairs." "That only counts as going to the convenience store. It doesn’t count as going out to have fun." "Yeah, and it’s Halloween. Let’s go get some candy together." "Huh? How old are you? Still playing such a boring game." "Not at all, I think it’s fun," the three say in unison. "Good grief. Fine, fine, I’ll play along." So Gabriel goes out with the three of them to ask for candy. "So, whose place first?" "I have a suggestion!!" Satania says excitedly, cutting in. They arrive at someone’s home. "Knock, knock." After a moment, the door opens, and out comes a bald man. "Trick or treat!" Satania calls out happily. Standing before them is their homeroom teacher. But while Satania is cheerfully asking for candy, the other three are already trembling in fear. "Uh... ho- homeroom teacher...? T- teacher, there’s been a misunderstanding..." Vignette says, shaking. "What misunderstanding? Homeroom teacher, trick or treat! Oh~ if you don’t give us candy, we’ll draw you into a ghost~" Satania remains fearless. "Hey..." Vignette takes a small step back. Surprisingly, the teacher goes back inside and takes out a bag of treats, including Satania’s favorite limited-edition pineapple bun. "Ah!!! It’s the limited edition!!! Awesome!!!" Just as Satania reaches for the bun, the angel’s lackey rushes out and snatches it away. "Hey!! That’s mine!! Give it back!" Satania glares at the angel’s lackey, vowing to take it back. Satania’s forces and the angel’s lackey’s forces occupy different areas. Each area occupied by the angel’s lackey contains one pineapple bun. Satania wants to take these pineapple buns back. Can you help her?

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.

- 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.

- 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.

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