dlaud5379   9달 전

(Kagi Translate로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)

문제

박한별은 여러 개의 철사 고리로 이루어진 체인을 가지고 있었는데, 오랫동안 서랍에서 나뒹굴고 있던 나머지 완전히 엉켜 버렸다. 박한별은 은하에게 체인을 고쳐 달라고 부탁하려고 한다.

각 고리에는 1번부터 n번까지의 번호가 붙어 있으며 처음에는 모두 닫혀 있다. 서로 다른 두 고리는 연결되어 있거나 연결되지 않은 상태일 수 있다. 은하는 두 가지의 작업을 할 수 있다.

  • 닫혀 있는 고리 중 원하는 고리 하나를 푼다. 이 작업을 하고 나면 고리가 열린 상태가 되며, 체인에서 완전히 분리할 수 있다.
  • 열려 있는 고리 중 원하는 고리 하나를 선택하고, 나머지 고리의 원하는 부분집합에 끼운 뒤 납땜한다. 이 작업을 하고 나면 고리가 닫힌 상태가 되며, 선택한 부분집합에 속하는 고리와만 연결된 상태가 된다.

모든 작업이 끝난 뒤에는 모든 고리가 닫힌 상태여야 한다.

박한별은 1번 고리와 2번 고리, 2번 고리와 3번 고리, ..., n-1번 고리와 n번 고리를 연결하려고 한다. 즉, 모든 1 ≤ i < n에 대해 i번 고리와 i+1번 고리가 연결되어야 한다. 이 이외에 어떤 고리 쌍도 연결되어서는 안 된다.

은하가 체인을 고치기 위해 수행해야 하는 최소 작업 횟수를 구하는 프로그램을 작성하여라.

입력

첫째 줄에 고리의 개수 n과 처음에 연결되어 있는 고리 쌍의 개수 m이 공백으로 구분되어 주어진다. (1 ≤ n ≤ 40, 0 ≤ m ≤ n(n-1)/2)

다음 줄부터 m개의 줄에 걸쳐 연결된 고리의 정보가 주어진다. 이 중 i번째 줄에는 서로 연결된 고리의 번호를 나타내는 두 정수 ai, bi가 공백으로 구분되어 주어진다. (1 ≤ ai, bi ≤ n; ai ≠ bi)

고리 쌍은 순서를 구분하지 않으며, 같은 고리 쌍이 여러 번 주어지지 않는다.

출력

문제의 정답을 한 줄로 출력한다.

노트

예제 입력 1에서는 우선 3번 고리를 풀어서 나머지 모든 고리에서 분리한 뒤, 다시 납땜하면서 2번 고리와만 연결하면 된다.

예제 입력 2에서는 우선 2번 고리를 푼 뒤 1번과 3번 고리와 연결한다. 그 다음에는 4번 고리를 푼 뒤 3번과 5번 고리와 연결하면 된다.

댓글을 작성하려면 로그인해야 합니다.