QUAN HỆ CĨ N NGƯỜI MANG TÊN TƯƠNG ỨNG LÀ 1, 2, ..., N VÀ TÌNH TRẠNG Q...

Bài 2: Quan hệ Cĩ N người mang tên tương ứng là 1, 2, ..., N và tình trạng quen biết của N người này được cho bởi mảng

đối xứng A[1..N,1..N] trong đĩ A[i,j] = A[j,i] = 1 nếu i quen j và bằng 0 nếu i khơng quen j. Hãy xét xem liệu cĩ thể chia N

người đĩ thành 2 nhĩm mà trong mỗi nhĩm hai người bất kì đều khơng quen nhau?

Dữ liệu vào được cho bởi file QHE.INP trong đĩ dịng thứ nhất ghi số nguyên dương N <= 100, trong N dịng tiếp

theo, dịng thứ i ghi N số A[i,1], ..., A[i,N].

Kết quả ghi ra file QHE.OUT như sau:

oNếu khơng cĩ thể , ghi -1

oNếu cĩ thể, ghi ra hai dịng, dịng thứ nhất tên những người thuộc nhĩm 1, dịng thứ hai tên những người thuộc

nhĩm 2.

Ví dụ:

QHE.INP QHE.OUT

11

1 3 4 7 8 11

0 1 0 0 1 1 0 0 0 0 0

2 5 6 9 10

1 0 1 0 0 0 0 0 0 0 0

0 1 0 0 0 0 0 0 0 0 0

0 0 0 0 1 1 0 0 1 0 0

1 0 0 1 0 0 0 0 0 0 0

1 0 0 1 0 0 1 0 0 0 0

0 0 0 0 0 1 0 0 0 1 0

0 0 0 0 0 0 0 0 1 1 0

0 0 0 1 0 0 0 1 0 0 0

0 0 0 0 0 0 1 0 0 0 1

0 0 0 0 0 0 0 0 0 1 0