M. [POI 2012] TOU-Tour de Byteotia

Type: RemoteJudge

1500ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

给定一个 $n$ 个点 $m$ 条边的无向图，问最少删掉多少条边能使得编号小于等于 $k$ 的点都不在任何一条简单环上。

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

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

第一行一个整数 $cnt$ ，表示最少的删边数量；

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

样例配图如下：

对于 $40\%$ 的数据有 $n \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$.

翻译来自于 LibreOJ。