Description

$N$ wizards, labeled $1,2,\cdots,N$, will take part in $M$ duels.

There is a wand. If the wand currently belongs to wizard $A$, and wizard $A$ is defeated by wizard $B$, then the wand will belong to wizard $B$. Initially, the wand belongs to wizard $1$.

Kile wants to know, if we are only allowed to change the order of the duels, who the wand may end up belonging to.

Input Format

The first line contains positive integers $N, M$.

Each of the next $M$ lines contains positive integers $X_i, Y_i$, meaning wizard $X_i$ will defeat wizard $Y_i$.

Output Format

Output $N$ characters. If the wand may finally belong to wizard $k$, output 1 at the $k$-th character; otherwise output 0.

3 2
2 3
3 1

011

2 2
2 1
1 2

11

5 5
3 1
2 1
4 3
4 5
2 5

01110

Hint

Explanation for Sample 1

If wizards $1$ and $3$ duel first, and then it is wizards $2$ and $3$, the wand will finally belong to wizard $2$.

If wizards $2$ and $3$ duel first, and then it is wizards $1$ and $3$, the wand will finally belong to wizard $3$.

Constraints

For $20\%$ of the testdata, $1 \le N, M \le 10$.

For $100\%$ of the testdata, $1 \le N, M \le 10^5$, $1 \le X_i, Y_i \le N$, and $X_i \neq Y_i$.

Notes

The scoring of this problem follows the original COCI settings, with a full score of $70$.

Translated from COCI2018-2019 CONTEST #4 T2 Wand.

Translated by ChatGPT 5