구슬 찾기

모양은 같으나, 무게가 모두 다른 [eqn: N]개의 구슬이 있다. [eqn: N]은 홀수이며, 구슬에는 번호가 [eqn: 1,2,`...,`N]으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 [eqn: (N+1)/2]번째) 구슬을 찾기 위해서 아래와 같은 일을 하려 한다.

우리에게 주어진 것은 양팔 저울이다. 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려 보면 어느 쪽이 무거운 가를 알 수 있다. 이렇게 [eqn: M]개의 쌍을 골라서 각각 양팔 저울에 올려서 어느 것이 무거운 가를 모두 알아냈다. 이 결과를 이용하여 무게가 중간이 될 가능성이 전혀 없는 구슬들은 먼저 제외한다.

예를 들어, [eqn: N=5]이고, [eqn: M=4] 쌍의 구슬에 대해서 어느 쪽이 무거운가를 알아낸 결과가 아래에 있다.

① 구슬 2번이 구슬 1번 보다 무겁다.

② 구슬 4번이 구슬 3번 보다 무겁다.

③ 구슬 5번이 구슬 1번 보다 무겁다.

④ 구슬 4번이 구슬 2번 보다 무겁다.

위와 같이 네 개의 결과만을 알고 있으면, 무게가 중간인 구슬을 정확하게 찾을 수는 없지만, 1번 구슬과 4번 구슬은 무게가 중간인 구슬이 절대 될 수 없다는 것은 확실히 알 수 있다. 1번 구슬보다 무거운 것이 2, 4, 5번 구슬이고, 4번 보다 가벼운 것이 1, 2, 3번이다. 따라서 답은 2개이다.

[eqn: M]개의 쌍에 대한 결과를 보고 무게가 중간인 구슬이 될 수 없는 구슬의 개수를 구하는 프로그램을 작성하시오.

프로그램 이름은 ball.cpp, 프로그램 설명 파일 이름은 ball.hwp로 하고, 실행 시간은 1초를 초과할 수 없다. 부분 점수는 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 입력 자료의 첫 줄은 구슬의 개수를 나타내는 정수 [eqn: N] ([eqn: 1≤N≤99])과 저울에 올려 본 쌍의 개수 [eqn: M]이 주어진다. 그 다음 [eqn: M]개의 줄은 각 줄마다 두 개의 구슬 번호가 주어지는데, 앞 번호의 구슬이 뒤 번호의 구슬보다 무겁다는 것을 뜻한다.

2003 가을학기 문제해결기법	문제 #2

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 첫 줄에 무게가 중간이 절대로 될 수 없는 구슬의 수를 출력한다.

입력과 출력의 예

입력(input.txt)

5 4

2 1

4 3

5 1

4 2

출력(output.txt)

2