No.2464 To DAG
タグ : / 解いたユーザー数 31
作問者 : 👑 Nachia / テスター : hirayuu_yc
問題文
頂点 辺の有向グラフがあります。 このグラフが単純グラフであるとは限りませんが、自己ループはもちません。 頂点は から の番号で区別されます。 番目の辺は頂点 から出て頂点 に向かっています。 各頂点 について、頂点 から出る辺の個数を 、頂点 に向かう辺の個数を として、 とします。
このグラフから 個以上の辺を選んで取り除くことで、新しいグラフを作ります。 このとき、新しいグラフとしてあり得るものであって、次の条件をすべて満たすものが存在するかどうか判定し、存在するならば つ求めてください。
- 各頂点 について、元のグラフと比べて の値が変化していない。
- サイクルをもたない。
求めたグラフは、入力と同じ形式で出力してください。
制約
入力は次の制約を満たします。
- 値はすべて整数
入力
出力
条件を満たす新しいグラフが存在しない場合は、 -1
という 行のみ出力してください。
存在する場合は、そのグラフを入力と同じ形式で出力してください。 問題文の条件を満たすグラフが複数ある場合、どれを出力しても構いません。 辺の順番は問いません。 念のため、最後は改行してください。
サンプル
サンプル1
入力
5 7 1 2 1 3 1 5 2 4 3 4 4 1 5 2
出力
5 4 1 2 1 5 2 4 5 2
番目の辺が残っています。
また、 番目の辺を残したグラフも条件を満たすため、次の出力でも正解になります。
5 3 1 3 3 4 1 2
サンプル2
入力
10 20 7 5 3 2 5 2 2 1 3 5 10 3 6 7 8 6 5 3 7 3 5 1 8 7 2 3 2 6 2 4 10 5 1 8 2 4 10 9 10 2
出力
10 10 5 2 2 1 10 3 8 6 2 3 2 4 10 5 2 4 10 9 10 2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。