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.
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.
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.
3 2 2 1 1 3
2 1 3
Michael R. Mirzayanov
Codeforces (c) Copyright 2010-2021 Mike Mirzayanov