loj#P2693. 「POI2012」比赛路线 Tour de Byteotia

「POI2012」比赛路线 Tour de Byteotia

题目描述

译自 POI 2012 Stage 2. Day 0「Tour de Byteotia

给定一个 nn 个点 mm 条边的无向图,问最少删掉多少条边能使得编号小于等于 kk 的点都不在任何一条简单环上。

输入格式

第一行包含三个整数 n n m m k k ,分别表示 n n 个节点, m m 条边,k k 意义见题面。

接下来 m m 行,每行两个整数 u u v v ,表示一条由 u u v v 的双向边,每一对点之间至多只有一条边。

输出格式

第一行一个整数 k k ,表示最少的删边数量;

接下来 k k 行,每行输出两个正整数 a,ba,b,表示删除 a,ba,b 之间的一条边,先输出编号小的点,再输出编号大的点。

11 13 5
1 2
1 3
1 5
3 5
2 8
4 11
7 11
6 10
6 9
2 3
8 9
5 9
9 10
3
2 3
5 9
3 5

数据范围与提示

对于 40%40\% 的数据有 n1000,m5000n \le 1000,m \le 5000.

对于所有数据有 $1 \le n \le 1\ 000\ 000,0 \le m \le 2\ 000\ 000,1 \le k \le n, 1 \le u \lt v \le n$.