프로그램 명: ncpc_enemy(special judge)
제한시간: 1 초
미군 대장 커람은 어려운 결정을 해야 한다. 2147 년에 큰 전쟁이 있었다.
그의 병사들은 전쟁이 일어난 후 쭉 함께 생활 했다.
이 년 전 부터 그들 중의 몇몇이 서로 적대적인 관계가 되었다. 다행이 각 병사는 많아야 3 명까지만 적대적이다.
그들은 곧 다른 나라를 공격하러 가야 한다, 그런데 커람은 전투시 서로 적대적인 관계인 사람 끼리 서로 협력하지 않을까 걱정하고 있다. 그래서 그룹에는 많아야 한 명의 적대적인 관계인 사람들을 두도록 그룹을 지을려고 한다.
그리고 가장한 적은 수의 그룹을 두려고 한다. 그를 도와라.
Picture by The U.S. Army. Captain Keram has to make a difficult decision. It is year
2147 and there is a big war in the world. His soldiers have
been together since the war started, two years ago, and some
of them have become enemies. Luckily, each soldier has at
most 3 enemies.
They need to attack another country soon, and Keram is
worried that soldiers who are enemies might not cooperate
well during the battle. He has decided to divide them into
groups such that every soldier has at most one enemy in his
group. He also wants to make it simple, so he wants to use as few groups as possible.
Can you divide the soldiers into groups for him?
입력
On the first line there are two integers n and m, 2 <= n <= 100 000, 0 <= m <= 3n/2, where
n is the number of soldiers and m is the number of enemy pairs. Then follow m lines,
each containing two space separated integers ai; bi, denoting that soldiers ai and bi are enemies, where 1 <= ai < bi <= n. You can assume that all soldiers have at most 3 enemies.
출력
The first line of output contains the minimal number of groups of soldiers k. Each of the
next k lines contains a space separated list of a soldiers in a unique group.
입출력 예
입력
4 4
1 2
2 3
3 4
1 4
출력
2
1 3
2 4
출처:The 2011 Nordic Collegiate Programming Contest problem J
special judge:ps1111
[질/답]
[제출 현황]
[푼 후(1)]