P1416 Attacking Mars

A group of aliens are going to attack Mars. The map of Mars is an undirected graph with $n$ vertices. The aliens invade as follows: they first attack vertices of degree $0$ (equivalently, delete them from the graph), then vertices of degree $1$, and so on up to degree $n-1$. All degree counts are updated dynamically. After a vertex is deleted, the degrees of its adjacent vertices all decrease by $1$. When attacking vertices of a certain degree, the aliens attack them simultaneously. You need to design the edges of the graph to maximize the number of vertices that remain un-attacked. Note: the graph you design **does not allow self-loops or multiple edges**.

The input contains one line with an integer $n$.

Output a single integer, the maximum number of vertices that remain un-attacked in the end.

[Sample Explanation] One possible construction is $1\leftrightarrow 2\leftrightarrow 3$. In this case, vertices $1$ and $3$ with degree $1$ are deleted first. Then vertex $2$ has degree $0$ and will not be deleted. [Constraints] - For $20\%$ of the testdata, $1\le n\le 10$. - For $100\%$ of the testdata, $1\le n\le 5\times 10^4$. [Source] Adapted by tinylic. Translated by ChatGPT 5