바니차
시간 제한3초메모리 제한2048 MB
원형으로 놓인 조각들 중 서로 다른 토핑을 얹어야 하는 쌍이 주어질 때, 필요한 토핑의 최소 종류 수를 구합니다.
문제
노란 오리 새끼가 가장 좋아하는 음식은 바니차(치즈 파이와 비슷한 불가리아의 전통 음식)다! 그래서 지난주에 엄마가 바니차를 하나 만들어 주셨다. 이 아이는 욕심이 많아서 거의 다 먹어 버렸고, 몇 조각만 남았다. 오리 새끼는 그 조각들을 아침으로 먹기로 하고, 아침에 위에 올릴 좋아하는 요거트를 사러 나갔다. 조각들을 원형으로 놓고 시계 방향으로 번호를 매겼다. 첫 번째 조각에 요거트를 한 숟가락 올리려는 순간, 엄마가 말을 끊고 아빠도 바니차를 맛봐야 한다고 했다(아빠는 이유는 모르겠지만 요거트를 정말 싫어한다?!). 그리고 서로 다른 토핑을 올려야 하는 조각 쌍 몇 개를 알려 주었다. 흥미로운 점은, 쌍을 이루는 조각들을 모두 선으로 이었을 때 어떤 두 선도 교차하지 않는다는 것이다.
노란 오리 새끼는 코로나19 사태 이후 집안 형편이 그리 넉넉하지 않은 것을 무척 걱정한다. 부모님을 생각하는 마음에서, 엄마의 조건을 만족시키면서 토핑을 최대한 적게 사고 싶어 한다. 하지만 아직 세 살이라 알고리즘에는 우리만큼 흥미가 없다(자라면 얼마나 멋진지 알게 되기를 바란다). 그래서 이 문제를 도와 달라고 부탁한다.
입력
첫 줄에 두 정수가 주어진다. 은 남은 바니차 조각의 수이고, 은 쌍의 개수이다.
이어지는 개의 줄에는 각각 서로 다른 토핑을 올려야 하는 두 조각의 번호가 주어진다.
출력
노란 오리 새끼가 사야 하는 서로 다른 토핑의 최소 개수를 출력한다.