Bedao Mini Contest 18 - FINDSET

Xem dạng PDF

Gửi bài giải


Điểm: 0,70 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.