p305.cpp
======================
#include <bits/stdc++.h>
// #include <coding_library/graph/hopcroft_karp.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

class HopcroftKarp {
  private:
    int n, m;
    vector<int> dist;

    bool bfs() {
        queue<int> q;
        dist.assign(n, -1);
        for(int u = 0; u < n; u++) {
            if(inv_match[u] == -1) {
                dist[u] = 0;
                q.push(u);
            }
        }

        bool found = false;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(int v: adj[u]) {
                int m = match[v];
                if(m == -1) {
                    found = true;
                } else if(dist[m] == -1) {
                    dist[m] = dist[u] + 1;
                    q.push(m);
                }
            }
        }

        return found;
    }

    bool dfs(int u) {
        for(int v: adj[u]) {
            int m = match[v];
            if(m == -1 || (dist[m] == dist[u] + 1 && dfs(m))) {
                inv_match[u] = v;
                match[v] = u;
                return true;
            }
        }
        dist[u] = -1;
        return false;
    }

  public:
    vector<int> match, inv_match;
    vector<vector<int>> adj;

    HopcroftKarp(int _n, int _m = -1) : n(_n), m(_m == -1 ? _n : _m) {
        adj.assign(n, vector<int>());
        clear(false);
    }

    void clear(bool clear_adj = true) {
        match.assign(m, -1);
        inv_match.assign(n, -1);
        if(clear_adj) {
            adj.assign(n, vector<int>());
        }
    }

    void add_edge(int u, int v) { adj[u].push_back(v); }

    int max_matching(bool shuffle_edges = false) {
        if(shuffle_edges) {
            for(int i = 0; i < n; i++) {
                shuffle(
                    adj[i].begin(), adj[i].end(),
                    mt19937(
                        chrono::steady_clock::now().time_since_epoch().count()
                    )
                );
            }
        }

        int ans = 0;
        while(bfs()) {
            for(int u = 0; u < n; u++) {
                if(inv_match[u] == -1 && dfs(u)) {
                    ans++;
                }
            }
        }
        return ans;
    }

    vector<pair<int, int>> get_matching() {
        vector<pair<int, int>> matches;
        for(int u = 0; u < n; u++) {
            if(inv_match[u] != -1) {
                matches.emplace_back(u, inv_match[u]);
            }
        }
        return matches;
    }

    pair<vector<int>, vector<int>> minimum_vertex_cover() {
        vector<int> left_cover, right_cover;
        bfs();

        for(int u = 0; u < n; u++) {
            if(dist[u] == -1) {
                left_cover.push_back(u);
            }
        }

        for(int v = 0; v < m; v++) {
            if(match[v] != -1 && dist[match[v]] != -1) {
                right_cover.push_back(v);
            }
        }

        return {left_cover, right_cover};
    }
};

using BipartiteMatching = HopcroftKarp;

int n, m;
vector<pair<int, int>> p;

void read() {
    cin >> n >> m;
    p.resize(n);
    cin >> p;
}

void solve() {
    // We can solve this with matching. Create a graph where on one side we have
    // the progressions, while on the other we keep the 1...m values. The main
    // issue is that m might be fairly large, but we can get the first n
    // numbers in the arithmetic progression. We then want the maximum matching.

    vector<vector<int64_t>> candidates(n);
    for(int i = 0; i < n; i++) {
        int64_t a = p[i].first, b = p[i].second;
        if(a == 0) {
            if(b >= 1 && b <= m) {
                candidates[i].push_back(b);
            }
        } else {
            int64_t start_k = 0;
            if(a > 0) {
                if(b < 1) {
                    start_k = (1 - b + a - 1) / a;
                }
            } else {
                if(b > m) {
                    start_k = (b - m + (-a) - 1) / (-a);
                }
            }
            for(int j = 0; j < n; j++) {
                int64_t x = a * (start_k + j) + b;
                if(x < 1 || x > m) {
                    break;
                }
                candidates[i].push_back(x);
            }
        }
    }

    vector<int64_t> all_vals;
    for(int i = 0; i < n; i++) {
        for(int64_t v: candidates[i]) {
            all_vals.push_back(v);
        }
    }
    sort(all_vals.begin(), all_vals.end());
    all_vals.erase(unique(all_vals.begin(), all_vals.end()), all_vals.end());
    int num_vals = all_vals.size();

    auto compress = [&](int64_t v) {
        return lower_bound(all_vals.begin(), all_vals.end(), v) -
               all_vals.begin();
    };

    BipartiteMatching bm(n, num_vals);
    for(int i = 0; i < n; i++) {
        for(int64_t v: candidates[i]) {
            bm.add_edge(i, compress(v));
        }
    }
    bm.max_matching();

    set<int64_t> used;
    vector<int64_t> ans(n, -1);
    for(int i = 0; i < n; i++) {
        if(bm.inv_match[i] != -1) {
            ans[i] = all_vals[bm.inv_match[i]];
            used.insert(ans[i]);
        }
    }

    int64_t next_free = 1;
    for(int i = 0; i < n; i++) {
        if(ans[i] == -1) {
            while(used.count(next_free)) {
                next_free++;
            }
            ans[i] = next_free;
            used.insert(next_free);
            next_free++;
        }
    }

    for(int i = 0; i < n; i++) {
        cout << ans[i] << " \n"[i == n - 1];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
p305.ans1
======================
2 3 1 6 4

=================
p305.in1
======================
5 6
1 1
2 1
3 1
3 1
6 4

=================
statement.txt
======================
305. Exhibition
Time limit per test: 0.75 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



The exhibition of arithmetical progressions will be opened in Berland soon. Each of N presented progressions is characterized by two integer numbers Ai and Bi. These numbers mean that all numbers X belong to the i-th progression if X = Ai*K+Bi for some non-negative integer K. Organizers decided that each sequence will be given a unique number from 1 to M. The organizers want as much as possible progressions to be assigned such a number, that would be a member of this progression. They hired you to do this job.

Input
The first line of the input contains two integer numbers N and M (1≤ N≤ 300; N≤ M≤ 109). Each of the following N lines contains the pair of numbers Ai and Bi (-109≤ Ai, Bi≤ 109).

Output
Write to the output distribution of numbers among sequences — N numbers delimited by spaces. All numbers should be unique. If there are several solutions output any of them.

Example(s)
sample input
sample output
5 6
1 1
2 1
3 1
3 1
6 4
2 3 1 6 4

=================
