Cải cách một chiều

Ở vương quốc Berland có $n$ thành phố và $m$ con đường hai chiều, mỗi con đường nối hai thành phố khác nhau. Giữa mỗi cặp thành phố có nhiều nhất một con đường, và không có con đường nào nối một thành phố với chính nó. Đồ thị đường đi có thể không liên thông.

Bộ trưởng giao thông quyết định cải cách: biến tất cả các con đường thành đường một chiều, tức là gán cho mỗi con đường một hướng. Bộ trưởng muốn tối đa hoá số thành phố mà tại đó số con đường đi ra bằng số con đường đi vào.

Hãy tìm số thành phố lớn nhất đạt được và chỉ ra một cách định hướng tương ứng. Nếu có nhiều phương án, in ra một phương án bất kỳ. Các con đường có thể in theo thứ tự tuỳ ý, nhưng mỗi con đường phải xuất hiện đúng một lần.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương $t$ ($1\le t\le 200$): số bộ dữ liệu.
• Mỗi bộ dữ liệu có dạng:
  • Dòng đầu chứa hai số nguyên $n$ và $m$ ($1\le n\le 200$, $0\le m\le n·(n-1)/2$): số thành phố và số con đường.
  • $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$, $v$ ($1\le u,v\le n$): một con đường nối hai thành phố $u$ và $v$.

Dữ liệu ra

Với mỗi bộ dữ liệu:

• Dòng đầu in số thành phố lớn nhất có số đường đi ra bằng số đường đi vào.
• $m$ dòng tiếp theo, mỗi dòng in hai số nguyên: thành phố nơi con đường bắt đầu và thành phố nơi con đường kết thúc, mô tả một cách định hướng đạt được giá trị lớn nhất đó.

Ràng buộc

• $1\le t\le 200$.
• $1\le n\le 200$, $0\le m\le n·(n-1)/2$.
• Không có khuyên và không có cạnh bội.
• Tổng số thành phố trong tất cả các bộ dữ liệu không vượt quá $200$.

Ví dụ