Untitled

class Solution {
public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions,
                                    vector<vector<int>>& colConditions) {
        vector<pair<int, int>> pos(k + 1);
        vector<vector<int>> ans;
        for (int i = 0; i < k; ++i) {
            pos[i + 1] = pair{i, i};
        }

        int cnt = k + 1;
        bool invalid = true;
        while (invalid && cnt--) {
            invalid = false;
            for (auto& r : rowConditions) {
                int above = r[0];
                int below = r[1];
                if (pos[above].second > pos[below].second) {
                    invalid = true;
                    int tmp = pos[above].second;
                    pos[above] = pair{pos[above].first, pos[below].second};
                    pos[below] = pair{pos[below].first, tmp};
                }
            }
        }

        if (cnt == -1) return ans;

        cnt = k + 1;
        invalid = true;
        while (invalid && cnt--) {
            invalid = false;
            for (auto& c : colConditions) {
                int left = c[0];
                int right = c[1];
                if (pos[left].first > pos[right].first) {
                    invalid = true;
                    int tmp = pos[left].first;
                    pos[left] = pair{pos[right].first, pos[left].second};
                    pos[right] = pair{tmp, pos[right].second};
                }
            }
        }

        if (cnt == -1) return ans;

        ans.resize(k, vector<int>(k));
        for (int i = 1; i <= k; ++i) {
            ans[pos[i].second][pos[i].first] = i;
        }
        return ans;
    }
};