小红的生成树构造
题号：NC316764
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

\hspace{15pt}给定一个 n 个点 m 条边的无向连通图，每个点被标记为字符 \texttt{A}、\texttt{B}、\texttt{C}、\texttt{D} 之一。你需要找到该图的一棵生成树，使得在这棵生成树中：
\hspace{23pt}\bullet 对于每个标记为 \texttt{A} 的点，存在一条从该点出发、不经过任何标记为 \texttt{C} 或 \texttt{D} 的点的路径，其连接到某个标记为 \texttt{B} 的点；
\hspace{23pt}\bullet 对于每个标记为 \texttt{B} 的点，存在一条从该点出发、不经过任何标记为 \texttt{C} 或 \texttt{D} 的点的路径，其连接到某个标记为 \texttt{A} 的点；
\hspace{23pt}\bullet 对于每个标记为 \texttt{C} 的点，存在一条从该点出发、不经过任何标记为 \texttt{A} 或 \texttt{B} 的点的路径，其连接到某个标记为 \texttt{D} 的点；
\hspace{23pt}\bullet 对于每个标记为 \texttt{D} 的点，存在一条从该点出发、不经过任何标记为 \texttt{A} 或 \texttt{B} 的点的路径，其连接到某个标记为 \texttt{C} 的点。

\hspace{15pt}请判断是否存在这样的生成树，如果存在请输出任意一种方案。

输入描述:

\hspace{15pt}第一行两个整数 n, m\left(2 \leq n \leq 2 \times 10^5, 1 \leq m \leq min\left(\tfrac{n\times \left(n-1 \right)}{2},2 \times 10^5\right)\right)。
\hspace{15pt}第二行一个长度为 n 的字符串 s，只包含字符 \texttt{A}, \texttt{B}, \texttt{C}, \texttt{D}，其中 s_i 表示 i 号点的标记。
\hspace{15pt}接下来 m 行，每行两个整数 u, v (1 \leq u, v \leq n, u \neq v)，表示图中一条无向边。保证图连通，且无重边。

输出描述:

\hspace{15pt}如果不存在满足条件的生成树，请输出 \texttt{No}；否则在第一行输出 \texttt{Yes}，之后输出 n-1 行，每行两个整数 u, v，表示生成树中的一条边。输出顺序任意。

\hspace{15pt}如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
示例1

输入

复制 
4 4
ABCD
1 2
2 3
3 4
4 1

输出

复制 
Yes
1 2
1 4
4 3
示例2

输入

复制 
4 3
ACBD
1 2
2 3
3 4

输出

复制 
No
示例3

输入

复制 
10 23
AACDBDDBDB
2 1
3 2
4 1
4 2
4 3
5 1
5 2
5 3
6 1
6 2
6 3
7 1
7 2
7 3
8 1
8 2
8 3
9 1
9 2
9 3
10 1
10 3
10 4

输出

复制 
Yes
1 5
5 2
2 8
1 10
1 4
4 3
3 6
3 7
3 9