Team Formation
Time limit2sMemory limit128 MB
Given pairs of students who know each other, decide if all students can be split into two teams where every same-team pair is acquainted, and output one valid split.
- Level
Medium6 of 10
- Topics
- Graph, BFS, Implementation
- Solved
- No attempts yet
Problem
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.
- Every student belongs to exactly one of team A and team B.
- 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.
Input
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.
Output
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.