問題一覧 > 通常問題

No.2664 Prime Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 122
作問者 : suisensuisen / テスター : 👑 p-adicp-adic cureskolcureskol 👑 ygussanyygussany
1 ProblemId : 10366 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-01-05 15:02:19

問題文

正整数 $n$ および $m$ 個の整数組 $(a _ i, b _ i)\ (i = 1, 2, \ldots, m)$ が与えられます。

ここで $a _ i,b _ i$ は $1$ 以上 $n$ 以下の整数であり、$a _ i \neq b _ i$ が保証されます。

次の条件を全て満たす長さ $n$ の数列 $X = (X _ 1, X _ 2, \ldots, X _ n)$ が存在するかを判定してください。

  • 全ての $i = 1, 2, \ldots, n$ について、$X _ i$ は $2$ 以上の 整数である
  • 全ての $i = 1, 2, \ldots, m$ について、$X _ {a _ i} + X _ {b _ i}$ は素数である

入力

入力は以下の形式で標準入力から与えられます。

$n\ m$
$a _ 1\ b _ 1$
$a _ 2\ b _ 2$
$\vdots$
$a _ m\ b _ m$
  • 入力は全て整数で与えられる
  • $2\leq n\leq 100$
  • $1\leq m\leq \dfrac{n(n-1)}{2}$
  • $1\leq a _ i, b _ i\leq n$
  • 全ての $1\leq i\leq m$ なる整数 $i$ に対して $a_i\neq b_i$
  • 全ての $1\leq i\lt j\leq m$ なる整数 $i,j$ に対して $(a_i,b_i)\neq (a_j,b_j)$ かつ $(a_i,b_i)\neq (b_j,a_j)$

出力

条件を満たす $X$ が存在するならば Yes を、存在しないならば No を $1$ 行に出力して改行してください。

サンプル

サンプル1
入力
4 4
1 2
2 3
3 4
4 1
出力
Yes

入力は $n = 4,\ m = 4, (a _ 1, b _ 1) = (1, 2),\ (a _ 2, b _ 2) = (2, 3),\ (a _ 3, b _ 3) = (3, 4),\ (a _ 4, b _ 4) = (4, 1)$ を表します。

例えば $X = (2,3,8,5)$ とすると確かに条件が成り立つので、答えとして Yes を出力してください。

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

条件を満たす $X$ は存在しないことを証明できます。

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