国际活动 International Event

有一个盛大的国际活动，一年举办一届。在活动现场，有N(2≤N≤100000)个旗杆排成一行，每个旗杆上都有一面国旗迎风飘扬。 每个旗杆用3个数$l_i, a_i, b_i$表示，即旗杆的坐标为$l_i$，去年挂着国家$a_i$的国旗，今年需要换成国家$b_i$的国旗。你有一个机器人，初始位置为A，要求为机器人设计一条路线，把所有旗杆上的国旗换成今年的，且移动总距离最小。 国家编号为1～M(1≤M≤1000)，且每个国家的国旗至少挂在一个旗杆上，并且去年和今年的旗杆数不变(即对于任意1≤c≤M，满足$a_i$＝c的i的个数等于满足$b_j$＝c的j的个数)。 假设机器人的手很大，可以捧着任意多面国旗。如图12-80所示，每个旗杆用两个数$(a_i,b_i)$表示，箭头表示了最优路径：4-5-1-7-4。 

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=825&page=show_problem&problem=4564 [PDF](https://uva.onlinejudge.org/external/16/p1689.pdf)