混合图的欧拉回路

题目描述

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

输入

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

输出

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

样例

提示

0 \leq n,m_1,m_2 \leq 500

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

来源

模板