CSES - Building Roads | Xây đường

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Thời gian:
Pypy 3 2.0s
Python 3 2.0s
Tác giả:
PhanDinhKhoi , Flower_On_Stone , kitsune
Dạng bài
Điểm: 1100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Byteland có \(n\) thành phố, và \(m\) con đường đường giữa chúng. Mục tiêu là xây dựng các con đường mới để có một tuyến đường giữa hai thành phố bất kỳ.

Nhiệm vụ của bạn là tìm ra số lượng đường tối thiểu cần thiết, đồng thời xác định những con đường nào nên được xây dựng.

Input

  • Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): số lượng thành phố và con đường đường. Các thành phố được đánh số \(1,2,\ldots,n\).
  • Sau đó, có \(m\) dòng mô tả các con đường. Mỗi dòng có hai số nguyên \(a\) và \(b\): có một đường giữa các thành phố đó.
  • Một con đường luôn kết nối hai thành phố khác nhau, và có nhiều nhất một con đường giữa hai thành phố bất kỳ.

Output

  • Đầu tiên in một số nguyên \(k\): số lượng con đường cần thiết.
  • Sau đó, in \(k\) dòng mô tả các con đường mới. Bạn có thể in bất kỳ giải pháp hợp lệ nào.

Constraints

  • \(1 \le n \leq 10^5\)
  • \(1 \leq m \leq 2 \cdot 10^5\)
  • \(1 \leq a, b \leq n\)

Example

Sample input

4 2
1 2
3 4

Sample output

1
2 3

Bình luận