<PREV Problem:
NEXT>
Solved by 139 users: ...
UserDateAttemptTimeCMSC
NIGHTFIT21 mar 2012C++800.03214 
NIGHTFIT21 mar 2012C++700.03216 
Madiyar_Tktl19 jan 2014C++700.03221 
Madiyar_Tktl19 jan 2014C++600.03225 
Madiyar_Tktl19 jan 2014C++500.02229 
topspin12 sep 2009Kylix2200.12243 
Iamnot231 jul 2004C1?.??245 
topspin12 sep 2009Kylix2100.12246 
Moonlight06 jan 2008FPC100.02248 
topspin12 sep 2009Kylix1800.11249 
topspin12 sep 2009Kylix1700.10254 
MasterYoda27 mar 2009C++400.03257 
MasterYoda27 mar 2009C++500.03257 
NIGHTFIT21 mar 2012C++500.02260 
NIGHTFIT18 apr 2012C++900.02261 
topspin12 sep 2009Kylix1600.10261 
MasterYoda27 mar 2009C++300.02263 
Puella25 jun 2009C++100.01264 
Madiyar_Tktl19 jan 2014C++300.02264 
fetetriste24 jul 2007C++1200.02264 
doriath04 sep 2007C++100.25270 
Evgeny27 jul 2004FPC1?.??270 
Languages
C++
81
FPC
33
Java
11
Kylix
11
C
8
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Graph Coloring

Time limit = 2 second(s)

Memory limit = 8

You are to write a program that tries to find an optimal coloring for a given graph. Colors are applied to the nodes of the graph and the only available colors are black and white. The coloring of the graph is called optimal if a maximum of nodes is black. The coloring is restricted by the rule that no two connected nodes may be black.

Input

The graph is given as a set of nodes denoted by numbers 1...N, N ≤ 100, and a set of undirected edges denoted by pairs of node numbers (n1, n2), n1 ≠ n2. The first line contains N and K, the number of nodes and the number of edges, respectively. The following K lines contain the edges given by a pair of node numbers, which are separated by a space.

Output

The output should consists of 2m lines, two lines for each graph found in the input file. The first line of output should contain the maximum number of nodes that can be colored black in the graph. The second line should contain one possible optimal coloring. It is given by the list of black nodes, separated by a blank.

Input#1
6 8
1 2
1 3
2 4
2 5
3 4
3 6
4 6
5 6

Output#1
3
1 4 5

Author:
ACM International Collegiate Programming Contest
Southwestern European Regional Contest
ETH Zurich, Switzerland, December 9, 1995
19 Jule 2004

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 18.207.240.35