import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class MaxFlowStrategy implements Strategy {

    final static int[] DX = {-1, 0, 1, 0};
    final static int[] DY = {0, -1, 0, 1};


    @Override
    public int[] turn(GameState state) {
        Integer best = null;
        int[] ans = null;
        boolean only0 = state.n * state.m > 100;
        if (!only0) {
            for (int x = 0; x < state.n; x++) {
                for (int y = 0; y < state.m; y++) {
                    if (state.field[x][y] == GameState.Cell.FREE) {
                        state.set(x, y, GameState.Cell.GOOD);
                        int now = state.toGraph().maxFlow();
                        state.set(x, y, GameState.Cell.FREE);
                        if (best == null || now > best) {
                            best = now;
                            ans = new int[]{x, y};
                        }
                    }
                }
            }
        }

        Graph noTurnYet = state.toGraph();
        int f = noTurnYet.maxFlow();
        if (only0 || best == f) {
            if (best == null || best == 0) {
                for (int x = 0; x < state.n; x++) {
                    for (int y = 0; y < state.m; y++) {
                        if (state.field[x][y] == GameState.Cell.FREE) {
                            return new int[]{x, y};
                        }
                    }
                }
                throw new AssertionError();
            }

            boolean[][] used = new boolean[state.n][state.m];
            int[][] color = new int[state.n][state.m];
            for (int[] xc : color) {
                Arrays.fill(xc, -1);
            }
            int colors = 0;
            for (int i = 0; i < state.n; i++) {
                for (int j = 0; j < state.m; j++) {
                    if (used[i][j] || state.field[i][j] == GameState.Cell.BAD) {
                        continue;
                    }
                    if (state.field[i][j] == GameState.Cell.FREE) {
                        used[i][j] = true;
                        color[i][j] = colors++;
                    } else {
                        Queue<Integer> q = new ArrayDeque<>();
                        q.add(i);
                        q.add(j);
                        used[i][j] = true;
                        color[i][j] = colors;
                        while (!q.isEmpty()) {
                            int x = q.poll();
                            int y = q.poll();
                            for (int d = 0; d < 4; d++) {
                                int xTo = x + DX[d];
                                int yTo = y + DY[d];
                                if (!(0 <= xTo && xTo < state.n) || !(0 <= yTo && yTo < state.m)) {
                                    continue;
                                }
                                if (!used[xTo][yTo] && state.field[xTo][yTo] == GameState.Cell.GOOD) {
                                    q.add(xTo);
                                    q.add(yTo);
                                    used[xTo][yTo] = true;
                                    color[xTo][yTo] = colors;
                                }
                            }
                        }
                        colors++;
                    }
                }
            }
            boolean[][] a = new boolean[colors][colors];
            for (int x = 0; x < state.n; x++) {
                for (int y = 0; y < state.m; y++) {
                    int c1 = color[x][y];
                    if (c1 == -1) {
                        continue;
                    }
                    for (int d = 0; d < 4; d++) {
                        int xTo = x + DX[d];
                        int yTo = y + DY[d];
                        if (!(0 <= xTo && xTo < state.n) || !(0 <= yTo && yTo < state.m)) {
                            continue;
                        }
                        int c2 = color[xTo][yTo];
                        if (c2 == -1) {
                            continue;
                        }

                        if (c1 != c2) {
                            a[c1][c2] = true;
                        }
                    }
                }
            }

            int[] d = new int[colors];
            Arrays.fill(d, -1);
            d[color[0][0]] = 0;
            Queue<Integer> q = new ArrayDeque<>();
            q.add(color[0][0]);
            while (!q.isEmpty()) {
                int v = q.poll();
                for (Graph.Edge e : noTurnYet.g[v]) {
                    if (e.rev.remain > 0 && !e.isReverse) {
                        if (d[e.to] == -1) {
                            d[e.to] = d[v] + 1;
                            q.add(e.to);
                        }
                    }
                }
            }

            int startC = color[0][0];
            int to = -1;
            c:
            for (Graph.Edge e : noTurnYet.g[startC]) {
                if (e.rev.remain > 0 && !e.isReverse) {
                    if (d[e.to] == d[startC] + 1) {
                        to = e.to;
                        break c;
                    }
                }
            }

            for (int x = 0; x < state.n; x++) {
                for (int y = 0; y < state.m; y++) {
                    if (color[x][y] != startC) {
                        continue;
                    }
                    for (int dd = 0; dd < 4; dd++) {
                        int xTo = x + DX[dd];
                        if (!(0 <= xTo && xTo < state.n)) {
                            continue;
                        }
                        int yTo = y + DY[dd];
                        if (!(0 <= yTo && yTo < state.m)) {
                            continue;
                        }
                        if (color[xTo][yTo] == to) {
                            return new int[]{xTo, yTo};
                        }
                    }
                }
            }

            throw new AssertionError();
        } else {
            return ans;
        }
    }
}
