M. Morphological Classification
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Karina, the famous paleontologist, dedicated her life to cataloging dinosaur species from around the world. Karina frequently went on expeditions to the most remote locations on the globe, driven by her desire to learn more about the history of these intriguing animals.

After years of expeditions, she managed to collect fossils from $$$N$$$ different dinosaurs. Based on her research with these fossils, she made $$$M$$$ notes regarding the dinosaurs' diet. However, since the notes were made over a long period of time and science is not fixed, some of them are inconsistent with each other. Each of these notes has a type:

  • Type 1: based on the morphology of the fossils, Karina concluded that dinosaurs $$$x$$$ and $$$y$$$ had the same diet.
  • Type 2: based on the morphology of the fossils, Karina concluded that dinosaurs $$$x$$$ and $$$y$$$ had different diets.

As every good paleontologist knows, each dinosaur can be classified as either carnivorous or herbivorous. Karina wants to know if it is possible to classify the $$$N$$$ dinosaurs while respecting all the notes and, if so, she wants a valid classification. If there is any inconsistency, she wishes to be informed.

Input

The first line contains two integers, $$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$ and $$$M$$$ $$$(0 \le M \le 2 \cdot 10^5)$$$, representing, respectively, the number of dinosaurs and the number of notes.

The next $$$M$$$ lines contain three integers, $$$t_i$$$, $$$x_i$$$ and $$$y_i$$$ $$$(1 \le t_i \le 2, 1 \le x_i, y_i \le N, x_i \neq y_i)$$$, representing, respectively, the type of the $$$i$$$-th note and the dinosaurs present in it.

Output

For each $$$i$$$ $$$(1 \le i \le N)$$$, print $$$1$$$ if dinosaur $$$i$$$ is carnivorous and $$$2$$$ if it is herbivorous. If there is more than one valid solution, print any of them. If it is not possible to follow all the notes, print $$$-1$$$.

Examples
Input
5 5
1 1 2
1 1 5
2 2 4
2 2 3
1 2 5
Output
1 1 2 2 1
Input
5 4
1 1 5
1 2 4
2 2 5
1 1 4
Output
-1