#P9741. 滈葕
滈葕
题目描述
给定一个 0/1 权有向图 , 给每个点赋予 ABCD 中的一个字母使得每条有向边 都满足
$w=1 \iff( a_{u} , a_{v} ) \in\{( A , D ) , ( A , B ) , ( B , D ) , ( B , A ) , ( C , D ) , ( C , A ) , ( C , B ) \}$
输入格式
第一行两个非负整数,表示点数和边数。
接下来行每行三个整数,表示一条边。
输出格式
如果没有解,输出 NO;
否则在第一行输出 YES,并在第二行输出长度为 的由 ABCD 构成的字符串,第 个字符表示第 个点的权值。如果有多解,你只需要输出任意一个。
样例输入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 \}$, 对可能相同。
子任务 1(20 分):; 子任务 2(20 分):; 子任务 3(30 分):; 子任务 4(30 分):无额外限制。