들판의 데이지 사슬

면접 대비

시간 제한1초메모리 제한128 MB

요약
소들이 밧줄로 연결된 무방향 그래프에서 1번 소에 도달할 수 없는 소의 번호를 오름차순으로 출력하고, 모두 연결되어 있으면 0을 출력한다.
난이도

쉬움10점 중 3점

유형
그래프, DFS, BFS, 구현
정답자
아직 제출이 없습니다

문제

농부 존은 11번부터 NN번까지 번호를 매긴 소 NN마리(1≤N≤2501 \le N \le 250)를 들판에서 놀게 했습니다. 소들은 밧줄로 서로를 이어 총 MM개(1≤M≤N(N−1)21 \le M \le \frac{N(N-1)}{2})의 연결을 만들었습니다. 두 소를 직접 잇는 밧줄은 많아야 하나뿐입니다. 각 연결은 이어진 두 소 c1c_1, c2c_2로 주어집니다(1≤c1≤N1 \le c_1 \le N; 1≤c2≤N1 \le c_2 \le N; c1≠c2c_1 \ne c_2).

농부 존은 모든 소가 11번 소와 같은 사슬에 속하기를 바랍니다. 문제를 일으키는 소를 찾아 주세요. 즉, 하나 이상의 밧줄을 거쳐 11번 소와 이어지지 않은 소들의 번호를 오름차순으로 출력하세요(11번 소는 당연히 언제나 자기 자신과 이어져 있습니다). 문제를 일으키는 소가 없다면 00을 출력합니다.

이해를 돕기 위해 소 여섯 마리가 네 개의 연결을 이룬 경우를 봅시다:

    1---2  4---5
     \  |
      \ |      6
       \|
        3

여기서 소 44, 55, 66번은 11번 소와 이어져 있지 않습니다.

입력

  • 첫째 줄: 공백으로 구분된 두 정수 NN과 MM.
  • 2…M+12 \ldots M+1번째 줄: i+1i+1번째 줄은 밧줄 ii가 잇는 두 소 c1c_1, c2c_2를 공백으로 구분된 두 정수로 나타냅니다.

출력

  • 11번 소와 이어지지 않은 소들의 번호를 오름차순으로 한 줄에 하나씩 출력합니다.
  • 모든 소가 11번 소와 이어져 있다면 00 한 줄만 출력합니다.

예제1

  1. 예제 1

    입력
    6 4
    1 3
    2 3
    1 2
    4 5
    
    예상 출력
    4
    5
    6