룩
시간 제한0.4초메모리 제한1024 MB
장애물이 있는 N x N 보드에서 같은 줄에 있어도 장애물 사이에 있으면 서로 공격하지 않는 조건으로 룩을 최대한 많이 배치하고 그 배치를 출력한다.
문제
N개의 행(랭크)과 N개의 열(파일)로 이루어진 정사각형 판을 생각하자. K개의 칸은 장애물로 막혀 있다. 이 판 위에 체스의 룩과 비슷한 기물을 놓는다. 두 룩이 같은 랭크나 파일에 있고 그 사이에 장애물이 없으면 두 룩이 서로 공격한다고 한다.
양의 정수 N과 K개의 장애물의 위치가 주어질 때, 어떤 두 룩도 서로 공격하지 않도록 판 위에 룩을 최대한 많이 놓아라.
입력
첫째 줄에 N과 K가 공백을 사이에 두고 주어진다. 다음 K개의 줄에는 장애물의 랭크와 파일을 나타내는 두 수 r과 f가 공백을 사이에 두고 주어진다. 모든 장애물은 서로 다르다.
출력
첫째 줄에 판에 놓을 수 있는 서로 공격하지 않는 룩의 최대 개수 S를 출력한다. 다음 S개의 줄에는 룩의 랭크와 파일을 나타내는 두 수 r과 f를 공백을 사이에 두고 출력한다. S개의 룩을 올바르게 배치한 것이면 어떤 것이든 정답으로 인정된다.
제한
- 1 ≤ N ≤ 1,000
- 1 ≤ K ≤ min(N2, 2,000)
- 랭크와 파일은 1부터 N까지 번호가 매겨진다.