No tags yet

No tag edit access

The problem statement has recently been changed. View the changes.

×
time limit per test: 0.25 sec.

memory limit per test: 4096 KB

memory limit per test: 4096 KB

input: standard

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

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.

Input

3 2

2 1

1 3

2 1

1 3

Output

2 1 3

Author: | Michael R. Mirzayanov |

Resource: | --- |

Date: | --- |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/25/2021 13:19:30 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|