COCI '18 Contest 4 #2 Wand

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 N of them labeled with integers from 1 to N and that M 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 M duels.

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


The first line contains two integers N and M (1 \le N, M \le 100\,000). In the following M lines there are two numbers X_i and Y_i (1 \le X_i, Y_i \le N, X_i \ne Y_i). The wizard X_i will win the fight against wizard Y_i.


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


In the sample tests totally worth 20% of points it will be true that 1 \le N, M \le 10.

Sample Input 1

3 2
2 3
3 1

Sample Output 1


Explanation for Sample Input 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


Sample Input 3

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

Sample Output 3



There are no comments at the moment.