There is a set of N men and N women. Each of them is numbered from 1 t...

Code in java

There is a set of N men and N women. Each of them is numbered from 1 to N. They have been married off in pairs. However complete information about the pairs is not available. Some specific clues about the pairs are available. These clues are either of the form:

ith woman, indicated as Wi, is paired with the man Mj

or

woman Wp is not paired with the man Mq

If Wi is paired with Mj then they cannot pair with anyone else.

Given the number N and the clues, you have to write a program, which deduces the complete pairing.

Consider the case where N = 3 and the clues are:

1. W1 is paired with M2
2. W3 is not paired with M1

Consider the case of woman W3. She cannot be paired with M1 (given as clue 2). She cannot be paired with M2 either as deducible from clue 1. This leaves only M3 to pair with her. Further, now W2 can only pair with M1 since both M2 and M3 are already paired off.

Input Format

• The first line contains an integer N denoting the number of pairs
• The second line contains an integer C denoting the number of clues which follow
• Each of the next C lines contains a clue of the form

= 1 2

which means woman W1 is paired with man M2

OR

# 3 1

which means woman W3 is not paired with man M1

Constraints

1<= N <=100

0<= C <=100

Output Format

You have to print the sequence of integers, each separated by a space, on a single line. The integer at ith location in the sequence denotes the man paired with Wi.

Sample TestCase 1

Input

3

2

= 1 2

# 3 1

Output

2 1 3