A vertical farm arranges its crop trays in a grid of m rows and n columns, and every tray starts with zero recorded waterings. Over the course of a day the farm runs k irrigation cycles. In the i-th cycle, an automated arm is aimed at row r_i and column c_i: every tray in row r_i receives one watering, and every tray in column c_i receives one watering (a tray that sits at the intersection of the chosen row and the chosen column is watered twice during that cycle -- once for the row pass and once for the column pass). After all k cycles have run, the farm's controller needs to know how many trays ended the day with an odd total number of waterings.
The first line contains three space-separated integers m n k.
Each of the next k lines contains two space-separated integers r c (the row and column targeted by that cycle).
A single integer: the number of trays (cells of the m x n grid) whose total number of waterings, summed over all k cycles, is odd.
Example 1
Input
2 3 2 0 1 1 1
Expected
6
Explanation
Cycle 1 targets row 0 and column 1; cycle 2 targets row 1 and column 1. Counting how many times each row and column line was hit: row 0 was hit once and row 1 was hit once (both odd), while column 0 was hit zero times, column 1 was hit twice, and column 2 was hit zero times (all even). A tray's total waterings equal its row's hit count plus its column's hit count, and that sum is odd exactly when one of the two counts is odd and the other is even. Since every row count is odd and every column count is even here, all 2*3 = 6 trays end up with an odd total, so the answer is 6.
Example 2
Input
1 1 1 0 0
Expected
0
Explanation
With a single tray (m=n=1) and one cycle aimed at row 0, column 0, that tray is watered once for the row pass and once for the column pass, for a total of 2 waterings -- an even number. No tray has an odd total, so the answer is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →