시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 252 77 72 40.678%

문제

현욱은 어느 신비한 밀림에서 1년간 열심히 스승님의 수행을 돕고 그 보상으로 보물 상자를 하나 받았다. 이 상자에는 1번 버튼부터 N번 버튼까지 총 N개의 버튼이 있는데, 이 중에 하나의 버튼만이 상자를 열 수 있는 버튼이고 나머지 버튼은 잘못된 버튼이다. 버튼을 하나만 누를 경우, 잘못된 버튼을 누르면 상자는 영영 열 수 없게 돼버린다.

상자의 버튼은 여러 개를 동시에 누를 수도 있는데, 동시에 누를 경우 누른 버튼에 올바른 버튼이 포함되어 있으면 상자에서 딩동 소리가 나고, 그렇지 않으면 삐삐 소리가 난다. 이 경우 잘못된 버튼들만 눌러도 상자를 못 열게 되지는 않는다.

하지만, 버튼 여러 개를 동시에 누를 때엔 바로 답을 알려주는 게 아니라 버튼을 누르고 10분~20분쯤 지나야 소리가 나는데, 참을성이 없는 현욱은 최대한 빨리 정답 버튼이 무엇인지 확인하고 싶다.

또 현욱은 머리를 쓰는 걸 싫어해서, 어떤 정해진 버튼들을 쭉 눌러보고 그 결과로부터 정답 버튼을 바로 알아낼 방법을 찾고 싶다. 즉, 정답 버튼이 무엇이든 상관없이 항상 정해진 순서대로 같은 버튼 쌍들을 눌러보기만 하면 정답 버튼을 찾을 수 있는 방법을 알고 싶다.

현욱을 도와, 어떠한 경우에도 올바른 버튼이 무엇인지 확인할 수 있으려면 최소 몇 번 버튼들을 누른 결과를 확인해봐야 하는지와 그때 눌러야 하는 각각의 버튼 집합들을 출력하는 프로그램을 작성해보자.

입력

첫째 줄에 정수 N이 주어진다.

출력

첫째 줄에 최소한으로 테스트해보아야 하는 횟수 K를 출력한다.

둘째 줄부터 한 줄에 하나씩 한 번에 눌러 볼 버튼 쌍을 K줄에 걸쳐 출력한다. 각 줄의 첫 번째 수는 한 번에 같이 눌러 볼 버튼 쌍의 개수 Ki이고, 그다음 Ki개 수는 같이 눌러 볼 버튼의 번호이다. Ki는 반드시 2 이상의 수여야 한다.

답이 여러 가지라면 그 중 아무것이나 출력해도 된다.

제한

  • 3 ≤ N ≤ 105

서브태스크 1 (3점)

  • 3 ≤ N ≤ 6

서브태스크 2 (4점)

  • 추가 제한 없음

예제 입력 1

3

예제 출력 1

2
2 1 3
2 1 2

출처

Contest > 소프트콘 > 제2회 소프트콘 C번

채점

  • 예제는 채점하지 않는다.