세 친구
면접 대비시간 제한2초메모리 제한512 MB
희소 무방향 그래프에서 서로 인접한 세 정점을 골라, 나머지 두 정점을 제외한 각 정점의 차수 합이 최소가 되는 값을 구한다.
문제
N명의 사람이 있고, 이 중에서 세 사람 A, B, C를 고르려고 한다. 세 사람은 모두 서로 친구여야 한다.
세 사람을 고르는 방법은 매우 많을 수 있다. 이때 A의 친구 수 + B의 친구 수 + C의 친구 수가 최소가 되어야 한다. 친구 수의 합을 계산할 때 세 사람은 제외한다. 즉, A의 친구 수를 셀 때 B와 C는 제외하고, B의 친구 수를 셀 때 A와 C를 제외하며, C의 친구 수를 셀 때 A와 B를 제외한다.
입력
첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000)과 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에 친구 관계를 나타내는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, B와 A가 서로 친구라는 뜻이다.
사람에게는 1번부터 N번까지 번호가 매겨져 있다. 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.
출력
첫째 줄에 A의 친구 수 + B의 친구 수 + C의 친구 수의 최솟값을 출력한다. 문제 조건대로 세 사람을 고를 수 없으면 -1을 출력한다.