How to solve this adhoc task?
You are given an undirected graph with $$$N$$$ vertexes and $$$M$$$ edges. Each vertex $$$i$$$ has a value, $$$a[i]$$$.
Is is possible to make all vertexes have the same value, using the following operation multiple times (or not use it at all):
- If there is a vertex $$$u$$$, such that vertexes $$$v$$$ and $$$w$$$ are directly connected to it, then change $$$a[v]$$$, $$$a[w]$$$ to $$$a[v] + k$$$ and $$$a[w] + k$$$ respectively, where $$$k$$$ is any integer.
If it is possible, print "YES", else "NO".
$$$N$$$ <= 100000, $$$M$$$ <= 200000
Link: https://www.acmicpc.net/problem/30187
I have been thinking in direction that if it is not a bipartite graph, then answer is YES. No idea is that even right or not.