CF1846E1 Rudolf and Snowflakes (simple version)
Description
This is a simple version of the problem. The only difference is that in this version $ n \le 10^6 $ .
One winter morning, Rudolf was looking thoughtfully out the window, watching the falling snowflakes. He quickly noticed a certain symmetry in the configuration of the snowflakes. And like a true mathematician, Rudolf came up with a mathematical model of a snowflake.
He defined a snowflake as an undirected graph constructed according to the following rules:
- Initially, the graph has only one vertex.
- Then, more vertices are added to the graph. The initial vertex is connected by edges to $ k $ new vertices ( $ k > 1 $ ).
- Each vertex that is connected to only one other vertex is connected by edges to $ k $ more new vertices. This step should be done at least once.
The smallest possible snowflake for $ k = 4 $ is shown in the figure.
After some mathematical research, Rudolf realized that such snowflakes may not have any number of vertices. Help Rudolf check if a snowflake with $ n $ vertices can exist.
Input Format
N/A
Output Format
N/A