시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 64 MB | 30 | 0 | 0 | 0.000% |
상범이는 수상한 것들을 모으는 취미가 있다. 이 상범이는 최근에 엄청 이상한 것을 발견했다. 그 이상한 물건은 철제 구조물로, 몇 개의 철 막대가 구슬과 납땜되어진 물건이었다. 이를테면 다음 그림과 같은 모양으로:
상범이는 이 구조물을 보자마자 자신의 남자친구에게 줄 사진 액자를 만들 재료로 딱!이라고 생각했다.
상범이가 원하는 액자는 반드시 철제 막대로 이루어진 닫힌 고리여야 한다. 이를 위해서 상범이는 몇 개의 구슬을 떼어내서 고리의 끝을 분리하고, 그런 막대들을 다시 납땜하는 식으로 고치기 시작했다.
여기서 흥미로운 사실은, 상범이가 구슬을 떼어낼 때 막대를 어떤 식으로 분리할 지 마음대로 고를 수 있다는 것이다. 그러니까, 한 개의 구슬에 여러 개의 막대가 납땜되어있을 경우, 이 구슬을 제거하면서 일부 막대끼리는 붙여놓고, 어떤 건 분리하는 것이 가능하다.
예를 들어, 위의 그림에 나온 구조물을 상범이가 남자친구에게 줄 액자로 만들기 위해서는 A번 구슬을 떼어내면서 막대 1번을 분리한다. 그 다음 D번 구슬을 떼어내면서 막대 4-5번 쌍과 3-7번 쌍을 분리하고(4번과 5번은 여전히 납땜되어진 채로 두고, 3-7번도 납땜되어진 채로 둔다), E번 구슬을 떼어내면서 막대 7번을 분리한다. 마지막으로 끝이 연결되지 않은 1번과 7번 막대를 연결하면 상범이가 남자친구에게 선물할 액자인 1-7-3-2-4-5-6-8이란 이름의 구조물이 완성된다.
상범이는 의외로 게으르기 때문에 최소한의 동작(구슬을 떼어내는 것, 두 개의 막대를 연결하는 것)을 통해 액자를 완성하고싶다.
철제 구조물의 초기 상태가 주어졌을 때, 이 구조물은 얼마나 많은 동작을 통해야 액자가 될 수 있을지 구해보자.
첫 번째 줄에 구슬의 수 N(0 ≤ N ≤ 1000)과 막대의 수 M(2 ≤ M ≤ 50,000)이 주어진다.
구슬의 번호는 1번부터 N번으로 매겨지며, 이어지는 M개의 줄에는 막대의 양 끝이 연결된 구슬의 번호를 나타내는 두 개의 정수가 주어진다.
철제 구조물의 초기 상태는 연결된 상태가 아닐 수도 있으며(즉, 여러 개의 구조물 조각으로 이루어져있을 수도 있다). 구슬 하나에 막대가 하나만 연결되어있을 수도 있는데, 이런 경우, 구슬은 연결된 막대가 다른 막대와 연결되기 전에 떼어내지 않아도 된다.
또한, 막대가 하나도 연결되지 않은 구슬도 있을 수 있다. 상범이는 구슬이 아닌 막대기에만 관심이 있으므로, 그런 구슬은 붙여도 되고 붙이지 않아도 된다.
상범이가 남자친구에게 줄 액자를 만들기 위해 행해야 하는 동작의 최소 횟수를 나타내는 정수 한 개를 출력한다.
6 8 1 2 1 3 3 4 1 4 4 6 5 6 4 5 1 5
4
0 2 0 0 0 0
2
3 3 0 1 0 0 2 2
4
ICPC > Regionals > Northern Eurasia > North-Western Russia Regional Contest > NEERC Northern Subregional 2006 I번