Sasha lives in a big happy family. At the Man's Day all the men of the family gather to celebrate it following their own traditions. There are n men in Sasha's family, so let's number them with integers from 1 to n . Each man has at most one father but may have arbitrary number of sons. Man number A is considered to be the ancestor of the man number B if at least one of the following conditions is satisfied: A = B ; the man number A is the father of the man number B ; there is a man number C , such that the man number A is his ancestor and the man number C is the father of the man number B . Of course, if the man number A is an ancestor of the man number B and A ≠ B , then the man number B is not an ancestor of the man number A . The tradition of the Sasha's family is to give gifts at the Man's Day. Because giving gifts in a normal way is boring, each year the following happens. A list of candidates is prepared, containing some (possibly all) of the n men in some order. Each of the n men decides to give a gift. In order to choose a person to give a gift to, man A looks through the list and picks the first man B in the list, such that B is an ancestor of A and gives him a gift. Note that according to definition it may happen that a person gives a gift to himself. If there is no ancestor of a person in the list, he becomes sad and leaves the celebration without giving a gift to anyone. This year you have decided to help in organizing celebration and asked each of the n men, who do they want to give presents to (this person is chosen only among ancestors). Are you able to make a list of candidates, such that all the wishes will be satisfied if they give gifts according to the process described above? In the first line of the input two integers n and m ( 0 ≤ m < n ≤ 100 000 ) are given — the number of the men in the Sasha's family and the number of family relations in it respectively. The next m lines describe family relations: the ( i + 1) th line consists of