시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB52266.667%

문제

Dana je $N \times N$ šahovska ploča. Odredite najveći broj kraljica koji se može postaviti na ploču, poštujući sljedeće pravilo:

Kraljicu je dozvoljeno staviti na bilo koje prazno polje koje trenutno napada paran broj već postavljenih kraljica.

Napomena: Jednom kad je postavljena na ploču, kraljica napada sva polja u istom retku, stupcu i na dijagonalama.

입력

U prvom i jedinom retku je prirodan broj $N$, dimenzija šahovske ploče.

출력

U prvi redak ispišite prirodan broj $K$, najveći broj kraljica koji se može postaviti na ploču poštujući zadano pravilo.

U $i$-tom od sljedećih $K$ redaka ispišite prirodne brojeve $R_i$ i $S_i$, redak i stupac u koji je stavljena $i$-ta kraljica.

Ako postoji više načina za postaviti kraljice, ispišite bilo koji.

서브태스크

번호배점제한
16

$1 ≤ N ≤ 16$

211

$1 ≤ N ≤ 64$

328

$1 ≤ N ≤ 256$

455

$1 ≤ N ≤ 1024$

예제 입력 1

1

예제 출력 1

1
1 1

예제 입력 2

2

예제 출력 2

1
1 1

예제 입력 3

3

예제 출력 3

9
2 3
3 1
2 2
1 1
3 3
3 2
1 2
1 3
2 1

채점 및 기타 정보

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