{"trustable":true,"prependHtml":"\u003cstyle\u003e.table {width: 100%;} .table-bordered {border: 1px solid #222; border-collapse: collapse; border-spacing: 0;} .table-bordered th { border: 1px solid #222; }.table-bordered td { border: 1px solid #222; padding: 0 5px; }\u003c/style\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e有一天一位灵魂画师画了一张图，现在要你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。\u003c/p\u003e\n\u003cp\u003e一共两个子任务：\u003c/p\u003e\n\u003col\u003e\n \u003cli\u003e这张图是无向图。（50分）\u003c/li\u003e\n \u003cli\u003e这张图是有向图。（50分）\u003c/li\u003e\n\u003c/ol\u003e\n\u003ch3\u003e输入格式\u003c/h3\u003e\n\u003cp\u003e第一行一个整数 $t$，表示子任务编号。$t \\in \\{1, 2\\}$，如果 $t \u003d 1$ 则表示处理无向图的情况，如果 $t \u003d 2$ 则表示处理有向图的情况。\u003c/p\u003e\n\u003cp\u003e第二行两个整数 $n, m$，表示图的结点数和边数。\u003c/p\u003e\n\u003cp\u003e接下来 $m$ 行中，第 $i$ 行两个整数 $v_i, u_i$，表示第 $i$ 条边（从 $1$ 开始编号）。保证 $1 \\leq v_i, u_i \\leq n$。\u003c/p\u003e\n\u003col\u003e\n \u003cli\u003e如果 $t \u003d 1$ 则表示 $v_i$ 到 $u_i$ 有一条无向边。\u003c/li\u003e\n \u003cli\u003e如果 $t \u003d 2$ 则表示 $v_i$ 到 $u_i$ 有一条有向边。\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp\u003e图中可能有重边也可能有自环。\u003c/p\u003e\n\u003ch3\u003e输出格式\u003c/h3\u003e\n\u003cp\u003e如果不可以一笔画，输出一行 “\u003csamp\u003eNO\u003c/samp\u003e”。\u003c/p\u003e\n\u003cp\u003e否则，输出一行 “\u003csamp\u003eYES\u003c/samp\u003e”，接下来一行输出一组方案。\u003c/p\u003e\n\u003col\u003e\n \u003cli\u003e如果 $t \u003d 1$，输出 $m$ 个整数 $p_1, p_2, \\dots, p_m$。令 $e \u003d \\lvert p_i \\rvert$，那么 $e$ 表示经过的第 $i$ 条边的编号。如果 $p_i$ 为正数表示从 $v_e$ 走到 $u_e$，否则表示从 $u_e$ 走到 $v_e$。\u003c/li\u003e\n \u003cli\u003e如果 $t \u003d 2$，输出 $m$ 个整数 $p_1, p_2, \\dots, p_m$。其中 $p_i$ 表示经过的第 $i$ 条边的编号。\u003c/li\u003e\n\u003c/ol\u003e\n\u003ch3\u003e样例一\u003c/h3\u003e\n\u003ch4\u003einput\u003c/h4\u003e\n\u003cpre\u003e1\n3 3\n1 2\n2 3\n1 3\n\n\u003c/pre\u003e\n\u003ch4\u003eoutput\u003c/h4\u003e\n\u003cpre\u003eYES\n1 2 -3\n\n\u003c/pre\u003e\n\u003ch3\u003e样例二\u003c/h3\u003e\n\u003ch4\u003einput\u003c/h4\u003e\n\u003cpre\u003e2\n5 6\n2 3\n2 5\n3 4\n1 2\n4 2\n5 1\n\n\u003c/pre\u003e\n\u003ch4\u003eoutput\u003c/h4\u003e\n\u003cpre\u003eYES\n4 1 3 5 2 6\n\n\u003c/pre\u003e\n\u003ch3\u003e限制与约定\u003c/h3\u003e\n\u003cp\u003e$1 \\leq n \\leq 10^5, 0 \\leq m \\leq 2 \\times 10^5$\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e时间限制\u003c/strong\u003e：$1\\texttt{s}$\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e空间限制\u003c/strong\u003e：$256\\texttt{MB}$\u003c/p\u003e\n\u003ch3\u003e下载\u003c/h3\u003e\n\u003cp\u003e\u003ca href\u003d\"https://uoj.ac/download.php?type\u003dproblem\u0026amp;id\u003d117\"\u003e样例数据下载\u003c/a\u003e\u003c/p\u003e"}}]}