Wand

Στον Kile άρεσε πολύ η εργασία του Nikola με τους μάγους και το ραβδί (βλ. πρόβλημα Elder) και έτσι αποφάσισε να φτιάξει τη δική του εκδοχή. Φαντάστηκε ότι, αντί για τους 26 μάγους, υπάρχουν ~N~ μάγοι που χαρακτηρίζονται με ακέραιους αριθμούς από το 1 έως το ~N~ και ότι ~M~ μονομαχίες πρέπει να διεξάγονται μεταξύ των μάγων. Είναι πιθανό μια μονομαχία μεταξύ του ίδιου ζευγαριού μάγων να διεξαχθεί πολλές φορές.

Όπως στο πρόβλημα του Nikola, αν πριν από τον αγώνα το ραβδί ανήκε στον ηττημένο, μετά τον αγώνα το ραβδί θα ανατεθεί στον νικητή.

Αν γνωρίζουμε εκ των προτέρων για κάθε μονομαχία ποιο ζευγάρι μάγων θα πολεμήσει, καθώς και ποιος από αυτούς θα κερδίσει και αν μπορούμε να επιλέξουμε τη σειρά με την οποία θα διεξαχθούν οι μονομαχίες, τότε ο Kile θέλει να μάθει σε ποιανού χέρια μπορεί το ραβδί να καταλήξει μετά από όλες τις Μ μονομαχίες.

Στην αρχή, το ραβδί ανήκει στον μάγο με την που χαρακτηρίζεται από τον αριθμό 1.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς ~N~ και ~M\;(1 \leq N, M \leq 100\,000)~.

Στις ακόλουθες ~M~ γραμμές υπάρχουν δύο αριθμοί ~X_i~ και ~Y_i~ ~(1 \leq X_i, Y_i \leq N, X_i \neq Y_i)~.

Ο μάγος ~X_i~ θα κερδίσει τη μάχη ενάντια στον μάγο ~Y_i~.

Έξοδος

Εκτυπώστε ~N~ χαρακτήρες στην πρώτη και μοναδική γραμμή. Ο χαρακτήρας στην ~k_i~ θέση θα πρέπει να είναι '1', εάν ο μάγος που χαρακτηρίζεται από τον αριθμό k μπορεί να κερδίσει το ραβδί μετά από όλες τις ~M~ μονομαχίες, αλλιώς να είναι '0'.

Βαθμολογία

Στα υποπροβλήματα συνολικής αξίας 20% των πόντων θα ισχύει ότι ~1 \le N, M \le 10~.

Παραδείγματα

input

3 2
2 3
3 1

output

011

Επεξήγηση του 1ου παραδείγματος:

Εάν οι μάγοι 1 και 3 παλέψουν πρώτοι και οι μάγοι 2 και 3 παλέψουν δεύτεροι, το ραβδί θα ανήκει στον μάγο 2.
Εάν οι μάγοι 2 και 3 παλέψουν πρώτοι και οι μάγοι 1 και 3 παλέψουν δεύτεροι, το ραβδί θα ανήκει στον μάγο 3.

input

2 2
2 1
1 2

output

11

input

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

output

01110