Ghost are living in big castle with K rooms.

As they have around few hundred years and very tired, they decided to buy teleports. Every teleport can work only in one way (to prevent collision). Ghosts have decided which teleports they want to build and in which order they should be built.

King of ghosts, Bob, asked you to check list of teleports and decide which of them do not build. He don't want ghosts having fun in infinite ride with teleports.

Input

In first line - number K <= 1000, number of rooms in castle.

In next line - number T <= 300000 number of teleports.

In next T lines a, b <= K

Rooms are numbered 1 to K

Output

Print teleports which should not be built. End test case with 0 0.

Example

Input:
4
5
2 4
4 3
3 2
1 2
3 1

Output:
3 2
3 1
0 0