Team Formation

N students attended a camp. You want to assign each student to exactly one of team A and team B for a team match.

The assignment must satisfy all of the following conditions.

1. Every student belongs to exactly one of team A and team B.
2. Every pair of students on the same team must know each other.

Write a program that determines whether such a team assignment is possible and, if it is possible, prints one valid assignment.

The first line contains a natural number N, the number of students. (N <= 1,000)

The students are numbered from 1 to N. Starting from the second line, each line contains two natural numbers a and b separated by a space. This means student a and student b know each other.

The input ends with a line containing -1 -1.

If a valid assignment is possible, print 1 on the first line. Then print two lines, one for each team, with the student numbers in increasing order separated by spaces. Print -1 at the end of each of these two lines.

The team containing student 1 must be printed first.

If no valid assignment is possible, print only -1 on the first line.