투 명 테 잎

KOI 전자에서는 건강에 좋고 맛있는 훈제오리구이 요리를 간편하게 만드는 인공지능 오븐을 개발하려고 한다. 인공지능 오븐을 사용하는 방법은 적당한 양의 오리 훈제 재료를 인공지능 오븐에 넣으면 된다. 그러면 인공지능 오븐은 오븐구이가 끝나는 시간을 초 단위로 자동적으로 계산한다.

또한, KOI 전자의 인공지능 오븐 앞면에는 사용자에게 훈제오리구이 요리가 끝나는 시각을 알려 주는 디지털 시계가 있다.

훈제오리구이를 시작하는 시각과 오븐구이를 하는 데 필요한 시간이 초 단위로 주어졌을 때, 오븐구이가 끝나는 시각을 계산하는 프로그램을 작성하시오.

입력

• 첫 째 줄에는 현재 시각이 나온다. 현재 시각은 시 A (0 <= A <= 23) , 분 B ( 0 <= B <= 59) 와 초 C ( 0 <= C <= 59) 가 정수로 빈칸을 사이에 두고 순서대로 주어진다.
• 두 번째 줄에는 요리하는 데 필요한 시간 D ( 0 <= D <= 500 000)가 초 단위로 주어진다.

출력

입출력 예

입력 

14 30 0
200

출력 

14 33 20

입력 

17 40 45
6015

출력 

19 21 0

입력 

23 48 59
2515

출력 

0 30 54

출처:2012 지역 본선 중등 1/5

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

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

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

1. 구슬 2번이 구슬 1번 보다 무겁다.
2. 구슬 4번이 구슬 3번 보다 무겁다.
3. 구슬 5번이 구슬 1번 보다 무겁다.
4. 구슬 4번이 구슬 2번 보다 무겁다.

위와 같이 네 개의 결과만을 알고 있으면, 무게가 중간인 구슬을 정확하게 찾을 수는 없지만, 1번 구슬과 4번 구슬은 무게가 중간인 구슬이 절대 될 수 없다는 것은 확실히 알 수 있다. M 개의 쌍에 대한 결과를 보고 무게가 중간인 구슬이 될 수 없는 구슬의 개수를 구하는 프로그램을 작성하시오.

실행 시간은 1초를 초과할 수 없다. 부분 점수는 없다.

입력 형식

출력 형식

입출력 예

입력

5 4
2 1
4 3
5 1
4 2

출력

2

출처: 제20회한국정보올림피아드(2003.7.19) 중등부문제1

1 번부터 N 번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단,N 명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.

• 1번 학생의 키 < 5번 학생의 키
• 3번 학생의 키 < 4번 학생의 키
• 5번 학생의 키 < 4번 학생의 키
• 4번 학생의 키 < 2번 학생의 키
• 4번 학생의 키 < 6번 학생의 키
• 5번 학생의 키 < 2번 학생의 키

1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다.

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력과 출력의 예

입력

• 첫째 줄에 학생들의 수 N ( 2 <= N <= 500) 이 주어진다.
• 다음 줄에 두 학생 키를 비교한 횟수 M ( 0 <= M <= N(N-1)/2 ) 이 주어진다.
• 다음 M 개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 두 양의 정수 a 와 b 가 주어진다. 이는 번호가 a 인 학생이 번호가 b 인 학생보다 키가 작은 것을 의미한다.

출력

입출력 예

입력 

6
6
1 5
3 4
5 4
4 2
4 6
5 2

출력

1

입력 

6
7
1 3
1 5
3 4
5 4
4 2
4 6
5 2

출력

2

입력 

6
3
1 2
2 3
4 5

출력

0

출처:koi 2011 지역 본선 초등 4