loj#P2693. 「POI2012」比赛路线 Tour de Byteotia
「POI2012」比赛路线 Tour de Byteotia
题目描述
译自 POI 2012 Stage 2. Day 0「Tour de Byteotia」
给定一个 个点 条边的无向图,问最少删掉多少条边能使得编号小于等于 的点都不在任何一条简单环上。
输入格式
第一行包含三个整数 、、,分别表示 个节点, 条边, 意义见题面。
接下来 行,每行两个整数 ,,表示一条由 到 的双向边,每一对点之间至多只有一条边。
输出格式
第一行一个整数 ,表示最少的删边数量;
接下来 行,每行输出两个正整数 ,表示删除 之间的一条边,先输出编号小的点,再输出编号大的点。
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
数据范围与提示
对于 的数据有 .
对于所有数据有 $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$.