In the distant East, there is a mysterious tribe that calls itself the Y tribe. They have lived on the water for generations and worship the Dragon King as their god. During every major celebration, the Y tribe holds a grand sacrificial ceremony on the water.

We can view the water system where the Y tribe lives as a network consisting of junctions and river channels. Each river channel connects two junctions, and water flows within the channels in a fixed direction. Clearly, there are no cycles in the water system (the figure below describes an example of a cycle).

Junction, River Channel, Cycle

Due to the large number of people, the Y tribe's sacrificial activities are held at multiple junctions simultaneously. Out of respect for the Dragon King, the selection of these sacrificial sites must be very careful. To be precise, the Y tribe believes that if water can flow from one sacrificial site to another, the sacrifice will lose its sacred meaning.

The tribal leader hopes to select as many sacrificial sites as possible while maintaining the sanctity of the sacrifice.

Input

The first line contains two space-separated integers $N$ and $M$, representing the number of junctions and river channels, respectively. The junctions are numbered from $1$ to $N$.

The next $M$ lines each contain two space-separated integers $u$ and $v$, describing a river channel connecting junction $u$ to junction $v$, with the water flowing from $u$ to $v$.

Output

The first line contains an integer $K$, representing the maximum number of sacrificial sites that can be selected.

The second line outputs a feasible selection scheme. For each junction, output an integer: if a sacrificial site is set at that junction, output $1$; otherwise, output $0$. Ensure that the number of $1$s you output is maximized, and there are no spaces between them.

The third line outputs, under the premise of selecting the maximum number of sacrificial sites, whether each junction can be set as a sacrificial site. For each junction, output an integer: if a sacrificial site can be set at that junction, output $1$; otherwise, output $0$.

Note: Extra spaces and line breaks may cause your answer to be judged as incorrect.

Examples

Input 1

4 4
1 2
3 4
3 2
4 2

Output 1

2
1010
1011

Note

In the water system given in the example, there is no way to select three or more sacrificial sites. There are two schemes for the test point containing two sacrificial sites: selecting junction $1$ and junction $3$ (as in the second line of the example output), or selecting junction $1$ and junction $4$.

Water can flow from any junction to junction $2$. If a sacrificial site is established at junction $2$, no other junction can have a sacrificial site. However, in one of the optimal sacrificial site selection schemes, we can establish two sacrificial sites, so junction $2$ cannot be a sacrificial site. For other junctions, there exists at least one optimal scheme that selects that junction as a sacrificial site, so the output is $1011$.

Subtasks

For each test point: If you only output the correct number of selected sacrificial sites, you will receive $30\%$ of the score for that test point. If you only output the correct number of selected sacrificial sites and one feasible scheme, you will receive $60\%$ of the score for that test point. * If your output is completely correct, you will receive $100\%$ of the score for that test point.

Constraints

$N \le 100$ $M \le 1\,000$