크기가 인 격자가 있다. 처음에는 모든 칸이 멀쩡하다.
격자의 칸 중 정확히 개를 박살낸다. 그 후 박살나지 않은 개의 칸에 을 각각 정확히 한 번씩 적는다.
두 정수 가 를 만족한다고 하자. 인 정수 가 적힌 칸들만 남겨 보았을 때, 이 칸들이 하나의 연결 컴포넌트를 이루면 구간 을 이라고 한다. 두 칸은 변을 공유할 때에만 인접하다.
모든 구간 이 좋은 구간이 아니도록 하고 싶다. 박살내야 하는 칸의 개수 의 최솟값을 구하고, 그 최솟값을 달성하는 격자의 구성을 하나 찾아라.
박살나지 않은 칸이 개 이하라면 을 만족하는 구간이 존재하지 않으므로 조건을 자동으로 만족한다.
입력은 다음과 같은 형식으로 주어진다.
첫째 줄에 박살내야 하는 칸의 개수의 최솟값 를 출력한다.
다음 개의 줄에 각각 개의 정수 을 출력하여 격자의 구성을 나타낸다.
가능한 최적 구성이 여러 가지라면 아무거나 출력해도 된다.
