p230.ans1
======================
2 1 3

=================
p230.cpp
======================
#include <bits/stdc++.h>

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;
};

int n, m;
vector<vector<int>> adj;

void read() {
    cin >> n >> m;
    adj.assign(n, vector<int>());
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
    }
}

vector<int> top_sort() {
    vector<int> order;
    vector<int> deg(n);
    for(int u = 0; u < n; u++) {
        for(int v: adj[u]) {
            deg[v]++;
        }
    }

    queue<int> q;
    for(int u = 0; u < n; u++) {
        if(deg[u] == 0) {
            q.push(u);
        }
    }

    while(!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        for(int v: adj[u]) {
            deg[v]--;
            if(deg[v] == 0) {
                q.push(v);
            }
        }
    }

    return order;
}

void solve() {
    // Each weighing "box P lighter than box Q" is a directed edge P -> Q in a
    // DAG whose vertices are the boxes. A valid assignment of coin values is a
    // linear extension of this partial order: run Kahn's topological sort, and
    // the position of a box in the resulting order (1-indexed) is the coin value
    // placed in it. If the topological order does not cover all boxes there is a
    // cycle and no assignment exists.

    vector<int> order = top_sort();
    if((int)order.size() != n) {
        cout << "No solution\n";
        return;
    }

    vector<int> pos(n);
    for(int i = 0; i < n; i++) {
        pos[order[i]] = i;
    }

    for(int i = 0; i < n; i++) {
        cout << pos[i] + 1 << ' ';
    }

    cout << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p230.in1
======================
3 2
2 1
1 3

=================
statement.txt
======================
230. Weighings
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard



There are N types of coins in Berland country. Values of the types are 1 burl, 2 burls, ..., N burls. The weight of i-burles coin is i grams. N coins (one of each type) are placed in N matchlog boxes, one coin in each box. A number of weighings was done on the cup-scales.
You are to write a program which should find such assignment of coins to boxes, that would not conflict with the weighings. It is possible that scales are broken and such assignment doesn't exist.

Input
The first line of the input consists of two integers N and M (1 <= N <= 100, 1 <= M <= 10000), where N is the amount of types, and M is the amount of weighings. Next M lines consist of pairs P, Q (1 <= P, Q <= N), each line means that the P-th box lighter than the Q-th.

Output
Write "No solution" if it is impossible to find such assignment. In opposite case, write N numbers, where the K-th number means the type of coin in K-th box, for example A, means that there is A-burles coin in the K-th box. Output sequence must be a permutation of numbers from 1 to N.

Sample test(s)

Input
3 2
2 1
1 3

Output
2 1 3
Author:	Michael R. Mirzayanov
Resource:	---
Date:	---







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