지원 도구 두 개 고르기

문제

사내 IT 지원팀은 다음 근무 시간에 사용할 휴대용 지원 장비를 준비하고 있다. 장비에는 저장 공간이 부족하여 지원 도구를 정확히 두 종류만 설치할 수 있다. 설치 후보 도구는 1번부터 K번까지이며, 같은 도구를 두 번 설치하는 것은 허용되지 않는다. 지원팀은 접수된 요청 중 현장에서 바로 처리할 수 있는 요청이 가장 많아지도록 두 도구를 고르려 한다. 각 지원 요청에는 그 요청을 처리할 수 있는 서로 다른 도구 번호 두 개가 적혀 있다. 두 도구 중 하나만 장비에 설치되어 있어도 해당 요청을 처리할 수 있다. 두 도구가 모두 설치되어 있더라도 처리 가능한 요청 수에는 그 요청을 한 번만 더한다. 어떤 요청에 적힌 두 도구가 모두 설치되지 않았다면 그 요청은 이번 장비로 처리할 수 없다. 도구는 사용해도 소모되지 않으며 한 도구로 여러 요청을 처리할 수 있다. 요청마다 처리 시간이나 우선순위의 차이는 없다. 따라서 고려할 값은 처리할 수 있는 요청의 개수뿐이다. 서로 다른 요청에 같은 도구 번호 쌍이 적혀 있을 수 있으며, 이 경우에도 각 행은 별개의 요청이다. 한 행 안에서 두 번호가 적힌 순서는 의미가 없다. 가능한 모든 서로 다른 도구 쌍 중 처리 가능한 요청 수가 가장 많은 쌍을 선택한다. 여러 쌍이 같은 최댓값을 만들면 각 쌍의 두 번호를 작은 번호, 큰 번호 순서로 놓고 비교한다. 작은 번호가 더 작은 쌍을 먼저 선택하며, 작은 번호가 같으면 큰 번호가 더 작은 쌍을 선택한다. 선택한 두 도구 번호와 처리 가능한 요청 수를 출력한다. 접수된 요청이 없어도 두 도구는 골라야 하며, 이때에는 1번과 2번을 선택하고 처리 가능한 요청 수는 0이다.

입력

첫 줄에 도구 종류 수 K와 요청 수 N이 주어진다. K는 2 이상 300 이하의 정수이고, N은 0 이상 20,000 이하의 정수이다.
다음 N개 줄에 해당 요청을 처리할 수 있는 도구 번호 a와 b가 주어진다. a와 b는 1 이상 K 이하의 서로 다른 정수이다. 같은 도구 번호 쌍이 여러 행에 등장할 수 있다.

출력

선택한 두 도구 번호를 오름차순으로 출력하고, 이어서 처리 가능한 요청 수를 출력한다. 세 정수를 공백으로 구분해 한 줄에 출력한다.

4 5
1 2
1 2
1 3
2 4
3 4

1 4 5

5 0

1 2 0

3 3
1 2
2 3
3 1

1 2 3

출처: Devin.KR 자체 제작