P5427 [USACO19OPEN] Left Out S

Farmer John is trying to take a photo of his cows. Based on past experience, he knows that this often does not turn out very well. This time, Farmer John bought an expensive drone and wants to take an aerial photo. To make the photo look as good as possible, he wants all of his cows to face the same direction when the photo is taken. The cows are currently arranged on a fenced pasture in an $N \times N$ ($2 \leq N \leq 1000$) square grid, for example: ``` RLR RRL LLR ``` Here, the character `R` represents a cow facing right, and `L` represents a cow facing left. Since the cows are packed closely together, Farmer John cannot walk up to a single cow and make her turn around. The only thing he can do is shout at an entire row or an entire column of cows to make them turn around, which flips all `L` to `R` and all `R` to `L` in that row or column. Farmer John may issue commands to any number of rows or columns, and may even issue commands multiple times to the same row or column. Just as Farmer John expected, he finds that it is impossible to make all cows face the same direction. The best he can do is to make all cows except one face the same direction. Please find such a cow.

The first line contains $N$. The next $N$ lines describe rows $1 \ldots N$ of the cow grid, each containing a string of length $N$.

Output the row and column coordinates of a cow such that, if that cow were flipped, Farmer John could make all of his cows face the same direction. If no such cow exists, output `-1`. If there are multiple such cows, output the one with the smallest row index; if multiple have the same row index, output the one with the smallest column index.

In this example, the cow at row $1$, column $1$ (the top-left corner) is the annoying cow, because Farmer John can shout at row $2$ and column $3$ to make all cows face left, with only this cow facing right. Translated by ChatGPT 5