No.629 グラフの中に眠る門松列

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 122
作問者 : maimai / テスター : ixmelixmel
1 ProblemId : 1683 / 出題時の順位表
問題文最終更新日: 2017-12-27 19:51:39

定義

3つの自然数から成る数列 $x = (x_1,x_2,x_3)$ が次の条件を満たす時,$x$ は門松列と呼びます.

  1. $x_1,x_2,x_3$ は全て異なる
  2. 3つの要素のうち $x_2$ が最も大きい,あるいは最も小さい

始点と終点が異なり,どの頂点も高々一度しか通らない,ある頂点からある頂点への行き方をパスと呼びます.
長さ2のパスとは,2つの辺と3つの頂点によって構成されているパスのことです.

さらに,この問題では,門松パスと呼ばれるものを定義します.
長さ2のパスの始点から終点までの頂点に書かれた数字を順に $x=(x_1,x_2,x_3)$ として, $x$ が門松列を満たすとき,そのパスを門松パスと呼びます.


問題文

$N$個の頂点と$M$個の無向辺から構成されるグラフが与えられます.

$i$番目の頂点には,数字$a_i$が書き込まれています.
$j$番目の辺は,$u_j$番目の頂点と,$v_j$番目の頂点に接続しています.


与えられたグラフの中に門松パスは存在するでしょうか.
与えられたグラフの中に門松パスが存在するならば'YES',なければ'NO'と出力してください.

入力

$N$ $M$
$a_1$ $a_2$ $\ldots$ $a_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\ldots$
$u_M$ $v_M$

$2 \le N \le 1000$
$0 \le M \le \min\{N(N-1)/2,4000\}$
$1 \le a_i \le 10^9$
$1 \le u_j \lt v_j \le N$

与えられるグラフは多重辺が存在しない($i \neq j$ならば$u_i \neq u_j$か$v_i \neq v_j$のいずれかを満たす).

出力

与えられたグラフの中に門松パスが存在するならば'YES',なければ'NO'と出力してください.

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

サンプル

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

頂点の中に書かれた白数字は,書き込まれた数字$a_i$です.
頂点の近くに$[1]$の形式で書かれた数字は,頂点番号を意味します.
同様に,辺の近くに$(1)$の形式で書かれた数字は,辺番号を意味します.

長さ2のパスとして,例えば$[1] \rightarrow (1) \rightarrow [2] \rightarrow (2) \rightarrow [3]$があります.
この順で書き込まれた数字を確認すると$(a_1,a_2,a_3) = (2,1,3)$となり,門松パスが存在することが確認できました.

$[2] \rightarrow (1) \rightarrow [1] \rightarrow (5) \rightarrow [5]$は,長さ2のパスですが門松パスではありません.

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

与えられるグラフは連結とは限りません.
辺が全く刺さらない頂点も考えられます.

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

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

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

サンプル6
入力
3 2
1 3 2
1 2
2 3
出力
YES

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。