No.3291 K-step Navigation
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
kona0001
drken1215