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 iburles 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 cupscales.
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 Pth box lighter than the Qth.
Output
Write "No solution" if it is impossible to find such assignment. In opposite case, write N numbers, where the Kth number means the type of coin in Kth box, for example A, means that there is Aburles coin in the Kth 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:  

Server time: 20180623 14:29:09  Online Contester Team © 2002  2016. All rights reserved. 

