問題一覧 > 通常問題

No.3291 K-step Navigation

レベル : / AI推定難易度 : 1750 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 46
作問者 : kona0001 / テスター : tobisatis RyosukeFukatani koba-e964 ir5 drken1215
お気に入りにしたユーザー ProblemId : 12635 / 自分の提出
問題文最終更新日: 2025-09-24 02:01:53
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 485 (順位表) の他の問題:

Problem Statement

You are given a simple undirected graph $G$ with $N$ vertices and $M$ edges. The vertices of $G$ are numbered vertex $1$, vertex $2$, ..., vertex $N$, and the $i$-th $(1≤i≤M)$ edge connects vertex $u_i$ and vertex $v_i$.

Initially, $1$ piece is placed on vertex $s$ of $G$. Consider moving this piece according to the following rule.

  • Choose $1$ vertex connected by an edge to the vertex where the piece is placed, and move the piece to that vertex. If not even $1$ edge extends from the vertex, do nothing.

You may add at most $1$ undirected edge to $G$ that is neither a self-loop nor a parallel edge.

Determine whether, after this addition, the piece can be placed on vertex $t$ by moving it exactly $K$ times.

Constraints

  • $2 \le N \le 2000$
  • $0 \le M \le \min\left(\frac{N(N-1)}{2}, 2000 \right)$
  • $1 \le K \le 10^{18}$
  • $1 \le s,t \le N$
  • $s \neq t$
  • $1 \le u_i < v_i \le N$
  • If $i \neq j$, then $(u_i,v_i) \neq (u_j,v_j)$
  • All input values are integers

Input

The input is given from standard input in the following format.

$N\ M\ K\ s\ t$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_M\ v_M$

Output

Print Yes if the piece can be placed on vertex $t$ with exactly $K$ moves, and No otherwise. Print a newline at the end.

Sample

Sample 1
Input
5 4 3 1 5
1 2
2 3
3 4
4 5
Output
Yes

For example, if you add an undirected edge connecting vertex $2$ and vertex $4$, moving the piece as $(1 → 2 → 4 → 5)$ places it on vertex $5$ with exactly $3$ moves.

Sample 2
Input
6 6 4 1 6
1 2
2 3
1 3
4 5
5 6
4 6
Output
Yes

Note that the given graph is not necessarily connected.

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