레이팅 미적용Mr. Malnar is organizing a banquet for 2N of his associates that are numbered
with integers 1, 2, . . . , 2N. Associates came to the banquet in pairs. Looking at
their behavior, Mr. Malnar noticed some strange rules that govern the spread of
information within this group.
First, person A is willing to share information with person B if and only if they
are friends. A pair of associates that came to the banquet together are friends.
Second, every person is willing to share information with at most one other person.
At the same time, that person must not be aware of that information.
Third, every person will try to share information where priority is given to the
person that came with them to the banquet.
In other words, if person A came with person B to the banquet and person A is
aware of some information that person B is not, person A will share that information with person B.
Because of the previous rules, person A will not share that information with anyone else and person B
will try to share it with another person that they are friends with etc.
Fourth, the group can be split into two subgroups such that if two people are friends they are not in the
same subgroup.
Mr. Malnar will tell his story to one of his associates and is interested in the maximum number of his
associates that can hear his story. If that number is \(K\), he is also interested in some sequence of associates
\(a_{1}\), \(a_{2}\), . . . , \(a_{K}\) such that if he is to tell his story to associate \(a_{1}\) then for every \(i = 1\), 2, . . . , \(K - 1\) associate
\(a_{i}\) can tell the story to associate \(a_{\)i+1\(}\).
In the process of discovering said rules Mr. Malnar determined all friendships but forgot the pairs of
associates that came to the banquet together. Fortunately, it is possible to recover this information. In
other words, there is a unique partition of associates into N pairs such that associates within the same
pair are friends.
Can you help Mr. Malnar answer his questions?
Subtask 1 (24 points): \(N \le 10\)
Subtask 2 (16 points): Every associate is friends with at most two other associates.
Subtask 3 (30 points): \(N \le 2000\), \(M \le 5000\)
Subtask 4 (40 points): No additional constraints.
The first line contains integers \(N\) and \(M\) (\(1 \le N \le 5 \cdot 10^{5}\), \(N \le M \le 10^{6}\)), number of pairs of associates
that came to the banquet and the number of friendships.
In each of the next M lines there are two integers \(u_{i}\) and \(v_{i}\) (\(1 \le u_{i}\), \(v_{i} \le 2 \cdot N\)), labels of associates that
are friends.
In the first line, print a single integer K - the maximum number of associates that can hear Mr. Malnar’s
story.
In the second line, print a sequence of \(K\) integers that satisfy the constraints.
2 3
1 2
1 4
3 44
2 1 4 33 5
1 2
2 3
1 4
4 5
1 64
6 1 2 34 8
1 2
2 3
3 4
4 1
2 5
3 6
4 7
7 86
6 3 4 1 2 5Clarification of the first example:
Associates that came together are: 1 and 2, 3 and 4.
Clarification of the second example:
Associates that came together are: 1 and 6, 2 and 3, 4 and 5. Longer sequences do not satisfy the
constraints. For example, sequence (3,2,1,4,5) does not satisfy the constraints even though every two
adjacent associates are friends because associate 1 can’t tell the story to person 4 after hearing it from
associate 2. This is because the associate that came with them to the banquet, namely associate 6, is still
unaware of the story (third rule).
Clarification of the third example:
Associates that came together are: 1 and 4, 2 and 5, 3 and 6, 7 and 8.