Bishops

시간 제한2초메모리 제한2048 MB

요약

n x m 체스판에 서로 공격하지 않는 비숍을 최대로 놓고 그 좌표를 출력한다.

난이도: 보통10점 중 4점
유형: 그리디, 구현, 수학
정답자: 아직 제출이 없습니다

문제

A chess bishop attacks every square that shares a diagonal with it.

Place the maximum number of bishops on an $n \times m$ chessboard in such a way that none of them attack each other.

입력

The first line contains two integers $n$ and $m$ : the dimensions of the chessboard ( $1 \leq n, m \leq 10^5 + 1$ ).

출력

On the first line, print an integer $k$ : the maximum possible number of bishops on an $n \times m$ chessboard such that they don't attack each other. On each of the next $k$ lines, print two integers: the coordinates of bishops. The first coordinate should be in the range $\[1, n]$ , and the second in the range $\[1, m]$ . If there are several possible answers, print any one of them.

예제2

예제 1
입력
```
2 5
```
예상 출력
```
6
2 5
1 5
2 3
1 1
1 3
2 1
```
예제 2
입력
```
5 5
```
예상 출력
```
8
1 1
1 2
5 4
1 3
5 3
1 4
5 2
1 5
```