9278 - 混合图的欧拉回路

通过次数

7

提交次数

42

时间限制 : 5 秒
内存限制 : 1024 MB

如果图G中的一个路径包括每个边恰好一次,则该路径称为欧拉路径(Euler path)。 如果一个回路是欧拉路径,则称为欧拉回路(Euler circuit)。 当存在一个起始节点和最终节点相同的欧拉回路则为欧拉图。 给定一个有一些有向边和一些无向边的图。判断是否为欧拉图,并输出其中任意一个欧拉路径。

输入

第一行三个数n,m_1,m_2n表示图的节点数,并且节点从1~n编号,m_1表示图的有向边的数量,m_2表示图的无向边的数量
然后从第2行到 m_1 +1行,共m_1行,每行两个数f_i,t_i,表示该有向边从f_it_i
然后是从第m_1 +2行到m_1 + m_2 +1行,共m_2行,每行两个数a_i,b_i,表示f_it_i连接,表示一条无向边。

输出

第一行,输出"YES"或者"NO",表示是否为欧拉图。 第二行,输出m_1 + m_2 +1个数,第i个数和第i+1个数表示欧拉路径上的第i条边。如果第一行输出“NO”则不用输出。

样例

输入

5 3 3
1 2
2 4
3 5
1 4
1 3
1 5

输出

YES
1 2 4 1 3 5 1

输入

5 2 3
1 2
1 3
2 5
3 4
4 5

输出

NO

提示

0 \leq n,m_1,m_2 \leq 200

对于样例1,1->2->4->1->3->5->1是一个欧拉回路,起点和终点都为1,并且每个边都正好都经过且只经过一次。

来源

模板