Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMST - Cây khung

Cho một đơn đồ thị liên thông gồm N đỉnh, M cạnh. Các đỉnh của đồ thị được đánh số từ 1 đến N. Tìm 3 cây khung khác nhau của đồ thị.
Định nghĩa cây khung của đồ thị:
Cây khung của đồ thị G gồm N đỉnh, M cạnh, là một đồ thị G’ gồm tất cả N đỉnh của đồ thị G, và đúng N-1 cạnh của đồ thị G, và G’ là đồ thị liên thông.

Input

Dòng đầu: 2 số nguyên dương N và M (1 < N <= M, N <= 1000, M <= 1500)
M dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương u, v (u khác v) thể hiện 1 cạnh nối giữa u và v. Input đảm bảo đồ thị liên thông và có ít nhất 3 cây khung khác nhau.

Output

Dòng 1 gồm 1 số nguyên dương K duy nhất - số cây khung mà bạn tìm được (0 <= K <= 3).
Tiếp theo là K nhóm dòng, mỗi nhóm dòng gồm đúng N-1 dòng, thể hiện 1 cây khung.

Cách tính điểm

  • Nếu trong K cây khung mà bạn tìm được, có một cây khung không hợp lệ (có chu trình, không liên thông), hoặc có 2 cây khung giống nhau thì bạn không được điểm nào
  • Nếu K = 0, bạn không được điểm nào
  • Nếu K = 1, bạn được 20% số điểm của test
  • Nếu K = 2, bạn được 40% số điểm của test
  • Nếu K = 3, bạn được 100% số điểm của test

Bài này có đúng 20 test, tổng điểm là 100. Trong lúc thi bạn chỉ được chấm với 2 test (không bao gồm test đề bài), và điểm tối đa mà bạn có thể nhận được là 10 điểm.

Example

Input:
3 3
1 2
2 3
3 1

Output:
3
1 2
2 3
2 3
3 1
3 1
1 2

Được gửi lên bởi:VOJ Team
Ngày:2014-08-16
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED

hide comments
2017-08-29 04:04:03
test yếu, chưa xử lý trường hợp các cây khung giống nhau vẫn AC :))
2016-11-22 13:23:48 Nguyễn Hữu Phong
DFS và BFS thì cũng sẽ cho ra cây khung :P, nhưng BFS để tạo cây khung theo độ rộng mới AC đc :))
2016-05-24 15:51:53
vl thuật toán bài này sao giống thuật trâu bò quá vậy :v
2015-06-07 09:52:08 [Nghien] Le Long
1 đấm haizzz
2014-08-23 11:05:51 Tây Cuồng
Một đấm ac :)) cũng không khó lắm :))
2014-08-22 18:16:37 Thcs Ðặng Chánh Kỷ
lúc đầu dfs vẫn ăn được 65 nha, vui vãi
, may đổi cách làm , cũng đơn giản
2014-08-22 18:15:20 Lollipop
thánh nhể quý :v
2014-08-22 18:14:42 Thcs Ðặng Chánh Kỷ
sai ngớ ngẩn thật cha[x]:=cha[y] và nó đã làm tôi mất rất nhiều time
2014-08-22 15:43:36 Stupid Dog

vãi cả random ! vậy mà cũng ac ! Kha Kha Kha !


Last edit: 2014-08-22 15:44:39
2014-08-22 14:18:51 LOVE VNOI
Người ta ko ac vì tìm thiếu cây khung, mình ko ac vì tìm thừa cây khung :3

Last edit: 2014-08-22 14:19:02
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.