問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 175
作問者 : maimai / テスター : ixmelixmel
2 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

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