<|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++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

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

    int N, M;
    cin >> N >> M;

    // Build graph: adj[u] lists all v such that u->v (u lighter than v)
    vector<vector<int>> adj(N);
    vector<int> indegree(N, 0);

    for (int i = 0; i < M; i++) {
        int P, Q;
        cin >> P >> Q;
        // convert to 0-based
        --P; 
        --Q;
        adj[P].push_back(Q);
        indegree[Q]++;
    }

    // Kahn's algorithm: collect all vertices with in-degree zero
    queue<int> q;
    for (int u = 0; u < N; u++) {
        if (indegree[u] == 0) {
            q.push(u);
        }
    }

    vector<int> order;  // will store the topological order
    order.reserve(N);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        // decrease in-degree of all neighbors
        for (int v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // If we couldn't order all N vertices, there's a cycle
    if ((int)order.size() < N) {
        cout << "No solution\n";
        return 0;
    }

    // pos[u] = position of u in topological order (0..N-1)
    vector<int> pos(N);
    for (int i = 0; i < N; i++) {
        pos[order[i]] = i;
    }

    // weight[u] = pos[u] + 1
    // Output the weight for each box in original order (1-based boxes)
    for (int u = 0; u < N; u++) {
        cout << (pos[u] + 1) << (u+1 < N ? ' ' : '\n');
    }

    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()
```