Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Colorful Friendship

By whoisshihab · Limits 3s, 512 MB

N friends are playing a game. N-1 of them have seated circling one person. So, there are N-1 adjacent pairs of friend, the centered friend and every other N-1 friends are adjacent pairs (when N > 1).

In how many minimum colors you can label them. No two adjacent friends can be labeled with the same color.

Input

Input consists of a single integer N (1 ≤ N ≤ 108) denoting the numbers of friends.

Output

Print a single integer X where X is the number of colors required to label all of the N friends.

Samples

InputOutput
3
2

If N = 3 and we have two colors Green and Black, we can color them this way.

Discussion
Submit

Login to submit