Tam đẳng cấu (Tri-Isomorphism)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một đồ thị đơn không có khuyên và không có đa cạnh. Hai đồ thị được gọi là đẳng cấu nếu tồn tại một song ánh giữa các tập đỉnh sao cho hai đỉnh kề nhau ở đồ thị thứ nhất khi và chỉ khi hai đỉnh tương ứng kề nhau ở đồ thị thứ hai.

$K_n$ là đồ thị đầy đủ trên $n$ đỉnh, tức mọi cặp đỉnh khác nhau đều được nối bởi một cạnh.

Một phân rã của đồ thị là một danh sách các đồ thị con sao cho mỗi cạnh của đồ thị ban đầu xuất hiện trong đúng một đồ thị con.

Cho $n$. Hãy xác định liệu có thể phân rã $K_n$ thành đúng ba đồ thị con đôi một đẳng cấu hay không.

Input

Một số nguyên dương $n$.

Output

In YES nếu tồn tại phân rã như yêu cầu, ngược lại in NO.

Subtask

• Subtask 1 (20%): $n\le20$.
• Subtask 2 (30%): $21\le n\le100$ và $n\equiv0$ hoặc $1\pmod3$.
• Subtask 3 (50%): Đầy đủ: $1\le n\le100$.

Ví dụ

Input

4

Output

YES

Giải thích

$K_4$ có $\binom42=6$ cạnh, có thể chia thành ba nhóm, mỗi nhóm $2$ cạnh và ba nhóm có cùng cấu trúc sau một phép đổi tên đỉnh. Điều kiện phân rã thỏa mãn, nên in YES.