#P1416. 攻击火星

攻击火星

题目描述

一群外星人将要攻击火星。

火星的地图是一个 nn 个点的无向图。这伙外星人将按照如下方法入侵,先攻击度为 00 的点(相当于从图中删除掉它),然后是度为 11 的点,依此类推直到度为 n1n-1 的点。

所有的点度统计是动态统计的。(一个点删掉后,与之相连的点的点度都会 1-1)。外星人攻击度为某个数的点时是同时攻击的。

你需要设计这个图的边的方案来使得未被攻击的点最多。注意:你设计的图不允许自环及重边

输入格式

输入文件包含一行一个整数 nn

输出格式

一行一个整数,表示最多的最后未被攻击的点。

3
1

提示

【样例解释】

一种可能的方案是 1231\leftrightarrow 2\leftrightarrow 3,这样首先删掉度为 11 的点 11 和点 33,此时点 22 度数为 00,不会被删去。

【数据范围】

  • 对于 20%20\% 的数据 1n101\le n\le 10
  • 对于 100%100\% 的数据 1n5×1041\le n\le 5\times 10^4

【题目来源】

tinylic改编