Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Complete Tripartite

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou have a simple undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. The graph doesn't contain self-loops, there is at most one edge between a pair of vertices. The given graph can be disconnected.

Let's make a definition.

Let $$$v_1$$$ and $$$v_2$$$ be two some nonempty subsets of vertices that do not intersect. Let $$$f(v_{1}, v_{2})$$$ be true if and only if all the conditions are satisfied:

- There are no edges with both endpoints in vertex set $$$v_1$$$.
- There are no edges with both endpoints in vertex set $$$v_2$$$.
- For every two vertices $$$x$$$ and $$$y$$$ such that $$$x$$$ is in $$$v_1$$$ and $$$y$$$ is in $$$v_2$$$, there is an edge between $$$x$$$ and $$$y$$$.

Create three vertex sets ($$$v_{1}$$$, $$$v_{2}$$$, $$$v_{3}$$$) which satisfy the conditions below;

- All vertex sets should not be empty.
- Each vertex should be assigned to only one vertex set.
- $$$f(v_{1}, v_{2})$$$, $$$f(v_{2}, v_{3})$$$, $$$f(v_{3}, v_{1})$$$ are all true.

Is it possible to create such three vertex sets? If it's possible, print matching vertex set for each vertex.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 10^{5}$$$, $$$0 \le m \le \text{min}(3 \cdot 10^{5}, \frac{n(n-1)}{2})$$$) — the number of vertices and edges in the graph.

The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$a_{i}$$$ and $$$b_{i}$$$ ($$$1 \le a_{i} \lt b_{i} \le n$$$) — it means there is an edge between $$$a_{i}$$$ and $$$b_{i}$$$. The graph doesn't contain self-loops, there is at most one edge between a pair of vertices. The given graph can be disconnected.

Output

If the answer exists, print $$$n$$$ integers. $$$i$$$-th integer means the vertex set number (from $$$1$$$ to $$$3$$$) of $$$i$$$-th vertex. Otherwise, print $$$-1$$$.

If there are multiple answers, print any.

Examples

Input

6 11 1 2 1 3 1 4 1 5 1 6 2 4 2 5 2 6 3 4 3 5 3 6

Output

1 2 2 3 3 3

Input

4 6 1 2 1 3 1 4 2 3 2 4 3 4

Output

-1

Note

In the first example, if $$$v_{1} = \{ 1 \}$$$, $$$v_{2} = \{ 2, 3 \}$$$, and $$$v_{3} = \{ 4, 5, 6 \}$$$ then vertex sets will satisfy all conditions. But you can assign vertices to vertex sets in a different way; Other answers like "2 3 3 1 1 1" will be accepted as well.

In the second example, it's impossible to make such vertex sets.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/27/2023 14:07:10 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|