No tags yet

No tag edit access

time limit per test: 0.25 sec.

memory limit per test: 4096 KB

memory limit per test: 4096 KB

input: standard input

output: standard output

output: standard output

There is a NxN squared chessboard (1<=N<=40). P squares were removed from the chessboard (0<=P<N*N). It is necessary to find out whether it is possible to cover the remaining part of the chessboard with dominoes dice (each die is 2x1 squares sized). Each die should lie on two neighboring squares exactly. No two dice can cover one and the same square. Your task is to find the covering, if it exists.

The first line contains two integer numbers N and P separated by a space. Each of the following P lines contains a pair of numbers separated by a space - coordinates of the removed square (1<=Xi, Yi<=N). The bottom left square has the coordinates (1, 1), the bottom right square - (N, 1).

If the covering exists, output "Yes" to the first line and "No" in the opposite case. If the first answer was positive, then output to the second line integer number Nh - the number of horizontally placed dice. Each of the following Nh lines should contain two integers - the coordinates of the left square covered by a corresponding die. Output to the next line Nv - the number of vertically placed dice. And the following Nv lines should contain the coordinates of the bottom square covered by a corresponding die.

Input

4 10

1 3

1 2

1 1

2 1

3 1

4 1

3 2

4 2

3 3

4 3

1 3

1 2

1 1

2 1

3 1

4 1

3 2

4 2

3 3

4 3

Output

Yes

2

1 4

3 4

1

2 2

2

1 4

3 4

1

2 2

Author: | Michael R. Mirzayanov |

Resource: | ACM International Collegiate Programming Contest 2003-2004 North-Eastern European Region, Southern Subregion |

Date: | 2003 October, 9 |

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/23/2019 17:12:30 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|