작은 노드
Press the right button to connect the device.
Quiz Info
작은 노드
100points
Participant
444
Solved Rate
98.1%
14
11

문제


개의 노드와 개의 양방향 간선으로 이루어진 그래프가 있다. 이 그래프의 노드는 번부터 번까지 번호가 붙어 있다. 양끝 노드가 동일한 간선은 주어지지 않는다.

플레이어는 아래 규칙에 따라 그래프에서 이동하려고 한다. 플레이어는 처음에 번 노드에 있다.

  • 한 번 방문한 노드는 다시 방문할 수 없다. 시작 노드도 방문한 것으로 간주한다.
  • 현재 노드와 간선으로 직접 연결된 다른 노드 중, 방문할 수 있으면서 번호가 가장 작은 노드로 이동한다.

플레이어가 더 이상 이동할 수 있는 노드가 없을 때, 방문한 서로 다른 노드의 개수와 마지막 노드 번호를 구해보자.


입력


첫째 줄에 노드의 개수 , 간선의 개수 , 시작 노드의 번호 가 공백을 두고 주어진다.
다음 개의 줄에는 간선이 잇는 양끝 정점의 번호 가 공백을 두고 주어진다.



출력


플레이어가 더 이상 이동할 수 없을 때까지 방문한 노드의 개수와 마지막 노드의 번호를 출력한다.

Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
661
12
13
23
34
35
46
Output
56
Example 2
Input
651
12
23
34
45
56
Output
66
Example 3
Input
651
23
32
62
42
43
Output
11
⋇ Please keep the input and output formats carefully
Q&A
누구나 질문하고 답변할 수 있는 Q&A입니다. 문제를 풀며 어려웠던 부분에 대해 질문해보세요.
Registered Questions (0)