In this problem, given a directed graph with $n$ nodes and $m$ edges, we need to return "YES" if we can travel between all pairs of vertices $u, v$ or "NO" and give pair of vertices we can't travel between otherwise.

Main Idea

Let's say $\texttt{can[u][v]} = 1$ if you can go from vertex $u$ to vertex $v$. Additionally, let's define the directed graph given in the statement as $G$ and the reverse of it (where an edge $u \rightarrow v$ becomes $v \rightarrow u$) as $G'$. Then, if $\texttt{can[1][x]}$ for $1 \leq x \leq n$ in both $G$ and $G'$, the answer is "YES".

To compute $\texttt{can[1][x]}$, we can run a dfs from from vertex $1$ and check if you can reach vertex $x$ for all $1 \leq x \leq n$. If we can't, then print $1$ $x$ if you're running the DFS on $G$ and $x$ $1$ otherwise.

Proof

Let's do a proof by contradiction. Assume that $\texttt{can[1][x]}$ is true for all vertices $x$ in both $G$ and $G'$, and there exists a pair of vertices $u, v$ such that $\texttt{can[u][v]} = 0$. Since $\texttt{can[1][u]}$ is true in $G'$, then $\texttt{can[u][1]}$ must be true in $G$. Additionally, $\texttt{can[1][v]}$ must be true in $G$. So, you can travel from $u \rightarrow 1 \rightarrow v$, which contradicts the statement that $\texttt{can[u][v]} = 0$. Thus, $\texttt{can[u][v]} = 1$ for all vertices $u, v$.

Example Code

#include <bits/stdc++.h> // see C++ Tips & Tricks
using namespace std;

using ll = long long;

using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()