문제
당신은 크리스마스 파티에 학교 안 자신의 친구와, 자신의 친구의 친구를 초대하기로 했다. 당신이 다니는 학교의 학생은 \(n\)명이고, 각 학생에게는 \(1\)부터 \(n\)까지 번호가 붙어 있다. 당신의 번호는 \(1\)이다. 손에는 누가 누구와 친구인지를 적은 목록이 있다. 이 목록을 바탕으로, 당신이 크리스마스 파티에 초대하는 학생 수를 구하는 프로그램을 작성하라. |
입력
입력은 다음 형식으로 주어진다.
\(n\)
\(m\)
\(a_1\) \(b_1\)
\(\vdots\)
\(a_m\) \(b_m\)
- 첫째 줄에 학교의 학생 수 \(n\)이 주어진다.
- 둘째 줄에 목록의 길이 \(m\)이 주어진다.
- 입력은 모두 \(2+m\)줄이다. \(2+i\)번째 줄에는 정수 \(a_i\)와 \(b_i\)가 공백 하나로 구분되어 주어지고, 번호 \(a_i\)와 번호 \(b_i\)의 학생이 친구임을 나타낸다.
- \(2 \le n \le 500\)
- \(1 \le m \le 10000\)
- \(1 \le a_i \lt b_i \le n\)
- 셋째 줄부터 \(2+m\)번째 줄에 같은 친구 관계를 나타내는 줄이 중복하여 나타나지 않는다.
- 입력되는 값은 모두 정수이다.
출력
다음 형식으로 출력한다.
첫째 줄에 당신이 크리스마스 파티에 초대하는 학생 수를 출력한다.
예시 1
입력
6
5
1 2
1 3
3 4
2 3
4 5
출력
3
설명
당신의 친구는 번호 \(2\), \(3\)의 두 사람이다. 번호 \(3\)과 \(4\)가 친구이므로 번호 \(4\)는 친구의 친구이다. 번호 \(5\), \(6\)은 친구도 친구의 친구도 아니다. 따라서 번호 \(2, 3, 4\)의 3명을 초대한다.
예시 2
입력
6
5
2 3
3 4
4 5
5 6
2 5
출력
0
설명
당신에게는 친구가 없다. 따라서 초대하는 학생 수는 \(0\)명이다.