아기 재민이는 작은 장난감 그래프를 선물받았다.

이 그래프는 이분 그래프의 모양을 하고 있어 왼쪽에 L개, 오른쪽에 R개의 정점이 있다.

재민이는 선물받은 그래프가 너무 밋밋해서 마음에 들지 않았다.

그래서 그래프의 간선들을 색칠해주기로 했다!

재민이는 여러가지 색의 물감을 간선에 발라 색칠한다.

밋밋한 걸 싫어하는 재민이는 한 끝점을 공유하는 두 간선이 같은 색으로 색칠되는 일이 없게 하려고 한다.

재민이는 물감을 많이 꺼내기 귀찮기 때문에 가능한 한 물감을 적게 쓰려고 한다.

그런데 재민이에게 한 가지 문제가 생겼다!

재민이가 도저히 그런 색칠 방법을 아무리 생각하려 해봐도 찾을 수가 없었던 것이다!

재민이는 고심 끝에 최소의 색깔을 쓰는 것을 포기했다.

그래프를 색칠할 수 있는 최소의 색깔 수가 C라고 하자.

재민이는 최소의 색깔 수 대신에 2^k >= C 인 최소의 2^k보다 작거나 같은 개수의 색을 사용하기로 했다.

하지만 이렇게 조건을 바꾸어도 재민이는 여전히 색칠 방법을 찾지 못했다.

여러분이 재민이가 원하는 대로 그래프를 색칠하는 방법을 대신 알려주자!

색칠놀이 timer 8s memory 256MB

색칠놀이 8s 256MB