seuOJ391 - 解锁游戏

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：春季, 夏季, 校赛, 2022

题目描述

log2r有$n$条绳子和$2m$个固定绳子的节点，其中，$m$个节点位于上方，另外$m$个节点位于下方，每条绳子其中一端固定在一个上方节点上，另一端固定在下方节点上，每个节点可以固定任意多条绳子。

现给定初始时刻绳子两端固定的位置，你要进行若干次以下操作：

将绳子的其中一端由一个节点移动到另一个同侧节点（即绳子上端只能在上方节点移动，绳子下端只能在下方节点移动）。

log2r想进行若干次操作后，任意两条绳子除两端点外不交叉，请你求出最少的操作次数是多少？

注意： 绳子之间不存在缠绕和打结，只存在交叉和不交叉两种关系。特别地，若两条绳子两端点重合，则这两条绳子不交叉。

输入格式

第一行为两个整数$n,m(1\leq n,m\leq 10^6)$，分别代表绳子的条数和每一侧固定绳子的节点数。

接下来$n$行，每行两个整数$a_i,b_i(1\leq a_i,b_i\leq m)$，分别代表绳子上端固定在上侧第$a_i$个节点、绳子下端固定在下侧第$b_i$个节点。

输出格式

一个整数，代表最少操作次数。

样例

输入样例

5 6
1 5
4 2
3 3
3 4
6 1

输出样例

3