codeforces Round #259(div2) E問題解決レポート_html/css_WEB-ITnose

E.リトルポニーと夏の太陽のお祝い

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

トワイライト・スパークルは、邪悪なナイトメア・ムーンが、千年間月に投獄されていた後、来たるサマー・サン・セレブレーション中に戻ってくることを知りました。彼女は指導者であるプリンセス セレスティアに警告しようとしましたが、プリンセスは彼女を無視し、お祝いの準備を確認するために彼女をポニービルに送りました。

トワイライト スパークルはナイトメア ムーンの軌跡を追跡したいと考えていました。残念ながら、彼女は正確な道を知りませんでした。彼女が知っていたのは、ナイトメア・ムーンが訪れた各場所の回数の同等性だった。トワイライト スパークルがこの情報と一致するパスを復元するのを手伝っていただけませんか?

ポニービルは、自己ループやマルチエッジのない無向グラフ (頂点は場所、エッジは場所間の道路) として表すことができます。パスは任意の場所で開始および終了できます (空にすることもできます)。各場所は複数回訪れることができます。パスは 4n か所を超えてはなりません。

入力

最初の行には 2 つの整数 n と m が含まれます (2?≤?n?≤?105; 0?≤?m?≤?105) ?ポニービルの場所の数と道路の数。次の各 m 行には 2 つの整数 ui,?vi (1?≤?ui,?vi?≤?n; ui?≠?vi) が含まれており、これらの整数は場所 ui と vi の間の道路を表します。

次の行n 個の整数が含まれます: x1,?x2,?...,?xn (0?≤?xi?≤?1)?各場所を訪問する必要がある回数の等価性。 xi?=?0 の場合、i 番目の場所は偶数回訪問する必要があり、それ以外の場合は奇数回訪問する必要があります。

出力

訪問した場所の数 k を最初の行に出力します ( 0?≤?k?≤?4n）。次に k 個の整数を出力しますか?パスの順序の桁数。 xi?=?0 の場合、i 番目の場所はパスに偶数回出現する必要があり、それ以外の場合、i 番目の場所はパスに奇数回出現する必要があります。指定された道路網には自己ループがないため、パス内の隣接する 2 つの場所は区別される必要があることに注意してください。

必要なパスがない場合は、-1 を出力します。複数の可能なパスがある場合は、そのいずれかを出力できます。

サンプル テスト

入力

3 21 22 31 1 1

出力

31 2 3

input

5 71 21 31 41 53 43 54 50 1 0 1 0

出力

102 1 3 4 5 4 5 4 3 1 

入力

2 00 0

出力

题目大意：

给出一张图、有N个点、M条边、并给出每个点要求访问次数の奇数性。、出力を要求しますパスを通過します。一点、我们完全に制御可能奇偶性，假设：

目前访问的点範囲v，父节点範囲fa，如若点v不符合当前的奇特性，则就让父节点到v绕一次，这样奇数[v] ^= 1、fa[v] ^ = 1、このようにして、要求の奇数性を満たさずに子ノードを完全に制御することができます。同時に、父点の奇数性も変更されます。操作，我们可以每次保護证子节点的奇偶性符合要求，然然父节点的奇偶性如若不符合要求，调整父节点与父节点来调整奇偶性，这样我们就可以奇偶性传递根の点は、この調整方法に適合していない場合はどうすればよいですか？次回归。私たちは、ルート ポイント r1 をルート ポイントの子ポイント r2 に調整して、奇妙に再度調整できるようにすることができます。