Untitled

Ta xét một bản đồ địa lý có N quốc gia được đánh số từ 1 đến N (1  <= N <=  1000). Đối với mọi quốc gia, chúng tôi biết số lượng các quốc gia khác được kết nối với biên giới của quốc gia đó. Từ mọi quốc gia, chúng ta có thể đến bất kỳ quốc gia nào khác, cuối cùng vượt qua một số biên giới. Viết chương trình xác định xem có thể tô bản đồ chỉ bằng hai màu-đỏ và xanh theo cách sao cho nếu hai quốc gia được kết nối với nhau thì màu của chúng sẽ khác nhau hay không. Màu của quốc gia đầu tiên là màu đỏ . Chương trình của bạn phải xuất ra một màu có thể có cho các quốc gia khác hoặc chỉ ra rằng việc tô màu như vậy là không thể.    

[Đầu vào]
Dòng đầu tiên là tổng số test T.

Một trường hợp thử nghiệm có hai dòng. Trong mỗi trường hợp thử nghiệm, dòng đầu tiên có N (số quốc gia ) và E (số biên giới ) được phân tách bằng khoảng trắng. Dòng tiếp theo liệt kê E border . Một biên giới bao gồm hai quốc gia mà nó kết nối. Ví dụ: biên giới nối quốc gia 5 và 28 được biểu thị bằng “5 28” hoặc “28 5”. Chỉ số của các quốc gia là từ 1 đến N. Tất cả các số liền kề trong một dòng được phân tách bằng dấu cách.

[Đầu ra]
Viết mỗi câu trả lời trong 1 dòng. Mỗi dòng bắt đầu bằng '#x', trong đó x có nghĩa là chỉ mục của một trường hợp thử nghiệm và đặt một khoảng trắng và in câu trả lời.

Nếu có thể tô màu, câu trả lời này phải chứa một danh sách các số 0 và 1, không có bất kỳ dấu phân cách nào giữa chúng. Chữ số thứ i trong dãy này là màu của quốc gia thứ i . 0 tương ứng với màu đỏ và một - với màu xanh lam. Nếu không thể tô màu, hãy xuất số nguyên −1.  

 

[Ví dụ I/O]

Đầu vào

1 ← Tổng test case T                                

3 2 ← Bắt đầu test case 1                             

1 2 2 3

 

đầu ra

#1 010