퍼져나가는 소문
쉬움
유형
프로그래밍
배점
100점
참여자
112
정답률
90.1%
0
0
문제
"발 없는 말이 천 리 간다"는 옛말이 있듯, 한 번 퍼져나가기 시작한 소문은 막을 수 없이 퍼져나간다.
구름이는 명의 친구가 있고, 그
친구들 중에는
쌍의
친구 관계가 있다. 구름이가 만약 어떤 친구에게 소문을 퍼뜨리게 된다면, 그
소문은 친구의 친구, 친구의 친구의 친구... 를 타고 퍼져나갈 것이다.
구름이가 번 친구에게
소문을 퍼뜨렸을 때, 그 소문을 듣게 될 친구가 몇 명이나 될지를 구해보자.
예제 설명
첫 번째 예시의 친구 관계는 아래 그림과 같다.
모든 친구가 친구 관계로 연결되어 있으므로, 1번 친구에게 비밀을 전달하게 되면 모든 친구에게 비밀이 퍼져나가게 된다.
두 번째 예시의 친구 관계는 아래 그림과 같다.
1번 친구에게 비밀을 전달하게 되면 3, 4, 5번 친구에게 비밀이 퍼져나가게 된다. 따라서 1번 친구를 포함해 네 명의 친구가 소문을 듣게 된다.
입력
첫째 줄에 구름이의 친구의 수 이 주어진다.
둘째 줄에 친구 관계의 수 이 주어진다.
다음 개의 줄에는 서로 친구
관계에 있는 두 친구의 번호인
가 공백을 두고
주어진다. 모든 친구 관계는 양방향이다.
-
-
-
- 같은 친구 관계가 중복해서 주어지지 않는다.
- 입력에서 주어지는 모든 수는 정수이다.
출력
구름이가 번 친구에게 소문을 냈을 때, 소문을 듣게 되는 친구의 수를 출력한다.