Before the start of the cockroach race, all fans were asked to make two bets on the results of the race. Each bet has the form "Cockroach #A will come before cockroach #B".
The organizers of the race decided to find out if the cockroaches could come in such an order that each fan had exactly one bet out of two played (that is, exactly one of the two statements of each fan turned out to be true). It is believed that no two cockroaches can reach the finish line at the same time.
Input
The first line of the input contains two positive integers separated by a space: the number K, not exceeding 10, is the number of cockroaches, and the number N, not exceeding 100, is the number of fans. All cockroaches are numbered from 1 to K. Each of the next N lines contains 4 natural numbers A, B, C, D, not exceeding K, separated by spaces. They match the fan's bets "Cockroach #A will come before cockroach #B" and "Cockroach #C will come before cockroach #D".
Imprint
If you finish the race so that each of the fans plays exactly one of the two bets, then you should print the numbers of cockroaches in the order in which they appear in the final table of results (first the number of the cockroach that came first, then the number of the cockroach that came second etc.) into one line separated by a space. If there are several such options, print any of them.
If the desired result cannot be achieved, print a single number 0.
Examples
| # |
Input |
Output |
| 1 |
3 2
2 1 2 3
1 2 3 2
| 3 2 1 |
| 2 |
3 4
1 2 1 3
1 2 3 1
1 2 2 3
1 2 3 2
| 0 |
Note: Solutions to the problem in the programming language
Python do not pass the time limit.