P7370 [COCI 2018/2019 #4] Wand

After seeing Nikola's problem, Kile got inspired and created his own version.

$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.

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 $N$ characters. If the wand may finally belong to wizard $k$, output `1` at the $k$-th character; otherwise output `0`.

#### 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](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #4](https://hsin.hr/coci/archive/2018_2019/contest4_tasks.pdf) _T2 Wand_.** Translated by ChatGPT 5