연극

N명의 배우가 있다. 한 장면은 무대 위에 서 있는 배우들의 집합으로 표현한다. 연극은 연속된 K개의 장면으로 이루어지며, 다음 조건을 모두 만족해야 한다.

1. 각 장면에는 적어도 한 명의 배우가 무대 위에 있어야 한다.
2. 한 장면이 진행되는 동안에는 무대 위 배우 구성이 바뀌지 않는다.
3. 한 장면이 끝나고 다음 장면으로 넘어갈 때에는 정확히 한 명의 배우만 이동한다. 이동은 무대 밖의 배우 한 명이 들어오거나, 무대 위의 배우 한 명이 나가는 것 중 하나이다.
4. 연극이 시작되기 전과 끝난 뒤에는 무대가 비어 있어야 한다. 따라서 첫 번째 장면과 마지막 장면에는 배우가 한 명만 있어야 한다.
5. 서로 다른 두 장면이 같은 배우 집합을 가져서는 안 된다.
6. 조건을 만족하는 장면 수 K가 최대가 되어야 한다.

배우 수 N이 주어질 때, 가능한 가장 긴 연극을 구성하는 프로그램을 작성하라.

첫째 줄에 자연수 N이 주어진다. (2 ≤ N ≤ 17) 배우들은 1번부터 N번까지 번호가 매겨져 있다.

첫째 줄에 조건을 만족하는 최대 장면 수 K를 출력한다.

둘째 줄에는 첫 번째 장면을 만들기 위해 무대로 들어오는 배우의 번호를 출력한다.

그다음 K-1개 줄에는 각 장면이 끝나고 다음 장면으로 넘어갈 때 이동하는 배우의 번호를 차례대로 출력한다. 해당 배우가 무대 밖에 있으면 들어오고, 무대 위에 있으면 나간다.

마지막 줄에는 마지막 장면이 끝난 뒤 무대에서 나가는 배우의 번호를 출력한다. 가능한 구성이 여러 가지라면 그중 아무 것이나 출력해도 된다.