## COCI '18 Contest 4 #2 Wand

View as PDF

Points: 7 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem type

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

As in Nikola's task, if before the match the wand belonged to the loser, after the match the wand will be assigned to the winner.

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

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

#### Input

The first line contains two integers and .

In the following lines there are two numbers and . The wizard will win the fight against wizard .

#### Output

Print characters in the first and only line. The character at the position should be 1 if the wizard labeled with can rule over the wand after all duels and 0 otherwise.

#### Scoring

In the sample tests totally worth 20% of points, it will be true that .

#### Sample Input 1

3 2
2 3
3 1

#### Sample Output 1

011

#### Explanation for Sample Output 1

If wizards 1 and 3 fight first, and wizards 2 and 3 fight second, the wand will belong to wizard 2.

If wizards 2 and 3 fight first, and wizards 1 and 3 fight second, the wand will belong to wizard 3.

#### Sample Input 2

2 2
2 1
1 2

#### Sample Output 2

11

#### Sample Input 3

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

#### Sample Output 3

01110