Untitled

Chúng ta xem xét một bản đồ địa lý với 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 đường viền của nó. Từ mọi quốc gia, cuối cùng chúng ta có thể tiếp cận với bất kỳ quốc gia nào khác vượt qua một số biên giới. Viết một chương trình xác định xem nó có khả thi hay không để tô màu bản đồ chỉ bằng hai màu - đỏ và xanh lam theo cách mà nếu hai Các quốc gia được kết nối, màu sắc của họ là khác nhau. 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 chương trình màu có thể cho các quốc gia khác, hoặc cho thấy, rằng màu đó là không thể.

[Đầu vào]
Các dòng đầu tiên là tổng số trường hợp kiểm thử T.

Một test case có hai dòng. Trong mỗi trường hợp kiểm thử, dòng đầu tiên có N (số quốc gia) và E (số biên giới) cách nhau bởi một khoảng trắng. Dòng tiếp theo liệt kê viền E. 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 kết nối các quốc gia 5 và 28 được thể hiện bằng "5 28" hoặc "28 5". Các chỉ số của các quốc gia là 1 đến N. Tất cả các số liền kề trong một dòng được phân tách bởi một không gian.

[Đầu ra]
Xuất ra từng 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 kiểm thử và đặt một khoảng trắng, và in câu trả lời.

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


1 ← Tổng số trường hợp kiểm thử T

3 2 ← Bắt đầu thử nghiệm Trường hợp 1

1 2 2 3

#1 010

6 9
3 5 2 6 4 2 6 3 3 1 3 4 6 1 5 1 1 4 
12 12
10 12 8 7 1 7 10 3 6 7 9 5 7 10 11 7 4 11 12 5 2 12 10 4 
46 45
32 10 7 26 5 29 15 45 13 38 5 27 24 41 46 23 12 25 22 21 44 42 40 15 17 34 17 37 27 43 10 25 16 27 13 2 43 8 22 15 17 1 17 4 8 3 36 39 36 6 30 5 40 44 39 4 18 39 1 29 36 15 16 12 38 26 24 13 28 43 41 19 17 33 7 42 11 13 13 31 46 43 6 14 2 35 9 6 35 20