Description

In the distant East, there is a mysterious people who call themselves the Y tribe. They have lived on the water for generations and worship the Dragon King as their deity. On major festivals, the Y tribe holds grand ritual ceremonies on the water. We can regard the water system of their habitat as a network composed of junctions and rivers. Each river connects two junctions, and water flows along each river in a fixed direction. Clearly, there is no circular flow in the water system (the figure below shows an example of a circular flow).

Because of their large population, the rituals will be held simultaneously at multiple junctions. Out of respect for the Dragon King, the selection of ritual locations must be very cautious. Specifically, the Y tribespeople believe that if water can flow from one ritual point to another ritual point, the ritual loses its sacred meaning. The chief wants to select as many ritual locations as possible while maintaining sacredness.

Input Format

The first line contains two integers $N$ and $M$ separated by a space, representing the numbers of junctions and rivers, respectively. Junctions are numbered from $1$ to $N$.

Each of the next $M$ lines contains two integers $u$ and $v$ separated by a space, describing a river connecting junction $u$ and junction $v$, with water flowing from $u$ to $v$.

Output Format

The first line contains an integer $K$, the maximum number of junctions that can be selected as ritual points.

The next line outputs one feasible selection scheme. For each junction in order, output an integer: output 1 if a ritual point is set at this junction, otherwise output 0. The number of 1s must be maximum, and there should be no spaces between them.

The next line outputs, under the premise of selecting the maximum number of ritual points, whether each junction can be chosen as a ritual point in some optimal scheme. For each junction in order, output an integer: output 1 if this junction can be chosen as a ritual point in at least one optimal scheme, otherwise output 0.

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

4 4
1 2
3 4
3 2
4 2

2
1010
1011

Hint

$N \le 100$, $M \le 1000$.

In the sample water system, there is no way to select three or more ritual points. There are two solutions that contain two ritual points:

• Choose junction $1$ and junction $3$ (as in the second line of the sample output).
• Choose junction $1$ and junction $4$.

Water can flow from any junction to junction $2$. If a ritual point is set at junction $2$, then no other junction can host a ritual point. However, in an optimal selection scheme we can set two ritual points, so junction $2$ cannot be chosen as a ritual point. For every other junction, there exists at least one optimal scheme that chooses it, so the output is 1011.

Thanks to @ACdreamer for providing the SPJ.

Translated by ChatGPT 5