Balanced Mutual Knowledge Partition

There are n people numbered from 1 to n. Some people know others; note that the "knowing" relation is directed (i.e. if person x knows person y, it does not imply that person y knows person x) and is not transitive. Your task is to divide these people into two non‐empty groups such that:

• Every person belongs to one of the two groups.
• Each group has at least one person.
• For every person in a group, he/she knows every other member of the same group. In other words, for any two persons a and b in the same group (with a ≠ b), the knowledge relationship a → b must exist.

Among all possible valid divisions, you are required to choose one in which the absolute difference between the number of members in the two groups is as small as possible.

Note: Since the "knowing" relation is one‐way and nontransmissible, for two people to be in the same group, it is necessary that both a knows b and b knows a (i.e. the relation is mutual) for every distinct pair in that group.

inputFormat

The first line contains two integers n and m (2 ≤ n, and m ≥ 0), where n is the number of people and m is the number of directed "knowing" relations.

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v), indicating that person u knows person v.

outputFormat

If a valid partition exists, output two lines. The first line contains the numbers of the people in the first group (separated by a space), and the second line contains the numbers of the people in the second group (separated by a space). If there are multiple valid answers, output any one of them.

sample

4 6
1 2
2 1
1 3
3 1
2 4
4 2

1 3
2 4