문제 1021 홍보뱃지
[만든사람 : ]
문제 설명
세종이는 "새로운 학교 행복한 아이들" 홍보활동을 펼치고 있다. 이번 주에는 홍보뱃지를 만들어서 학생들에게 나누어주려고 한다.
새로 만든 홍보뱃지가 인기가 워낙 많아서
세종이 친구들, (→ 1단계 친구)
세종이 친구의 친구들, (→ 2단계 친구)
세종이 친구의 친구의 친구들, (→ 3단계 친구)
세종이 친구의 친구의 친구의 친구들, (→ 4단계 친구)
세종이 친구의 친구의 친구의 친구의 친구들, (→ 5단계 친구)
세종이 친구의 ... 친구의 친구들 (→ k단계 친구)
에게도 뱃지를 나눠주려고 한다.
세종이가 만든 홍보뱃지를 받게 되는 학생은 총 몇명인지 알아내서 세종이를 도와주자.
(세종이는 뱃지를 받지 않는다)
학생들은 번호로 표현(n명일 경우 1~n)되고, 친구관계가 주어진다.
새로 만든 홍보뱃지가 인기가 워낙 많아서
세종이 친구들, (→ 1단계 친구)
세종이 친구의 친구들, (→ 2단계 친구)
세종이 친구의 친구의 친구들, (→ 3단계 친구)
세종이 친구의 친구의 친구의 친구들, (→ 4단계 친구)
세종이 친구의 친구의 친구의 친구의 친구들, (→ 5단계 친구)
세종이 친구의 ... 친구의 친구들 (→ k단계 친구)
에게도 뱃지를 나눠주려고 한다.
세종이가 만든 홍보뱃지를 받게 되는 학생은 총 몇명인지 알아내서 세종이를 도와주자.
(세종이는 뱃지를 받지 않는다)
학생들은 번호로 표현(n명일 경우 1~n)되고, 친구관계가 주어진다.
세종이가 9번이고 2단계 친구들까지 뱃지를 나누어준다면, 위 그림에서와 같이 7명(3, 6, 11, 13, 1, 5, 10)이 뱃지를 받게 된다.
입력 설명
첫 줄에 총 학생수 n(1 <= n <= 30)과 친구관계의 수 m(1 <= m <= 30), 세종이의 번호, 단계 k(1<= k <= 7)가 주어진다.
둘째줄부터 m줄에 걸쳐 서로 친구인 2명 학생의 숫자
둘째줄부터 m줄에 걸쳐 서로 친구인 2명 학생의 숫자
출력 설명
홍보뱃지를 받게 되는 친구의 총 인원수
입력 예시 복사
13 14 9 2
1 3
1 4
2 13
3 5
3 9
3 13
4 5
5 8
5 10
5 12
6 9
6 10
7 10
9 11
출력 예시 복사
7
출처/분류