# 「题解」Complete Tripartite

“完全”的三分图的存在性判定问题……

# 一 题目

Source

## Descriptions

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:
There are no edges with both endpoints in vertex set v1.
There are no edges with both endpoints in vertex set v2.
For every two vertices x and y such that x is in v1 and y is in v2, there is an edge between x and y.

Create three vertex sets (v1, v2, v3) which satisfy the conditions below;
All vertex sets should not be empty.
Each vertex should be assigned to only one vertex set.
f(v1,v2), f(v2,v3), f(v3,v1) 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≤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.

## 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.

# 二 题解

ce-amtic

2019-10-04

2020-12-27

### 评论

###### Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×