for (int i = 0; i < 100000; ++i) {
        vector<ipair> path;
        std::random_shuffle(cells.begin(), cells.end());
        path.emplace_back(cells[0]);
        std::unordered_set<int> unused;
        for (size_t r = 1; r < cells.size(); ++r) {
            unused.insert(r);
        }
        for (int k = 1; k < R * C; ++k) {
            int id = -1;
            for (auto x : unused) {
                if (cells[x].first != path.back().first &&
                    cells[x].second != path.back().second &&
                    cells[x].first - cells[x].second != path.back().first - path.back().second &&
                    cells[x].first + cells[x].second != path.back().first + path.back().second) {
                    id = x;
                    break;
                }
            }
            if (id == -1) {
                break;
            }
            path.push_back(cells[id]);
            unused.erase(id);
        }
        if (path.size() == R * C) {
            //cerr << i << endl;
            cout << "POSSIBLE\n";
            for (auto x : path) {
                cout << x.first + 1 << ' ' << x.second + 1 << '\n';
            }
            return;
        }
    }