{"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 $2$, $\\ldots$, edge $M$, respectively, and edge $i$ $(1\\leq i\\leq M)$ connects vertices $U_i$ and $V_i$.\nYou 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$.\nWhat 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.  \nA graph $G$ is said to be an undirected graph when the edges of $G$ have no direction.  \nA graph $G$ is simple when $G$ does not contain self-loops or multi-edges.  \nA 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}$.  \nA 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$.\n\n## Constraints\n\n*   $3 \\leq N \\leq 2\\times 10^5$\n*   $N-1\\leq M\\leq\\min\\left(\\frac{N(N-1)}{2},2\\times 10^5\\right)$\n*   $1\\leq A,B,C\\leq N$\n*   $A$, $B$, and $C$ are all distinct.\n*   $1\\leq U_i<V_i\\leq N$\n*   The pairs $(U_i,V_i)$ are all distinct.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$A$ $B$ $C$\n$U_1$ $V_1$\n$U_2$ $V_2$\n$\\vdots$\n$U_M$ $V_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc318_g","tags":[],"sample_group":[["6 7\n1 3 2\n1 2\n1 5\n2 3\n2 5\n2 6\n3 4\n4 5","Yes\n\nOne simple path connecting vertices $1$ and $2$ via vertex $3$ is $1$ $\\to$ $5$ $\\to$ $4$ $\\to$ $3$ $\\to$ $2$.\nThus, print `Yes`."],["6 6\n1 3 2\n1 2\n2 3\n2 5\n2 6\n3 4\n4 5","No\n\nNo simple path satisfies the condition. Thus, print `No`."],["3 2\n1 3 2\n1 2\n2 3","No"]],"created_at":"2026-03-03 11:01:14"}}