编程介的小学生 2017-04-02 03:08 采纳率: 20.5%
浏览 659
已采纳

Cake Robbery

As usual, Alice finishes her delicious cake at noon. Unfortunately, the smell of cake beckoned hungry Bob, and he decided to rob one piece of cake.

The cake is a convex polygon with N edges. At the beginning, Bob cut it along the diagonals. After M cuts, Bob decided to rob the 'largest' piece of cake. Strangely, in Bob's opinion, the piece has the most number of edge is the biggest one.

Please help Bob to find the 'largest' piece.

Input

There are multiple test cases (about 20).

The first line of each test case contains two integer number N, M (5 <= N <= 10000), indicating the number of point of the cake and the cut, respectively.

The following M lines contain two integer x, y (1 <= x, y <= N), denoting the index of the starting and ending cut point. (the index of points mark from 1 to N clockwise.)

The input will guarantee that all of the cuts will not intersect inside the cake, but they may cross each other at the edge of cake, and Bob won't cut along the initial edge of the cake.

Output

Output the maximal size (most number of edges) of the piece which Bob will get.

Sample Input

7 2
3 6
7 2
Sample Output

4

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-04-12 15:30
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型