曹文信息在线OJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

6088: infrnd

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：18 Solved：15
SubmitSubmit RecordStatisticsWeb BoardShowOff!

Description

现在有N头奶牛，每个奶牛有一个编号，编号都是在1到N之间的而且是唯一的。你知道某些奶牛之间的朋友关系，而每一对朋友之间的distance就是他们编号的差，现在你需要最小化所有的朋友关系distance的总和，当然也就是给奶牛们编号。

Input

第一行两个整数N和F，F表示奶牛朋友关系的总数。（N小于30，F小于4*N）
下面F行每行两个整数a,b，表示第a头奶牛和第b头奶牛是朋友。（他们还没有编号）

Output

输出最小的distance总和。

Sample Input Copy 

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

Sample Output Copy 

8

HINT

样例给奶牛的编号 1 2 3 5 6 4