1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <iostream>
#include <vector>
#include <functional>
#include <stack>
#define SOURCE 0
#define SINK 1
#define VIN(v) (2*(v))
#define VOUT(v) (2*(v) + 1)
using namespace std;
typedef pair<int,int> pii;

struct Edge{
    int target, capacity, flow;
    int rev_it;
};

struct Range{
    int b_from, b_to;
    int result_from, result_to;
};

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

    int n,m,k;
    cin >> n >> m >> k;

    vector<vector<Edge>>G(2+2*n);
    auto add_edge = [&](int from, int to){
        G[from].push_back(Edge{.target=to, .capacity=1, .rev_it=(int)G[to].size()});
        G[to].push_back(Edge{.target=from, .capacity=0, .rev_it=(int)G[from].size()-1});
    };
    //make SOURCE -> [k]
    for (int i=1; i<=k; i++)
        add_edge(SOURCE, VIN(i));
    //make node internal edges
    for (int i=1; i<=n; i++)
        add_edge(VIN(i), VOUT(i));
    //make real edges
    for (int i=0; i<m; i++) {
        int a,b;
        cin >> a >> b;
        add_edge(VOUT(a), VIN(b));
    }
    //make [n-k] -> SINK
    for (int i=k+1; i<=n; i++)
        add_edge(VOUT(i), SINK);
    
    //flow procedures
    vector<bool>Used(G.size());
    function<bool(int)> dfs = [&](int v)->bool{
        Used[v] = true;
        if(v==SINK)
            return true;
        for (Edge &e : G[v])
            if (e.flow < e.capacity && !Used[e.target] && dfs(e.target)) {
                e.flow++;
                G[e.target][e.rev_it].flow--;
                return true;
            }
        return false;
    };
    auto evaluate_many = [&](int a, const vector<pair<int,function<void(int)>>>&B){
        //clear flow
        for (auto &edgelist : G)
            for (Edge &edge : edgelist)
                edge.flow = 0;
        
        //reset capacities
        for (int i=k+1; i<=n; i++)
            G[VOUT(i)].back().capacity = 0;

        int last_set = a-1;
        int result_acc = 0;
        for (auto b : B) {
            //set new sink capacities
            for (int i=last_set+1; i<=b.first; i++)
                G[VOUT(i)].back().capacity = 1;
            last_set = b.first;

            //iterate flow augment for b
            while(true) {
                fill(Used.begin(), Used.end(), false);
                if (dfs(SOURCE))
                    result_acc++;
                else
                    break;
            }

            b.second(result_acc);
        }
    };

    //even better brute force
    vector<long long>Results(k+1);
    for (int a=k+1; a<=n; a++) {
        vector<Range>ranges;
        int init_eval_a=42, init_eval_n=42;
        vector<pair<int,function<void(int)>>> init_orders;
        init_orders.push_back({a, [&](int ev){
            init_eval_a = ev;
        }});
        init_orders.push_back({n, [&](int ev){
            init_eval_n = ev;
        }});
        evaluate_many(a, init_orders);
        ranges.push_back(Range{.b_from=a, .b_to=n, .result_from=init_eval_a, .result_to=init_eval_n});
        
        while(!ranges.empty()) {
            vector<Range>future_ranges;
            vector<pair<int,function<void(int)>>>orders;

            //phase one - make orders
            for (int i=0; i<(int)ranges.size(); i++) {
                Range r = ranges[i];

                if (r.result_from == r.result_to)
                    Results[r.result_to] += r.b_to - r.b_from + 1;

                else if (r.b_from + 1 == r.b_to) {
                    Results[r.result_from]++;
                    Results[r.result_to]++;
                }

                else if (r.b_from + 2 == r.b_to) {
                    Results[r.result_from]++;
                    Results[r.result_to]++;
                    orders.push_back({r.b_from+1, [&Results](int ev){
                        Results[ev]++;
                    }});
                }

                else {
                    int lm = (r.b_from+r.b_to)/2;
                    orders.push_back({lm, [lm, r, &future_ranges](int ev){
                        future_ranges.push_back(Range{.b_from=r.b_from, .b_to=lm, .result_from=r.result_from, .result_to=ev});
                    }});
                    orders.push_back({lm+1, [lm, r, &future_ranges](int ev){
                        future_ranges.push_back(Range{.b_from=lm+1, .b_to=r.b_to, .result_from=ev, .result_to=r.result_to});
                    }});
                }
            }

            //evaluate them all
            evaluate_many(a, orders);
            ranges.clear();
            ranges.swap(future_ranges);
        }
    }
    
    //output
    for (long long x : Results)
        cout << x << "\n";

    return 0;
}