퍼져나가는 소문
우측 버튼을 눌러 기기를 연결해주세요.
문제 정보
퍼져나가는 소문
쉬움
유형
프로그래밍
배점
100
참여자
112
정답률
90.1%
0
0

문제


"발 없는 말이 천 리 간다"는 옛말이 있듯, 한 번 퍼져나가기 시작한 소문은 막을 수 없이 퍼져나간다.

구름이는 명의 친구가 있고, 그 친구들 중에는 쌍의 친구 관계가 있다. 구름이가 만약 어떤 친구에게 소문을 퍼뜨리게 된다면, 그 소문은 친구의 친구, 친구의 친구의 친구... 를 타고 퍼져나갈 것이다.

구름이가 번 친구에게 소문을 퍼뜨렸을 때, 그 소문을 듣게 될 친구가 몇 명이나 될지를 구해보자.


예제 설명


첫 번째 예시의 친구 관계는 아래 그림과 같다.


모든 친구가 친구 관계로 연결되어 있으므로, 1번 친구에게 비밀을 전달하게 되면 모든 친구에게 비밀이 퍼져나가게 된다.

두 번째 예시의 친구 관계는 아래 그림과 같다.


1번 친구에게 비밀을 전달하게 되면 3, 4, 5 친구에게 비밀이 퍼져나가게 된다. 따라서 1번 친구를 포함해 네 명의 친구가 소문을 듣게 된다.


입력


첫째 줄에 구름이의 친구의 수 이 주어진다.
둘째 줄에 친구 관계의 수 이 주어진다.
다음 개의 줄에는 서로 친구 관계에 있는 두 친구의 번호인 가 공백을 두고 주어진다. 모든 친구 관계는 양방향이다.

  • 같은 친구 관계가 중복해서 주어지지 않는다.
  • 입력에서 주어지는 모든 수는 정수이다.


출력


구름이가 번 친구에게 소문을 냈을 때, 소문을 듣게 되는 친구의 수를 출력한다.

입/출력 예시
:
공백
:
줄 바꿈
:
예시 1
입력
5
5
13
23
34
45
42
출력
5
예시 2
입력
7
5
14
35
76
15
43
출력
4
⋇ 입출력 형식을 잘 지켜주세요
Q&A
누구나 질문하고 답변할 수 있는 Q&A입니다. 문제를 풀며 어려웠던 부분에 대해 질문해보세요.
이 문제에 관한 질문 (0)