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
Bình luận