방향이 없는 무방향 그래프(Undirected Graph)가 주어집니다.

이 그래프에서 특정 시작 정점(Vertex)에서 출발하여 도달할 수 있는 모든 정점을 찾고자 합니다.

노드의 개수 N, 간선의 개수 M, 그리고 시작 정점의 번호 V가 주어질 때, 시작 정점 V를 포함하여 방문 가능한 모든 정점의 번호를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

단, 방문할 수 있는 정점이 여러 개일 경우 정점 번호가 작은 것부터 방문 여부와 관계없이 결과적으로 '도달 가능한 정점의 집합'을 오름차순으로 출력하면 됩니다.

입력

첫째 줄에 노드의 개수 N (1 ≤ N ≤ 1,000), 간선의 개수 M (1 ≤ M ≤ 1,000), 시작 정점의 번호 V (1 ≤ V ≤ N)가 공백을 사이에 두고 주어진다.

둘째 줄부터 M개의 줄에 걸쳐 간선이 연결하는 두 정점의 번호 u, v (1 ≤ u, v ≤ N, u ≠ v)가 공백을 사이에 두고 주어진다.

두 정점 사이에는 여러 개의 간선이 존재할 수 있습니다.

출력

시작 정점 V에서 출발하여 도달할 수 있는 모든 정점의 번호를 공백으로 구분하여 한 줄에 오름차순으로 출력한다.

First line \(N\), \(M\), \(V\); then \(M\) lines each with an edge \(u\), \(v\) (\(1 \le N, M \le 1000\), \(u \ne v\)). Multiple edges may appear.

Print the reachable vertices in ascending order, space-separated.

riseoj 작성

출처 Online Judge > GoldOJ