No.466 ジオラマ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 31
作問者 : 🍡yurahuna🍡yurahuna / テスター : 🐱ctyl🐱ctyl

1 ProblemId : 1138 / 出題時の順位表

問題文

ある日いろはちゃんは、めぐるちゃんに自分の故郷の話をしていました。
いろはちゃんの故郷では、いくつかの村がいくつかの向きのある水路によってつながれていました。
村には0, 1, 2, ...と順に番号がつけられていました。その中でも村0と村1は特別な村で、水源としての役割を担っていました。
村0あるいは村1から水を流すと、水路を向きの通りに辿って到達可能なすべての村に水が届きます。
1本の水路がある村 $x$ から同じ村 $x$ へ向かうことはありませんが、いくつかの水路を通って水がもとの村に戻ってくることはあり得ます。
また、村0や村1に他の村から水が流れ込むこともあります。
いろはちゃんによれば、故郷は以下のすべての条件を満たしていたといいます。

  • 故郷には2つ以上の村があった。
  • どの村も、村0あるいは村1から水が届いた。
  • 村0から水を流すと、村0を含めて $A$ 個の村に水が届いた。
  • 村1から水を流すと、村1を含めて $B$ 個の村に水が届いた。
  • 村0からも村1からも水が届いた村は $C$ 個であった。(ただし、$C \leq \min(A, B)$ をみたす。)
  • 水路は $D$ 本以下であった。
この話を聞いためぐるちゃんは、故郷を恋しがるいろはちゃんのために故郷のジオラマを作ってあげようと考えました。
ジオラマを作るには、いろはちゃんの述べた条件をすべて満たす「村の個数、水路の個数、水路の接続関係(どの村からどの村に向かって水路が通っているか)」 の組が必要です。
めぐるちゃんの代わりに、このような組を1つ求めてあげましょう。
もしかするといろはちゃんの記憶違いで条件を満たす組が存在しない可能性もあるので、そのときはこっそりと教えてあげましょう。

入力

$A$ $B$ $C$ $D$

入力は1行からなり、1行目には問題文中の $A, B, C, D$ がスペース区切りで与えられます。
$A, B, C, D$ は以下の条件を満たします。

  • $A, B, C, D$ は整数
  • $1 \leq A \leq 10^4$
  • $1 \leq B \leq 10^4$
  • $0 \leq C \leq \min(A, B)$
  • $0 \leq D \leq 10^5$

出力

出力は以下のようになります。

  • 題意を満たす組が存在しない場合、-1を出力し、最後に改行してください。
    この場合、出力は1行のみです。
  • 上記以外の場合、出力は以下のようになります。
    $N$ $M$
    $a_1$ $b_1$
    $a_2$ $b_2$
    $\dots$
    $a_M$ $b_M$
    
    • 1行目には、村の個数 $N$ と 水路の本数 $M$ を出力してください。
    • 2行目から $M + 1$ 行目には、水路が村 $a_i$ から 村 $b_i$ の向きで存在するとき、$a_i$, $b_i$ をスペース区切りで1行ごとに出力してください。
    • ただし、同じ水路を複数出力してはいけません。また、$0 \leq a_i, b_i < N, a_i \neq b_i$を満たさなければなりません。
    • ただし出力は、すべて符号付き64ビット整数型で収まる値でかつ出力の全体は20MBに収まるようにしてください。
    • 最後に改行してください。

サンプル

サンプル1
入力
6 4 2 12
出力
8 10
0 2
0 4
1 2
1 7
2 3
4 2
4 3
4 5
4 6
7 3


解はあくまで一例であり、他にも条件を満たす解は存在します。

サンプル2
入力
5 3 3 5
出力
5 4
0 1
0 2
1 3
1 4


村0から村1に、あるいは村1から村0に水が届くこともあります。

サンプル3
入力
1 4 0 3
出力
5 3
1 2
1 3
1 4


サンプル4
入力
9 8 5 10
出力
-1

どうやら水路の本数が少なすぎるようです。

提出ページヘ