세 대화방의 집중 설정

문제

한 회사의 사내 메신저에는 업무별로 나눈 대화방이 K개 있으며, 각 대화방에는 1번부터 K번까지 번호가 붙어 있다. 한 직원은 집중 업무 시간에 사용할 알림 설정을 정하려 한다. 이 설정에서는 서로 다른 대화방을 정확히 세 개 선택한다. 선택한 대화방은 집중 대화방으로 표시되며, 그 선택에 따라 일부 알림이 숨겨진다. 선택은 집중 시간 동안 바뀌지 않는다. 메신저는 지난 집중 시간에 생성된 N개의 알림 기록을 제공한다. 각 알림에는 두 개의 대화방 번호 a와 b가 적혀 있다. a와 b가 다르면 두 대화방에 함께 연결된 알림이며, 두 대화방을 모두 집중 대화방으로 선택했을 때만 숨겨진다. 둘 중 하나만 선택한 경우에는 알림이 그대로 표시된다. a와 b가 같으면 해당 대화방 하나에만 연결된 알림이며, 그 대화방을 선택하면 숨겨진다. 번호가 적힌 순서는 알림을 숨기는 조건에 영향을 주지 않는다. 각 기록은 별개의 알림 한 개를 나타낸다. 따라서 같은 두 번호가 적힌 기록이 여러 번 나와도 각각 따로 센다. 직원은 과거 기록에 현재 설정을 적용했을 때 숨겨지는 알림의 수가 최대가 되도록 세 대화방을 선택하려 한다. 대화방 자체에 연결된 기록이 전혀 없어도 선택할 수 있으며, 기록이 하나도 없어도 정확히 세 대화방을 선택해야 한다. 선택한 세 번호를 오름차순으로 정렬하여 x, y, z로 나타낸다. 숨겨지는 알림의 수가 같은 선택이 여러 개이면 x가 가장 작은 선택을 고른다. x도 같으면 y가 가장 작은 선택을 고르고, y까지 같으면 z가 가장 작은 선택을 고른다. 주어진 알림 기록을 바탕으로 선택할 세 번호와 숨겨지는 알림의 수를 구한다.

입력

첫째 줄에 정수 K와 N이 공백으로 주어진다. 3 ≤ K ≤ 60, 0 ≤ N ≤ 20,000이다.
다음 N개 줄에 각 알림의 대화방 번호를 나타내는 정수 a와 b가 공백으로 주어진다. 1 ≤ a, b ≤ K이며, a와 b는 같을 수 있다. 같은 번호 쌍이 여러 번 주어질 수 있다.

출력

선택한 대화방 번호 x, y, z와 숨겨지는 알림의 수를 한 줄에 공백으로 구분하여 출력한다. 반드시 x < y < z여야 한다. 숨길 수 있는 알림이 없어도 동점 규칙에 따라 1 2 3 0을 출력한다.

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

1 2 3 5

4 0

1 2 3 0

4 4
4 4
4 4
2 4
3 4

2 3 4 4

출처: Devin.KR 자체 제작