시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 16 8 7 77.778%

문제

캠프에 많은 학생들이 참석했다. 학생들 모두에게 A팀 또는 B팀을 할당해서 두 개의 팀으로 나누어 팀전을 진행할 예정인데, 아래의 조건을 만족하도록 팀을 편성하고 싶다.

  1. 모든 사람은 A팀 또는 B팀 중 오직 하나의 팀에 반드시 속해야 한다.
  2. 같은 그룹의 학생들끼리는 모두 서로 아는 사이어야 한다.

이 조건을 만족하면서 팀을 편성하는 프로그램을 작성하시오.

입력

첫째 줄에 학생 수를 나타내는 자연수 N이 주어진다. (N≤1,000) 편의상 각 학생들은 1부터 N까지 번호가 붙어 있다고 가정한다. 둘째 줄부터 각 줄에 두 개의 자연수 a와 b가 빈 칸을 사이에 두고 주어지는데, 이는 a번 학생과 b번 학생이 서로 아는 사이라는 뜻이다. 마지막 줄에 -1 -1이 주어진다.

출력

가능한 경우 첫째 줄에 1을 출력하고, 이어서 두 줄에 학생의 번호를 빈 칸을 사이에 두고 증가하는 순서대로 각각 출력한다. 1번 학생이 포함된 팀을 먼저 출력해야 한다. 이 두 줄의 끝에는 -1을 출력하도록 한다. 불가능한 경우에는 첫째 줄에 -1만을 출력하면 된다.

예제 입력

6
1 2
2 3
1 5
4 5
3 1
4 6
5 6
-1 -1

예제 출력

1
1 2 3 -1
4 5 6 -1

힌트

출처