DMOPC '21 Contest 9 P4 - Ace of Diamonds

View as PDF

Submit solution


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

Author:
Problem type

Amidst his journey through the Borderlands, Arisu stumbles upon a diamonds game involving an N \times M grid of coins. The goal of the game is to remove all of the coins, one by one, under the following two conditions:

  1. A coin may only be removed from the grid if it is heads.
  2. When a coin is removed, the coins in the cells that share an edge with it are flipped (if they exist).

Unfortunately, diamonds is not one of Arisu's strong suits. Help him beat the game, or determine that it's impossible to do so!

Constraints

1 \le N \times M \le 10^6

N and M are both odd positive integers.

Subtask 1 [25%]

N = 1

Subtask 2 [75%]

No additional constraints.

Input Specification

The first line contains 2 integers N and M.

The next N lines each contain a string of M characters. The j-th character of the i-th string is H if the coin in cell (i, j) is initially heads, or T if it is initially tails.

Output Specification

If it is impossible to beat the game, output -1 on its own line.

Otherwise, output N \times M lines. The i-th of these should contain 2 space-separated integers r_i (1 \le r_i \le N) and c_i (1 \le c_i \le M), indicating that the coin in cell (r_i, c_i) should be the i-th coin removed. If there are multiple valid solutions, output any of them.

Sample Input 1

3 3
HTH
THT
HTH

Sample Output 1

2 2
1 1
1 3
3 1
3 3
1 2
2 1
2 3
3 2

Sample Input 2

1 3
HHT

Sample Output 2

-1

Comments

There are no comments at the moment.