We may consider that Snuke walks on a bipartite graph with \(9\) vertices and \(12\) edges.

We determine how many times he passes through each edge. Here, the following condition must be satisfied.

• For each vertex, the sum of the number of times he passes through all of its incident edges is equal to \(2\times A_{i,j}\)
• After removing the edges which is not passed through at all, the residue graph is connected

Actually, if these conditions are met, a solution always exists.

1. Determine the number of times that each edge is passed through

In order to guarantee the connectivity, we choose a nine-vertex tree and assume that each edge of the tree is passed through at least once.

Once a tree is fixed, we compute the maximum flow to find the conditions of degrees.

Since there are at most \(2^{12}\) kinds of trees, we may brute force through all of them.

2. Actually construct the solution

We construct an solution just as constructing an Euler tour.

Specifically, we manage how many times each edge was passed through while doing DFS, and record the trace in the postorder.

As a reference, the following is a code to construct an Euler tour.

vector<int> euler_circuit(vector<vector<pair<int, int>>> G, int n, int m) {
    vector<int> path;
    vector<bool> used(m, false);
    function<void(int)> dfs=[&](int i) {
        for(pair<int, int> x : G[i]) { // x = (destination vertex index, edge index)
            if(!used[x.second]) {
                used[x.second] = true;
                dfs(x.first);
            }
        }
        path.push_back(i);
    };
    dfs(0);
    reverse(path.begin(), path.end());
    return path;
}

Sample code (C++)：https://atcoder.jp/contests/abc227/submissions/27198758