Vương quốc nọ có lâu đài, và giữa chúng có con đường nối với nhau. Biết rằng không có con đường nào nối một lâu đài với chính nó, và cũng không có cặp lâu đài nào nhiều hơn một đường nối giữa chúng.
Quốc vương muốn dạo chơi quanh vương quốc này. Với mỗi lâu đài, quốc vương muốn đi thăm nó chẵn, hoặc lẻ lần. Biết được ý muốn của quốc vương, bạn hãy sắp xếp lộ trình cho quốc vương, sao cho thỏa mãn ý muốn của ngài. Tuy nhiên, lộ trình cũng không được quá dài, do kinh phí hạn hẹp, số lâu đài đi qua chỉ được phép không quá .
Chú ý rằng mỗi thành phố có thể đi qua nhiều lần. Trong bài toán này, bạn không phải in ra lộ trình cho quốc vương, đơn giản, bạn chỉ cần phải kiểm tra xem có tồn tại lịch trình như vậy hay không.
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên dương là số lượng test ;
Tiếp sau là test, mỗi test bắt đầu bằng hai số nguyên dương ;
Tiếp sau đó là cặp số thể hiện có đường nối giữa lâu đài với lâu đài ;
Dòng tiếp theo trong mỗi test là số nguyên hoặc , có nghĩa là cần được thăm chẵn hay lẻ lần.
Dữ liệu ra:
Gồm dòng là kết quả tương ứng với dữ liệu vào. In ra nếu tồn tại đường đi và nếu ngược lại.
