Wand

Interview

Time limit1sMemory limit512 MB

Summary

Given M duels with fixed winners, in any order, decide which wizards can hold the wand (initially with wizard 1) after all duels.

Level: Medium7 of 10
Topics: Graph, DFS, Greedy, Implementation
Solved: No attempts yet

Problem

Kile really liked Nikola's task about wizards and a wand (see the task Elder), so he decided to make his own version. He imagined that instead of 26 wizards there are N of them, labeled with integers from 1 to N, and that M duels must be held among the wizards. A duel between the same pair of wizards may be held multiple times.

As in Nikola's task, if the wand belonged to the loser before the duel, then after the duel the wand goes to the winner.

If we know in advance, for each duel, which pair of wizards will fight and which of them will win, and if we can choose the order in which the duels are held, then Kile wants to know in whose hands the wand can end up after all M duels.

In the beginning, the wand belongs to the wizard with the label 1.

Input

The first line contains two integers N and M. (1 ≤ N, M ≤ 100 000)

In the following M lines there are two numbers Xi and Yi. (1 ≤ Xi, Yi ≤ N, Xi ≠ Yi) Wizard Xi will win the fight against wizard Yi.

Output

Print N characters in the first and only line. The character at the kth position should be '1' if the wizard labeled k can hold the wand after all M duels, and '0' otherwise.

Examples3

Example 1
Input
```
3 2
2 3
3 1
```
Expected output
```
011
```
Example 2
Input
```
2 2
2 1
1 2
```
Expected output
```
11
```
Example 3
Input
```
5 5
3 1
2 1
4 3
4 5
2 5
```
Expected output
```
01110
```