Bajtysia và Bajteusz là những nhà du hành nổi tiếng, những người đã đặt chân đến hầu hết mọi ngóc ngách của Bajtocja. Vùng đất này bao gồm $n$ thành phố, được đánh số từ $1$ đến $n$, kết nối với nhau bởi một mạng lưới các con đường một chiều. Tuy nhiên, họ đã cảm thấy nhàm chán với các phương thức di chuyển truyền thống – họ đã đi đến tất cả những nơi có thể đến được.

Gần đây, Bajtysia sở hữu một cổ vật ma thuật – Sổ Đăng ký Đường bộ (Road Register). Nó cho phép tạo ra các con đường một chiều mới giữa các thành phố. Tuy nhiên, có một điều kiện. Phép thuật của cuốn sổ rất thất thường và chỉ cho phép tạo một con đường giữa hai thành phố nếu hiện tại không thể đi từ thành phố thứ nhất đến thành phố thứ hai bằng mạng lưới đường hiện có (nghĩa là không có chuỗi các con đường dẫn từ thành phố thứ nhất đến thành phố thứ hai; tuy nhiên, có thể tồn tại một chuỗi các con đường dẫn từ thành phố thứ hai đến thành phố thứ nhất). Việc cố gắng tạo một con đường giữa hai thành phố đã có đường kết nối sẽ thất bại và phá hủy cuốn sổ.

Đối với Bajtysia và Bajteusz, đây là một thử thách tuyệt vời! Họ ngay lập tức quyết định rằng họ muốn tạo ra càng nhiều con đường mới càng tốt.

Thật không may, Bajtysia và Bajteusz quá bận rộn với việc lên kế hoạch cho chuyến thám hiểm tiếp theo nên không thể tự mình giải quyết vấn đề này. Hãy giúp họ lập kế hoạch tạo từng con đường một sao cho tổng số lượng con đường là lớn nhất có thể.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ và $m$ ($1 \le n \le 1500$, $0 \le m \le n(n-1)$), lần lượt là số lượng thành phố và số lượng con đường một chiều ở Bajtocja. $m$ dòng tiếp theo chứa mô tả các con đường. Dòng thứ $i$ trong số đó (với $1 \le i \le m$) chứa hai số nguyên $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$), biểu thị rằng có một con đường một chiều từ thành phố $a_i$ đến thành phố $b_i$. Các con đường một chiều được mô tả không bị lặp lại.

Dữ liệu ra

Ở dòng đầu tiên của dữ liệu ra, in ra một số nguyên không âm $k$ đại diện cho số lượng tối đa các con đường một chiều có thể được tạo ra sao cho mỗi con đường tiếp theo kết nối một cặp thành phố mà hiện tại không thể đi lại giữa chúng. $k$ dòng tiếp theo mô tả các con đường cần được tạo theo thứ tự. Dòng thứ $i$ trong số đó (với $1 \le i \le k$) chứa hai số nguyên $c_i, d_i$ đại diện cho hai thành phố mà con đường thứ $i$ sẽ được tạo giữa chúng. Tại thời điểm tạo con đường này, không được phép có đường đi từ thành phố $c_i$ đến thành phố $d_i$ bằng các con đường hiện có (bao gồm cả các con đường ban đầu và các con đường đã được tạo trước đó). Nếu có nhiều lời giải, hãy in ra bất kỳ lời giải nào.

Nhiệm vụ con

Nếu chỉ dòng đầu tiên trong câu trả lời của bạn là chính xác, lời giải của bạn sẽ nhận được 50% số điểm cho bài kiểm tra đó. Bạn không cần phải in các dòng tiếp theo để nhận được số điểm này.

Ví dụ

Dữ liệu vào 1

7 8
1 2
2 3
3 1
3 4
4 5
5 4
5 6
6 7

Dữ liệu ra 1

3
4 1
6 4
7 6

Dữ liệu vào 2

3 0

Dữ liệu ra 2

5
3 1
3 2
2 1
2 3
1 2

Ghi chú

Trong ví dụ đầu tiên, mạng lưới đường hiện có ban đầu được minh họa dưới đây:

Không thể đi từ thành phố 4 đến thành phố 1, vì vậy một con đường như vậy có thể được thêm vào. Sau khi thêm các con đường từ thành phố 6 đến thành phố 4 và từ thành phố 7 đến thành phố 6, chúng ta thu được một mạng lưới mà tại đó có thể đi lại giữa mọi cặp thành phố. Không thể thêm bất kỳ cạnh nào nữa.