瓜瓜上电工
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

队友拍醒了瓜瓜,因为电工实验开始了,不能再盯着二极管发呆了。

测量电路电压需要用很多次电压表,每次都要把测量头从一个接线柱上拔下来,再绑到另一个接线柱上,这让他感到烦躁。瓜瓜可以通过调整测量顺序,减小测量头的移动次数。

形式的说,电路有 n 个接线柱,需要测量 q 次电压。当需要测量 (a_i, b_i) 两个接线柱时,瓜瓜需要把测量头从之前的位置移到接线柱上。瓜瓜并没有强迫症,电压表接反了他也会读数。

瓜瓜想知道测量头最少移动几次。注意:初始时,测量头是放在桌子上的,结束时也需要拔下来放在桌子上。

输入描述:

第一行有两个正整数 n, q,其中 

接下来有 q 行,每行有两个正整数 a_i, b_i,其中 。保证不存在相同的 (a_i, b_i)

输出描述:

在一行输出最少的移动步数。
示例1

输入

复制
5 3
1 2
3 4
4 5

输出

复制
7

说明

开始需要把两个测量头接在 (1, 2) 上,移动 2 次。

第一步把 (1, 2) \to (3, 4),移动 2 次。

第二步把 (3, 4) \to (4, 5),移动 1 次。

结尾把两个测量头拔下来,移动 2 次。总共是 7 次。