FootballAndLie.java

import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class FootballAndLie implements Closeable {

    private InputReader in = new InputReader(System.in);
    private PrintWriter out = new PrintWriter(System.out);

    public void solve() {
        int n = in.ni();
        init(2 * n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = in.ni();
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (grid[i][j] == -1 || grid[j][i] == -1) continue;
                if (grid[i][j] == grid[j][i]) {
                    if (grid[i][j] == 0) {
                        imply(2 * i, 2 * j);
                    } else {
                        imply(not(2 * i), not(2 * j));
                    }
                    imply(not(2 * i), 2 * j);
                    imply(2 * i, not(2 * j));
                } else if (grid[i][j] == 0) {
                    imply(2 * i, 2 * j);
                    imply(not(2 * i), not(2 * j));
                    imply(2 * i, not(2 * j));
                } else {
                    imply(2 * i, 2 * j);
                    imply(not(2 * i), not(2 * j));
                    imply(not(2 * i), 2 * j);
                }
            }
        }
        kosaraju();
        
        boolean[] liar = new boolean[n];
        boolean possible = true;
        for (int i = 0; i < n; i += 2) {
            if (component[i] == component[i + 1]) {
                possible = false;
                break;
            }
            liar[i] = component[i] > component[i + 1];
        }
        if (!possible) {
            out.println("Impossible");
            return;
        }
        
        int[][] result = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (liar[i]) {
                    if (liar[j]) {
                        //i and j are both liars
                        if (grid[i][j] == -1 && grid[j][i] == -1) {
                            result[i][j] = result[j][i] = 1;
                        } else if (grid[i][j] == -1) {
                            if (grid[j][i] == 1) {
                                result[j][i] = 0; result[i][j] = 3;
                            } else {
                                result[j][i] = 3; result[i][j] = 0;
                            }
                        } else if (grid[j][i] == -1) {
                            if (grid[i][j] == 1) {
                                result[i][j] = 0; result[j][i] = 3;
                            } else {
                                result[i][j] = 3; result[j][i] = 0;
                            }
                        } else {
                            if (grid[i][j] == grid[j][i] && grid[i][j] == 0) {
                                result[i][j] = result[j][i] = 1;
                            } else {
                                result[i][j] = grid[j][i] * 3;
                                result[j][i] = grid[i][j] * 3;
                            }
                        }
                    } else {
                        //i is a liar, but j tells the truth
                        if (grid[i][j] == -1 && grid[j][i] == -1) {
                            result[i][j] = result[j][i] = 1;
                        } else if (grid[i][j] == -1) {
                            if (grid[j][i] == 1) {
                                result[j][i] = 3; result[i][j] = 0;
                            } else {
                                result[j][i] = 0; result[i][j] = 3;
                            }
                        } else if (grid[j][i] == -1) {
                            if (grid[i][j] == 1) {
                                result[i][j] = 0; result[j][i] = 3;
                            } else {
                                result[i][j] = 3; result[j][i] = 0;
                            }
                        } else {
                            if (grid[j][i] == 1) {
                                result[i][j] = 0; result[j][i] = 3;
                            } else {
                                result[i][j] = 3; result[j][i] = 0;
                            }
                        }
                    }
                } else {
                    if (liar[j]) {
                        //i tells the truth, but j is a liar
                        if (grid[i][j] == -1 && grid[j][i] == -1) {
                            result[i][j] = result[j][i] = 1;
                        } else if (grid[i][j] == -1) {
                            if (grid[j][i] == 1) {
                                result[i][j] = 3; result[j][i] = 0;
                            } else {
                                result[i][j] = 0; result[j][i] = 3;
                            }
                        } else if (grid[j][i] == -1) {
                            if (grid[i][j] == 1) {
                                result[i][j] = 3; result[j][i] = 0;
                            } else {
                                result[i][j] = 0; result[j][i] = 3;
                            }
                        } else {
                            if (grid[i][j] == 1) {
                                result[i][j] = 3; result[j][i] = 0;
                            } else {
                                result[i][j] = 0; result[j][i] = 3;
                            }
                        }     
                    } else {
                        //i and j both tell the truth
                        if (grid[i][j] == -1 && grid[j][i] == -1) {
                            result[i][j] = result[j][i] = 1;
                        } else if (grid[i][j] == -1) {
                            if (grid[j][i] == 0) {
                                result[i][j] = 3; result[j][i] = 0;
                            } else {
                                result[i][j] = result[j][i] = 1;
                            }
                        } else if (grid[j][i] == -1) {
                            if (grid[i][j] == 0) {
                                result[j][i] = 3; result[i][j] = 0;
                            } else {
                                result[i][j] = result[j][i] = 1;
                            }
                        } else {
                            if (grid[i][j] == 1) {
                                if (grid[j][i] == 1) {
                                    result[i][j] = result[j][i] = 1;
                                } else {
                                    result[i][j] = 3;
                                }
                            } else {
                                result[j][i] = 3;
                            }
                        }
                    }
                }
            }
        }
        print(result);
    }

    private void print(int[][] result) {
        for (int[] row : result) {
            for (int value : row) {
                out.print(value);
                out.print(' ');
            }
            out.println();
        }
    }

    private int[][] grid;
    private List<List<Integer>> graph = new ArrayList<>(), reverse = new ArrayList<>();
    private List<Integer> order = new ArrayList<>();
    private boolean[] visited;
    private int[] component;
    
    private void init(int n) {
        grid = new int[n / 2][n / 2];
        visited = new boolean[n];
        component = new int[n];
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
            reverse.add(new ArrayList<>());
        }
    }
    
    private int not(int value) {
        return value ^ 1;
    }
    
    private void imply(int from, int to) {
        graph.get(from).add(to);
        reverse.get(to).add(from);
    }
    
    private void kosaraju() {
        int n = graph.size();
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs1(i);
            }
        }
        int c = 0;
        for (int i = n - 1; i >= 0; i--) {
            int node = order.get(i);
            if (visited[node]) {
                dfs2(node, c++);
            }
        }
    }
    
    private void dfs1(int u) {
        visited[u] = true;
        for (int v : graph.get(u)) if (!visited[v]) dfs1(v);
        order.add(u);
    }
    
    private void dfs2(int u, int cmp) {
        visited[u] = false;
        component[u] = cmp;
        for (int v : reverse.get(u)) if (visited[v]) dfs2(v, cmp);
    }
    
    @Override
    public void close() throws IOException {
        in.close();
        out.close();
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int ni() {
            return Integer.parseInt(next());
        }

        public long nl() {
            return Long.parseLong(next());
        }

        public void close() throws IOException {
            reader.close();
        }
    }

    public static void main(String[] args) throws IOException {
        try (FootballAndLie instance = new FootballAndLie()) {
            instance.solve();
        }
    }
}

Wrong test cases:

input:
3
-1 1 1
0 -1 0
1 1 -1
output:
0 3 1 (Not liar)
0 0 0 (Not liar)
1 3 0 (Not liar)

input:
5
-1 1 1 0 0
0 -1 1 -1 -1
1 0 -1 -1 -1
0 -1 -1 -1 1
1 -1 -1 0 -1
output:
Impossible

input:
13
-1 0 -1 1 0 1 -1 0 1 0 1 0 1
-1 -1 0 0 -1 -1 0 1 0 1 0 0 -1
-1 1 -1 0 1 -1 0 1 -1 0 1 0 -1
-1 0 -1 -1 -1 -1 0 0 0 -1 -1 -1 0
-1 0 -1 1 -1 0 0 1 1 -1 1 1 1
0 0 -1 1 -1 -1 1 0 0 1 1 1 -1
-1 -1 -1 1 -1 0 -1 0 0 1 -1 -1 -1
1 0 -1 0 -1 -1 -1 -1 1 -1 -1 1 0
1 1 0 -1 0 0 0 -1 -1 0 -1 -1 1
0 -1 1 -1 -1 -1 1 -1 -1 -1 0 1 -1
0 -1 -1 1 0 0 -1 0 -1 -1 -1 -1 -1
1 1 1 0 1 1 -1 0 -1 -1 -1 -1 -1
0 -1 0 -1 0 1 0 0 -1 -1 0 1 -1

output:
0 3 1 0 3 0 0 1 0 3 0 1 0
0 0 0 0 3 0 0 3 0 3 0 0 3
1 3 0 0 3 3 0 3 3 0 3 0 0
3 3 3 0 0 3 3 3 3 1 3 3 3
0 0 0 3 0 0 0 3 3 1 1 1 1
3 3 0 0 3 0 0 3 3 0 0 0 3
3 3 3 0 3 3 0 3 3 0 0 1 0
1 0 0 0 0 0 0 0 3 1 0 3 0
3 3 0 0 0 0 0 0 0 0 3 1 3
0 0 3 1 1 3 3 1 3 0 0 3 3
3 3 0 0 1 3 3 3 0 3 0 1 0
1 3 3 0 1 3 1 0 1 0 1 0 3
3 0 3 0 1 0 3 3 0 0 3 0 0