<p>There is a <strong>bi-directional</strong> graph with <code>n</code> vertices, where each vertex is labeled from <code>0</code> to <code>n - 1</code> (<strong>inclusive</strong>). The edges in the graph are represented as a 2D integer array <code>edges</code>, where each <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> denotes a bi-directional edge between vertex <code>u<sub>i</sub></code> and vertex <code>v<sub>i</sub></code>. Every vertex pair is connected by <strong>at most one</strong> edge, and no vertex has an edge to itself.</p>

<p>You want to determine if there is a <strong>valid path</strong> that exists from vertex <code>source</code> to vertex <code>destination</code>.</p>

<p>Given <code>edges</code> and the integers <code>n</code>, <code>source</code>, and <code>destination</code>, return <code>true</code><em> if there is a <strong>valid path</strong> from </em><code>source</code><em> to </em><code>destination</code><em>, or </em><code>false</code><em> otherwise</em><em>.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/14/validpath-ex1.png" style="width: 141px; height: 121px;" />
<pre>
<strong>Input:</strong> n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
<strong>Output:</strong> true
<strong>Explanation:</strong> There are two paths from vertex 0 to vertex 2:
- 0 &rarr; 1 &rarr; 2
- 0 &rarr; 2
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/14/validpath-ex2.png" style="width: 281px; height: 141px;" />
<pre>
<strong>Input:</strong> n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
<strong>Output:</strong> false
<strong>Explanation:</strong> There is no path from vertex 0 to vertex 5.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>0 &lt;= edges.length &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt;= n - 1</code></li>
	<li><code>u<sub>i</sub> != v<sub>i</sub></code></li>
	<li><code>0 &lt;= source, destination &lt;= n - 1</code></li>
	<li>There are no duplicate edges.</li>
	<li>There are no self edges.</li>
</ul>

// clang-format off
static const auto io_sync_off = []() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); return 0; }();
#define tT template<typename T>
#define tAB template<typename A, typename B>
#define Ti typename T::iterator
#define Tv typename T::value_type
#define Tk typename T::key_type
#define Tm typename T::mapped_type
using ll = long long; using S = string;
using pii = pair<int, int>; using pis = pair<int, S>; using psi = pair<S, int>;
tT using V = vector<T>; tT using VV = V<V<T>>; tT using VVV = VV<V<T>>;
using vi = V<int>; using vvi = VV<int>; using vvvi = VVV<int>; using vb = V<bool>; using vvb = VV<bool>; using vs = V<S>; using vd = V<double>; using vli = V<list<int>>;
tT using US = unordered_set<T>; tAB using UM = unordered_map<A, B>;
using si = set<int>; using usi = US<int>; using uss = US<S>;
using mii = map<int, int>; using umii = UM<int, int>; using umib = UM<int, bool>; using umsi = UM<S, int>;
using pqi = priority_queue<int, vi, greater<int>>; using pqri = priority_queue<int, vi>;
constexpr int BIG = 1e9; constexpr int MOD = 1e9 + 7; constexpr int MAX_INT = INT_MAX; constexpr bool fasle = false; constexpr bool ture = true;
#define fi first
#define se second
#define pb push_back
#define F(i, a, b) for(int(i) = (a); (i) < (b); ++(i))
#define Fs(i, a, b, s) for(int(i) = (a); (i) < (b); (i) += (s))
#define Fe(i, a, b) for(int(i) = (a); (i) <= (b); ++(i))
#define FR(i, a, b) for(int(i) = (a); (i) >= (b); --(i))
#define FRn(i, a, b) for(int(i) = (a); (i) > (b); --(i))
#define FE(a, v) for(auto &(a): (v)) // For each element in a container...
#define FEv(v, m) for(auto &[k, v]: (m)) // For each element in a map or unordered_map...
#define FEt(t, s) stringstream ss(s); for(S (t); ss >> (t);) // For each token in a S...
#define W(n) while((n)--)
#define ALL(v) (v).begin(), (v).end()
tT void R(T &v) { reverse(ALL(v)); }
tT void SORT(T &v) { sort(ALL(v)); } tT void SORTR(T &v) { sort(ALL(v), greater()); } tT void SORTf(T &v, const function<bool(const Tv&, const Tv&)> &f) { sort(ALL(v), f); }
#define SORTfab(v, fab) SORTf(v, [&](const auto &a, const auto &b) { return (fab); }) // Sort elements based on a function of any 2 elements `a` and `b`.
tT void UE(T &v) { v.erase(unique(ALL(v)), v.end()); }
tT void SUE(T &v) { SORT(v); UE(v); }
tT int COUNT(const T &v, const Tv &k) { return count(ALL(v), k); }
#define COUNTifa(v, ifa) count_if(ALL(v), [&](const auto &a) { return (ifa); }) // Count elements based on an if-condition of any elemnent `a`.
tT int sz(const T &v) { return v.size(); }
#define szXY(vv) int X = sz(vv), Y = X ? sz((vv)[0]) : 0
tT auto maxe(T &v) { return max_element(ALL(v)); } tT auto mine(T &v) { return min_element(ALL(v)); } tT Tv maxv(const T &v) { return *maxe(v); } tT Tv minv(const T &v) { return *mine(v); } tT int maxvi(const T &v) { return maxe(v) - v.begin(); } tT int minvi(const T &v) { return mine(v) - v.begin(); }
tT auto lb(T &v, const Tv &k) { return lower_bound(ALL(v), k); } tT auto ub(T &v, const Tv &k) { return upper_bound(ALL(v), k); } tT auto lub(T &v, const Tv &k) { return pair{lb(v, k), ub(v, k)}; }
tT Tv SUM(const T &v) { return accumulate(ALL(v), Tv{0}); }
#define SUMifa(v, ifa) accumulate(ALL(v), 0, [](const auto &s, const auto &a) { return s + ((ifa) ? a : 0); }) // Sum elements based on an if-condition of any element `a`.
#define SUMfa(v, fa) accumulate(ALL(v), 0, [](const auto &s, const auto &a) { return s + (fa); }) // Sum elements with a function of any element `a`.
tT vi HISTV(const T &v, int n, int b = 0, const function<bool(const Tv&)> &if_ = [](const Tv &a) { return true; }) { vi hist(n); FE(a, v) if(if_(a)) hist[a - b]++; return hist; }
#define HISTVifa(v, n, b, ifa) HISTV((v), (n), (b), [](const auto &a) { return (ifa); })
tT UM<Tv, int> HISTM(const T &v, const function<bool(const Tv &)> &if_ = [](const Tv &a) { return true; }) { UM<Tv, int> um; FE(a, v) if(if_(a)) um[a]++; return um; }
#define HISTMifa(v, ifa) HISTM((v), [](const auto &a) { return (ifa); })
vi IOTA(int n, int b = 0) { vi v(n); iota(ALL(v), b); return v; } // Create a `vector<int>` with b+0, b+1, b+2, ..., b+n-1. `b` means base.
tT V<Tm> Mv2V(const T &m) { V<Tm> v(sz(m)); int i = 0; FEv(a, m) v[i++] = a; return v; }
tT V<pair<Tk, Tm>> Mp2V(const T &m) { V<pair<Tk, Tm>> v(sz(m)); int i = 0; FE(p, m) v[i++] = p; return v; }
tT T POP(queue<T> &q) { T r = q.front(); q.pop(); return r; } tT Tv POP(T &c) { Tv r = c.top(); c.pop(); return r; }
tT VV<T> _T(const VV<T> &vv) { szXY(vv); VV<T> r(X, V<T>(Y)); for(int y = 0; y < Y; y++) for(int x = 0; x < X; x++) r[y][x] = vv[x][y]; return r; }
tT void _P(const T &t) { cout << t << " "; } tT void _P(const V<T> &v) { FE(k, v) cout << k << " "; cout << endl; } tT void _P(const VV<T> &vv) { FE(v, vv) { FE(k, v) cout << k << " "; cout << endl; } }
template<typename ...T> void P(const T& ...t) { (_P(t), ...); cout << endl; }
tAB pair<A, B> operator+(const pair<A, B> &a, const pair<A, B> &b) { return {a.fi + b.fi, a.se + b.se}; } tAB pair<A, B> &operator+=(pair<A, B> &a, const pair<A, B> &b) { a.fi += b.fi; a.se += b.se; return a; } tAB pair<A, B> operator-(const pair<A, B> &a, const pair<A, B> &b) { return {a.fi - b.fi, a.se - b.se}; } tAB pair<A, B> &operator-=(pair<A, B> &a, const pair<A, B> &b) { a.fi -= b.fi; a.se -= b.se; return a; }
tT T operator+(const T &a, const T &b) { T c; c.reserve(sz(a)); transform(ALL(a), b.begin(), back_inserter(c), plus()); return c; } tT T& operator+=(T &a, const T &b) { transform(ALL(a), b.begin(), a.begin(), plus()); return a; } tT T operator-(const T &a, const T &b) { T c; c.reserve(sz(a)); transform(ALL(a), b.begin(), back_inserter(c), minus()); return c; } tT T& operator-=(T &a, const T &b) { transform(ALL(a), b.begin(), a.begin(), minus()); return a; }
// clang-format on

/*
int r = 0, n = sz(v);
return r;
*/

//****************************************************************************************************

class Solution {
public:
    bool validPath(int n, vector<vector<int>> &edges, int source, int destination) {
        vi v = IOTA(n);
        FE(e, edges) {
            vi r(2);
            F(i, 0, 2) {
                int k = e[i];
                while(k != v[k])
                    k = v[k];
                r[i] = k;
            }
            SORT(r);
            v[r[1]] = r[0];
        }
        while(v[source] != source)
            source = v[source];
        while(v[destination] != destination)
            destination = v[destination];
        return source == destination;
    }
};

236662