[Bài 3 trong chuỗi bài Mỗi tuần một bài toán 2025]

Các coder có thể xem thông tin thêm tại đây: Thông tin về contest

Cho graph đơn vô hướng ~G=(V,E)~ có ~n~ đỉnh, với ~n \ge 3~. Người ta tô màu các cạnh của graph bởi ~m~, mỗi cạnh tô đúng một màu, mỗi màu có thể dùng ~0~, ~1~ hoặc nhiều lần. Ký hiệu ~G(i)~ là graph con của ~G~, có tập đỉnh là ~n~ đỉnh ban đầu và tập cạnh là tất cả các cạnh cùng được tô bởi màu ~i~. Hãy trả lời từng câu hỏi sau đây:

1. Tìm giá trị lớn nhất của ~m~ sao cho các graph ~G(1), G(2), ..., G(m)~ đều là liên thông.

2. Tìm giá trị nhỏ nhất của ~m~ sao cho các graph ~G(1), G(2), ..., G(m)~ đều là lưỡng phân (bipartite).

3. Tìm giá trị nhỏ nhất của ~m~ sao cho các graph ~G(1), G(2), ..., G(m)~ đều là tam phân (tripartite).

Input

Số đỉnh ~n~ của graph với ~3 \le n \le 10^{18}~.

Output

Câu trả lời cho từng câu hỏi.

Sample input

10

Sample output

5 4 3