Magnet Toy
Time limit1.5sMemory limit256 MB
Given a simple graph, decide whether its vertices can be removed one by one so that each removed vertex's remaining neighbors form a clique, and output the order if possible.
- Level
Hard8 of 10
- Topics
- Graph, Implementation, Simulation, Sorting
- Solved
- No attempts yet
Problem
JayG published a toy set for the Little Friends. The set contains N round magnets shaped like the Little Friends and M string-shaped magnets. Round magnets do not stick to each other, and string-shaped magnets do not stick to each other either. But a string-shaped magnet and a round magnet do stick together, so when you gather these magnets, a string-shaped magnet connects two different round magnets.
You play with this set by removing the connected round magnets one at a time. When you remove a round magnet X, all string-shaped magnets attached to X are removed as well, and to remove X, every pair of all the other round magnets connected to X by a string-shaped magnet must be connected by a string-shaped magnet.
For example, in the connection state shown below, all magnets can be removed according to the rule described above.
The state below also allows every magnet to be removed. For instance, you can remove them in the order Muzi, Apeach, Con, Tube, Ryan, and other orders work too.
But the figure below is impossible. At first the only magnet you can remove is Ryan, and after that you cannot remove any other magnet.
JayG wants to bundle a program with the toy set that tells the Little Friends who will play with it whether the magnet connections allow a way to remove every magnet. Write that program for JayG and the Little Friends.
Input
The first line gives the number of round magnets N and the number of string-shaped magnets M. The round magnets are numbered 1 through N. (1≤N≤100,000, 1≤M≤300,000)
Each of the following M lines gives the numbers of two different round magnets that a string-shaped magnet connects. At most one string-shaped magnet connects the same pair of round magnets.
Output
If the connection state given as input allows every magnet to be removed according to the rule, print 1 on the first line, then print on the next line the order of magnet numbers in which all magnets are removed. If several orders are possible, you may print any of them. If the rule does not allow every magnet to be removed, print 0 on a single line.