문제

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

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

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

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

입력

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

• 
• 
  
• 
• ; 

출력

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