Codeforces Round 589 (Div. 2) |
---|
Finished |
You 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 v1 and v2 be two some nonempty subsets of vertices that do not intersect. Let f(v1,v2) be true if and only if all the conditions are satisfied:
Create three vertex sets (v1, v2, v3) which satisfy the conditions below;
Is it possible to create such three vertex sets? If it's possible, print matching vertex set for each vertex.
The first line contains two integers n and m (3≤n≤105, 0≤m≤min(3⋅105,n(n−1)2)) — the number of vertices and edges in the graph.
The i-th of the next m lines contains two integers ai and bi (1≤ai<bi≤n) — it means there is an edge between ai and bi. The graph doesn't contain self-loops, there is at most one edge between a pair of vertices. The given graph can be disconnected.
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.
6 11 1 2 1 3 1 4 1 5 1 6 2 4 2 5 2 6 3 4 3 5 3 6
1 2 2 3 3 3
4 6 1 2 1 3 1 4 2 3 2 4 3 4
-1
In the first example, if v1={1}, v2={2,3}, and v3={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.
Name |
---|