問題一覧 > 通常問題

No.1914 Directed by Two Sequences

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 3
作問者 : chineristACchineristAC / テスター : HYEA LEEHYEA LEE tokusakuraitokusakurai
1 ProblemId : 7227 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-13 23:38:26

問題文

長さ $N$ の整数列 $A=(A_1,\ A_2,\ \dots,\ A_N),\ B=(B_1,\ B_2,\ \dots,\ B_N)$ および $M$ 個の $2$ 頂点の組 $(u_i,\ v_i)\ (1\le i \le M)$ が与えられます。

$N$ 頂点 $\frac{N(N-1)}{2}-M$ 辺の有向グラフ $G$ があります。$2$ 頂点 $x,\ y\ (1\le x < y \le N)$ 間の有向辺については

  • ある整数 $i\ (1\le i \le M)$ があって $(x,\ y)=(u_i,\ v_i)$ が成り立つとき
  • 頂点 $x,\ y$ 間に有向辺は存在しない。

  • そうでない場合
  • $A_x < B_y$ のとき頂点 $x$ から頂点 $y$ へ向かう有向辺が、そうでないとき頂点 $y$ から頂点 $x$ へ向かう有向辺が存在する。

が成り立ちます。

以下の条件を満たす単純有向グラフ $G'$ を $1$ つ求めて下さい。この問題の制約の下で条件を満たす $G'$ が $1$ つ以上存在することが証明できます。

条件

  • 頂点数は $N$ であり、辺の数は $3 \times 10^5$ 以下
  • 「グラフ $G$ において頂点 $x$ から頂点 $y$ へのパスが存在する $\iff$ グラフ $G'$ において頂点 $x$ から頂点 $y$ へのパスが存在する」が成り立つ

入力

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$
  • $1 \le N \le 5 \times 10^4$
  • $0 \le M \le \min(\frac{N(N-1)}{2},10^5)$
  • $1 \le A_i,B_i \le 2N$
  • $i \neq j$ ならば $A_i \neq A_j,\ B_i \neq B_j$
  • $A_i \neq B_j\ (1\le i,\ j \le N)$
  • $1 \le u_i < v_i \le N$
  • $i \neq j$ ならば $(u_i,\ v_i) \neq (u_j,\ v_j)$
  • 与えられる入力はすべて整数

出力

$G'$ の辺数を $M'$ 、 $i$ 番目の辺は頂点 $u'_i$ から頂点 $v'_i$ へ向かう辺であるとして、以下の形式で出力してください。

$M'$
$u'_1$ $v'_1$
$u'_2$ $v'_2$
$\vdots$
$u'_{M'}$ $v'_{M'}$

出力は(問題の条件に加えて)以下の条件を満たす必要があります。

  • $0 \le M' \le 3 \times 10^5$
  • $1 \le u'_i,\ v'_i \le N$
  • $i \neq j$ ならば $(u'_i,\ v'_i) \neq (u'_j,\ v'_j)$

条件を満たすグラフが複数存在する場合、いずれを出力してもかまいません。

最後に改行してください。

サンプル

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

頂点 $x$ から頂点 $y$ に向かう辺を $(x,\ y)$ と表すことにすると、グラフ $G$ が持つ辺は $(1,\ 3),\ (4,\ 1),\ (2,\ 3),\ (2,\ 4),\ (3,\ 4)$ の $5$ 辺です。

頂点 $1$ からは頂点 $1,\ 3,\ 4$ へ向かうパスが存在します。頂点 $3,\ 4$ も同様です。頂点 $2$ からは頂点 $1,\ 2,\ 3,\ 4$ へ向かうパスが存在します。

グラフ $G'$ はグラフ $G$ から辺 $(2,\ 4)$ を除いたものであり、$2$ 頂点間のパスの有無は変化していません。

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

グラフ $G$ が辺を持たないことがあります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。