Description

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.

Input Format

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

Output Format

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

3

1

Hint

[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