#P9741. 滈葕

    ID: 6365 传统题 1000ms 512MiB 尝试: 3 已通过: 1 难度: 7 上传者: 标签>难度分类提高+/省选-图论2-SAT蕴含图Tarjan 强连通分量算法SCC 判定可满足性CF2200

滈葕

题目描述

给定一个 0/1 权有向图 , 给每个点赋予 ABCD 中的一个字母使得每条有向边 (u,v,w)\left( u , v , w \right) 都满足

$w=1 \iff( a_{u} , a_{v} ) \in\{( A , D ) , ( A , B ) , ( B , D ) , ( B , A ) , ( C , D ) , ( C , A ) , ( C , B ) \}$

输入格式

第一行两个非负整数n,mn , m,表示点数和边数。

接下来mm行每行三个整数x,y,zx , y , z,表示一条边。

输出格式

如果没有解,输出 NO;

否则在第一行输出 YES,并在第二行输出长度为nn 的由 ABCD 构成的字符串,第ii 个字符表示第ii 个点的权值。如果有多解,你只需要输出任意一个。

样例输入1

4 16
1 1 0
1 2 0
1 3 0
1 4 0
2 1 1
2 2 0
2 3 1
2 4 0
3 1 1
3 2 1
3 3 0
3 4 0
4 1 1
4 2 1
4 3 1
4 4 0

样例输出1

YES
DABC

样例输入2

5 8
3 1 1
5 2 1
4 3 0
1 4 1
2 4 0
3 4 1
4 5 1
2 5 0

样例输出2

YES
BDCAB

样例输入3

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

样例输出3

NO

数据范围

对于所有数据,$n \leq10^5 , m \leq5 \times10^5 , 1 \leq x , y \leq n , z \in\{0 , 1 \}$,(x,y)( x , y ) 对可能相同。

子任务 1(20 分):n≤18,m≤50n \leq18 , m \leq50; 子任务 2(20 分):z=1z=1; 子任务 3(30 分):n,m≤5000n , m \leq5000; 子任务 4(30 分):无额外限制。