DMOPC '20 Contest 4 P2 - Beautiful Grids

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Penelope is playing a game on a N\times M grid! Her grid currently contains K 1s, while the rest of her grid cells contain 0s.

Penelope isn't sure she likes her grid though. Specifically, she is worried that her grid isn't beautiful. A grid is beautiful if every row sum and column sum are even.

Penelope is in a hurry to make her grid beautiful so she asks you: how can she make her grid beautiful? On each move, you can flip the value of a grid cell: from 1 to 0 or 0 to 1. Since she is in a hurry, she asks you to make her grid beautiful as fast as possible.

Constraints

1 \le N,M \le 10^{18}

0 \le K \le \min(N \cdot M, 3 \times 10^5)

1 \le a_i \le N

1 \le b_i \le M

All cells given are distinct.

Subtask 1 [30%]

1 \le N, M \le 5000

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains 3 integers, N, the number of rows; M, the number of columns; and K.

The next K lines each contain two integers a_i and b_i, indicating that the cell in the a_i^\text{th} row, b_i^\text{th} column contains a 1.

Output Specification

On the first line output A, the minimum number of moves required to make the grid beautiful. A must satisfy 0 \le A \le 10^6. It can be proven that the minimum A lies within this range.

On the next A lines, output two space-separated integers a_i and b_i, indicating that you will flip the cell in the a_i^\text{th} row, b_i^\text{th} column.

You may output any valid sequence.

Note: your output must follow the standard convention of not having any extra whitespace, and it must end with a new line.

Scoring

If you output an incorrect value A, but a valid sequence of moves, you will receive 10\% for that test case.

If you output a correct value A, but an invalid sequence of moves, you will receive 20\% for that test case.

If you output a correct value of A and any valid sequence of moves, you will receive 100\% for that test case.

Your score for a subtask will be the minimum score across all test cases of that subtask.

Sample Input

2 3 3
1 1
1 3
2 1

Sample Output

1
2 3

Explanation

Note that after our operation, our grid is:

1 0 1
1 0 1

which satisfies the constraints.


Comments

There are no comments at the moment.