6314: ABC231 —— D - Neighbors
[Creator : ]
Description
Determine whether there is a way to line up $N$ people, numbered $1$ to $N$, in a row side by side to satisfy all of the $M$ conditions in the following format.
- Condition: Person $A_i$ and Person $B_i$ are adjacent.
Input
Input is given from Standard Input in the following format:
$N\ M$
$A_1\ B_1$
$\vdots$
$A_M\ B_M$
$N\ M$
$A_1\ B_1$
$\vdots$
$A_M\ B_M$
Output
If there is a way to line up people to satisfy the conditions, print Yes; if not, print No.
Constraints
$2≤N≤10^5$
$0 \leq M \leq 10^5$
$1\leq A_i < B_i \leq N$
All pairs $(A_i,B_i)$ are distinct.
$0 \leq M \leq 10^5$
$1\leq A_i < B_i \leq N$
All pairs $(A_i,B_i)$ are distinct.
Sample 1 Input
4 2
1 3
2 3
Sample 1 Output
Yes
One way to satisfy all the conditions is to line them up in the order $4,1,3,2$.
Sample 2 Input
4 3
1 4
2 4
3 4
Sample 2 Output
No
There is no way to line them up to satisfy all the conditions.