Typical Path Problem

AtCoder

IDabc318_g

Time2000ms

Memory256MB

Difficulty—

You are given a simple connected undirected graph $G$ with $N$ vertices and $M$ edges. The vertices and edges of $G$ are numbered as vertex $1$, vertex $2$, $\ldots$, vertex $N$, and edge $1$, edge $2$, $\ldots$, edge $M$, respectively, and edge $i$ $(1\leq i\leq M)$ connects vertices $U_i$ and $V_i$. You are also given distinct vertices $A,B,C$ on $G$. Determine if there is a simple path connecting vertices $A$ and $C$ via vertex $B$. What is a simple connected undirected graph? A graph $G$ is said to be a simple connected undirected graph when $G$ is an undirected graph that is simple and connected. A graph $G$ is said to be an undirected graph when the edges of $G$ have no direction. A graph $G$ is simple when $G$ does not contain self-loops or multi-edges. A graph $G$ is connected when one can travel between all vertices of $G$ via edges. What is a simple path via vertex $Z$? For vertices $X$ and $Y$ on a graph $G$, a simple path connecting $X$ and $Y$ is a sequence of distinct vertices $(v_1,v_2,\ldots,v_k)$ such that $v_1=X$, $v_k=Y$, and for every integer $i$ satisfying $1\leq i\leq k-1$, there is an edge on $G$ connecting vertices $v_i$ and $v_{i+1}$. A simple path $(v_1,v_2,\ldots,v_k)$ is said to be via vertex $Z$ when there is an $i$ $(2\leq i\leq k-1)$ satisfying $v_i=Z$. ## Constraints * $3 \leq N \leq 2\times 10^5$ * $N-1\leq M\leq\min\left(\frac{N(N-1)}{2},2\times 10^5\right)$ * $1\leq A,B,C\leq N$ * $A$, $B$, and $C$ are all distinct. * $1\leq U_i<V_i\leq N$ * The pairs $(U_i,V_i)$ are all distinct. * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $M$ $A$ $B$ $C$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$ [samples]

Samples

Input #1

Output #1

Yes

One simple path connecting vertices $1$ and $2$ via vertex $3$ is $1$ $\to$ $5$ $\to$ $4$ $\to$ $3$ $\to$ $2$.
Thus, print `Yes`.

Input #2

Output #2

No

No simple path satisfies the condition. Thus, print `No`.

Input #3

Output #3

No

API Response (JSON)

{
  "problem": {
    "name": "Typical Path Problem",
    "description": {
      "content": "You are given a simple connected undirected graph $G$ with $N$ vertices and $M$ edges.   The vertices and edges of $G$ are numbered as vertex $1$, vertex $2$, $\\ldots$, vertex $N$, and edge $1$, edge ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc318_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a simple connected undirected graph $G$ with $N$ vertices and $M$ edges.  \nThe vertices and edges of $G$ are numbered as vertex $1$, vertex $2$, $\\ldots$, vertex $N$, and edge $1$, edge ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments