Go Make It Complete

Andi는 N개의 기계와 M개의 링크로 이루어진 네트워크 G를 가지고 있다. 각 링크는 서로 다른 두 기계를 연결한다. 어떤 사정으로 인해 Andi는 자신의 네트워크를 "완전"하게 만들어야 한다. 즉, 모든 기계가 다른 모든 기계와 직접 연결되어야 한다. 따라서 Andi는 아직 직접 연결되지 않은 기계 쌍 사이에 새 링크를 추가해야 한다.

목표를 달성하기 위해 Andi는 이 작업을 회사 Go에 외주로 맡긴다. Go는 네트워크 G와 요청된 정수 k, 즉 go(G, k)에 대한 어떤 작업 주문도 받아들인다. Go가 작업하는 방식은 다음과 같다. 먼저, 아직 직접 연결되지 않은 모든 기계 쌍을 담은 리스트 L을 만든다. 그런 다음 Go는 L에 있는 각 기계 쌍 (a, b)를 평가하고, δa + δb ≥ k이면 두 기계 사이에 새 링크를 만든다. 여기서 δa는 기계 a의 차수, 즉 평가 시점에 a가 가지고 있는 링크의 수이다. 마찬가지로 δb는 기계 b의 차수이다.

Go의 절차에서 문제가 되는 점은 각 기계 쌍을 L에 나타난 순서대로 평가한다는 것이다. 예를 들어, G가 N = 4개의 기계(기계 1, 2, 3, 4)와 M = 3개의 링크로 이루어진 네트워크이고, 링크가 {(1, 2), (2, 3), (3, 4)}라고 하자. 작업 주문이 요청되기 전 각 기계의 차수는 δ1 = 1, δ2 = 2, δ3 = 2, δ4 = 1이며, 간단히 [1, 2, 2, 1]로 쓸 수 있다. k = 3인 작업 주문이 요청되었다고 하자(go(G, 3)).

다음 두 리스트를 보자.

• L1 = ((1, 4), (1, 3), (2, 4)).

  • (1, 4)를 평가하고 δ1 + δ4 = 1 + 1 = 2이므로 새 링크를 만들지 않는다. 차수는 여전히 [1, 2, 2, 1]이다.
  • (1, 3)을 평가하고 δ1 + δ3 = 1 + 2 = 3이므로 새 링크를 만든다. 차수는 [2, 2, 3, 1]이 된다.
  • (2, 4)를 평가하고 δ2 + δ4 = 2 + 1 = 3이므로 새 링크를 만든다. 차수는 [2, 3, 3, 2]가 된다.

최종 결과는 5개의 링크를 가진 네트워크이며, (1, 4) 링크가 빠져 있어 완전하지 않다.

• L2 = ((2, 4), (1, 3), (1, 4)).

  • (2, 4)를 평가하고 δ2 + δ4 = 2 + 1 = 3이므로 새 링크를 만든다. 차수는 [1, 3, 2, 2]가 된다.
  • (1, 3)을 평가하고 δ1 + δ3 = 1 + 2 = 3이므로 새 링크를 만든다. 차수는 [2, 3, 3, 2]가 된다.
  • (1, 4)를 평가하고 δ1 + δ4 = 2 + 2 = 4이므로 새 링크를 만든다. 차수는 [3, 3, 3, 3]이 된다.

최종 결과는 6개의 링크를 가진 네트워크이며 완전하다.

보다시피 L2는 완전한 네트워크를 만들지만 L1은 그렇지 않다.

k가 작을수록 Go에 작업을 주문하는 비용이 매우 비쌀 수 있으므로, Andi는 k로 완전한 네트워크를 얻을 수 있는 가능성을 유지하면서 k를 최대한 높여야 한다. 다시 말해, Andi는 go(G, k)가 완전한 네트워크를 만들 수 있는 L이 존재하고, j > k인 모든 j에 대해 go(G, j)가 완전한 네트워크를 만들 수 있는 유효한 L이 존재하지 않는 가장 큰 k를 원한다. 이 문제에서 당신의 임무는 그러한 k를 찾는 것이다.

입력은 두 정수 N M (2 ≤ N ≤ 500; 0 ≤ M < N×(N−1)/2)을 포함하는 한 줄로 시작한다. 이는 각각 기계의 수와 기존 링크의 수를 나타낸다. 기계는 1부터 N까지 번호가 매겨진다. 다음 M개의 줄 각각은 두 정수 ai bi (1 ≤ ai < bi ≤ N)를 포함하며, 이는 기계 ai와 bi를 연결하는 기존 링크를 나타낸다. 각 쌍 (ai, bi)는 입력에 최대 한 번만 나타난다.

요청대로 정수 k를 한 줄에 출력한다.