atcoder#AGC035B. [AGC035B] Even Degrees

[AGC035B] Even Degrees

题目描述

N N 頂点 M M 辺の単純連結無向グラフが与えられます。頂点には 1 1 から N N までの番号がついており、i i 本目の辺は頂点 Ai A_i と頂点 Bi B_i を結んでいます。 高橋君は、与えられたグラフのすべての辺にどちらかの向きをつけて有向グラフを作ります。 どの頂点から出る辺の本数も偶数になるような有向グラフを作ることが可能かどうか判定し、可能ならそのような例をひとつ構成してください。

输入格式

入力は以下の形式で標準入力から与えられる。

N N M M A1 A_1 B1 B_1 : : AM A_M BM B_M

输出格式

条件を満たす向き付けが不可能な場合、1 -1 を出力せよ。 そうでない場合、以下の形式でグラフのすべての辺の向きを重複なく出力せよ。

C1 C_1 D1 D_1 : : CM C_M DM D_M

ただし、組 (Ci,Di) (C_i,D_i) Ci C_i から頂点 Di D_i に向かって向き付けられた辺が存在することを表す。 辺は任意の順で出力して構わない。

题目大意

给一张无向简单连通图,给每一条边定向,使得每一个点出度为偶数,输出任意一种方案。

如果无法做到,输出-1

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

提示

ノート

無向グラフが単純であるとは、自己ループと多重辺を含まないことを指します。

制約

  • 2  N  105 2\ \leq\ N\ \leq\ 10^5
  • N1  M  105 N-1\ \leq\ M\ \leq\ 10^5
  • 1  Ai,Bi  N (1 i M) 1\ \leq\ A_i,B_i\ \leq\ N\ (1\leq\ i\leq\ M)
  • 与えられるグラフは単純かつ連結

Sample Explanation 1

このように向き付けることで、頂点 1,3 1,3 からは 2 2 本、頂点 2,4 2,4 からは 0 0 本の辺が出るようになります。