Cho một tập tập ~S~ với kích thước ~m~ và một số nguyên dương ~n~; mỗi phần tử của tập hợp là một cặp số ~(x,y)~ thỏa mãn:

• ~1\le x \le n~

• ~1\le y \le n~

• ~x\neq y~

Đồng thời; với hai phần tử ~(x, y)~ và ~(u,v)~ bất kì thuộc ~S~ thì:

• ~u\neq x~ hoặc ~v \neq y~

• ~v \neq x~

Yêu cầu: Hãy tìm tập ~P~ có tính chất tương tự tập ~S~ thỏa mãn ~P \cap S = \emptyset ~ và ~P~ có kích thước càng lớn càng tốt

Input

• Dòng đầu tiên chứa hai số nguyên dương ~m,n~ (~m\le 10^6, n\le 2\times 10^3~)

• ~m~ dòng tiếp, mỗi dòng gồm hai số nguyên mô tả một phần tử của tập ~S~

Output

• In ra một số nguyên là số phần tử của tập ~P~ bạn tìm được

• ~|P|~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên mô tả một phần tử của tập ~P~

Subtask

Gọi ~GK~ là lực lượng tập ~P~ trong đáp án của Ban giám khảo, và ~TS~ là lực lượng tập ~P~ trong đáp án của bạn. Với mỗi test bạn sẽ được:

• Toàn bộ số điểm nếu ~TS \ge GK~

• ~- 0.416 \times \log_{10}(\frac{GK-TS}{GK})~ Nếu ~TS < GK~

Sample Input 1

1 3
1 2

Sample Output 1

2
1 3
2 3

Note

Dễ thấy tập trên là tập có kích thước lớn nhất thỏa mãn điều kiện