<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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:	---

<|response|>
1. Abridged Problem Statement  
You have N boxes, each containing exactly one coin of distinct integer weights 1 through N. You are given M comparisons of the form “box P is lighter than box Q.” Find a permutation A of {1…N} so that for every comparison P<Q, A[P] < A[Q]. If no such assignment exists, print “No solution.”

2. Key Observations  
- Each comparison “P lighter than Q” is a constraint A[P] < A[Q].  
- Model the boxes as vertices of a directed graph, and each constraint P<Q as a directed edge P→Q.  
- A valid assignment corresponds exactly to a topological order of this graph.  
- If the graph has a cycle, no topological order exists → “No solution.”  
- If acyclic, any topological order gives us a way to number the vertices from smallest weight (1) to largest weight (N).

3. Full Solution Approach  
- Read N, M.  
- Build adjacency list `adj` of size N, and an in-degree array `indegree[]`.  
- For each comparison (P, Q): convert to 0-based, add edge P→Q, and increment `indegree[Q]`.  
- Perform Kahn’s algorithm for topological sort:  
  • Initialize a queue with all vertices u having `indegree[u] = 0`.  
  • While the queue is not empty:  
    – Pop u, append u to `order`.  
    – For each neighbor v in `adj[u]`, decrement `indegree[v]`. If it becomes 0, push v.  
- After the process, if `order.size() < N`, there is a cycle → print “No solution.”  
- Otherwise, `order` is a valid topological order. Let `pos[u]` be the index of u in `order` (0..N-1). Assign `weight[u] = pos[u] + 1`.  
- Finally, output `weight[0] weight[1] … weight[N-1]`.

Time Complexity: O(N + M), which is fine for N≤100, M≤10000.

4. C++ Solution
```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;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it))
    m = int(next(it))

    # Build adjacency list and in-degree array
    adj = [[] for _ in range(n)]
    indegree = [0] * n

    for _ in range(m):
        p = int(next(it)) - 1  # 0-based
        q = int(next(it)) - 1
        adj[p].append(q)
        indegree[q] += 1

    # Initialize queue with all vertices of in-degree 0
    queue = deque([u for u in range(n) if indegree[u] == 0])
    order = []

    # Kahn's topological sort
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    # If cycle exists, we won't have all n vertices in `order`
    if len(order) < n:
        print("No solution")
        return

    # pos[u] = index of u in topological order
    pos = [0] * n
    for idx, u in enumerate(order):
        pos[u] = idx

    # The assigned weight of box u is pos[u]+1
    result = [str(pos[u] + 1) for u in range(n)]
    print(" ".join(result))

if __name__ == "__main__":
    main()
```