서로 떨어지고 도로로 연결된 여러 마을이 있을 때, 주유소를 최소한으로 설립하려고 한다.

주유소는 해당 마을 또는 바로 옆 마을에는 있어야 한다.

각 마을에 번호를 붙여서 아래와 같은 형식으로 마을과 마을이 연결된 정보를 받을 때, 최소로 주유소를 세울 수 있는 마을 번호를 적어라.

• 각 마을의 도로 연결 정보는 2쌍의 수로 받는다.
• 각 마을간 거리는 동일하다고 가정한다.

입력

출력

입출력 예

입력

1 2
2 4
3 4
4 5
6 7
1 6
1 7
0

출력

1 4
4 6
4 7

출처:http://kin.naver.com/qna/detail.nhn?d1id=1&dirId=1040101&docId=106815060&qb=7J6F7IKs66y47KCc&enc=utf8§ion=kin&rank=4&search_sort=0&spq=0
채점 데이터:emiyamolzomdao