그래프 색칠하기

그래프가 주어집니다. 각 정점을 검은색 또는 흰색 으로 칠하며, 사용할 수 있는 색은 검은색과 흰색 두 가지뿐입니다. 간선으로 직접 연결된 두 정점을 동시에 검은색으로 칠할 수는 없습니다. 이 조건에서 검은색으로 칠한 정점의 수가 가능한 한 많아지는 색칠을 최적 색칠이라고 합니다.

각 그래프에 대해, 검은색으로 칠할 수 있는 정점의 최대 개수와 그 최대 개수를 달성하는 최적 색칠 하나를 구하세요. 다시 말해 검은 정점들의 집합은 서로 인접하지 않는 독립 집합이며, 그 크기를 최대로 만들어야 합니다.

그래프의 정점은 $1$ 부터 $n$ 까지의 번호로 주어지며, $n \le 100$ 입니다. 각 간선은 무방향이며, 서로 다른 두 정점 번호의 쌍 $(n_1, n_2)$ ($n_1 \ne n_2$) 로 주어집니다.

첫 줄에 그래프의 개수 $m$ 이 주어집니다. 이어서 각 그래프마다, 첫 줄에 정점 수 $n$ 과 간선 수 $k$ 가 공백으로 구분되어 주어지고, 다음 $k$ 개의 줄에 각 간선을 이루는 두 정점 번호가 공백으로 구분되어 주어집니다.

각 그래프마다 두 줄씩, 총 $2m$ 개의 줄을 출력합니다. 첫 줄에는 검은색으로 칠할 수 있는 정점의 최대 개수를 출력합니다. 둘째 줄에는 최적 색칠을 출력합니다. 검은 정점들의 번호를 오름차순으로 정렬하여 공백 하나로 구분해 출력하세요.

최적 색칠이 여러 개일 수 있으므로, 그중 사전순으로 가장 작은 것을 출력합니다. 즉, 검은 정점 번호를 오름차순으로 나열한 수열들을 앞에서부터 원소 단위로 비교하여 가장 작은 수열을 출력합니다.