Flag Day

Descriptions

小G请你对 n 个点进行染色，可选的颜色有三种：白、红、蓝，并使得给定的 m 个三元组中，每个点的颜色各不相同。

因为你可能不会三分图匹配，于是小G给出了更多的特殊条件：

每个点在三元组中至少出现一次，至多出现两次。
第 i 个（i ≥ 2）三元组中，至多有一个点在第 1 个到第 i-1 个三元组中出现过。

虽然这题现在已经很水了，但是小G为了照顾萌新，你只要输出其中任意一种方案即可。

Input

输入格式如下：
n m
a₁ b₁ c₁
a₂ b₂ c₂
…
a_m b_m c_m

其中， a_i,b_i,c_i 表示一个三元组，其中的元素为第 a_i,b_i,c_i 个点。

Output

输出格式如下：
c₁ c₂ … c_n

其中， c_i 表示第 i 个点的颜色， 1 表示白色， 2 表示红色， 3 表示蓝色。

Examples

Input

Output

1 2 3 3 2 2 1

Input

Output

1 1 1 2 2 2 3 3 3

Input

5 2
4 1 5
3 1 2

Output
2 3 1 1 3 

题目链接

https://vjudge.net/problem/CodeForces-357B

题意

同一行三个数字代表编号，例

5 2
4 1 5
3 1 2

4号 1号 5号

3号 1号 2号

最后输出结果 1号 2号 3号 4号 5号

　　　分别为 2　 3　 1　 1 3

4号 1号 5号

3号 1号 2号

分别对应 1 2 3

　　　　 1 2 3

即每一行都是这三个数字不能重复，不能缺少

AC代码

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#define IOS ios_base::sync_with_stdio(0); cin.tie(0);

#define Mod 1000000007

#define eps 1e-6

#define ll long long

#define INF 0x3f3f3f3f

#define MEM(x,y) memset(x,y,sizeof(x))

#define Maxn 100005

using namespace std;

int n,m;

int color[Maxn];

int a[];

int main()

{

    cin>>n>>m;

    MEM(color,);

    for(int i=; i<m; i++)

    {

        cin>>a[]>>a[]>>a[];

        if(i==)

        {

            color[a[]]=;

            color[a[]]=;

            color[a[]]=;

        }

        else

        {

            if(color[a[]]!=)

            {

                color[a[]]=(color[a[]]+);

                color[a[]]=(color[a[]]+);

                if(color[a[]]>)

                    color[a[]]-=;

                if(color[a[]]>)

                    color[a[]]-=;

            }

            else if(color[a[]]!=)

            {

                color[a[]]=(color[a[]]+);

                color[a[]]=(color[a[]]+);

                if(color[a[]]>)

                    color[a[]]-=;

                if(color[a[]]>)

                    color[a[]]-=;

            }

            else if(color[a[]]!=)

            {

                color[a[]]=(color[a[]]+);

                color[a[]]=(color[a[]]+);

                if(color[a[]]>)

                    color[a[]]-=;

                if(color[a[]]>)

                    color[a[]]-=;

            }

            else

            {

                color[a[]]=;

                color[a[]]=;

                color[a[]]=;

            }

        }

    }

    for(int i=;i<=n;i++)

        cout<<color[i]<<" ";

    return ;

}

巴特西

【CodeForces - 357B】Flag Day（水题）

Flag Day

最新文章

热门文章