У завданні слід вивести "YES", якщо граф є сильно зв'язним. Граф називається сильно зв'язним, якщо для будь-якої його вершини $v$ виконуються наступні умови:

• з вершини $v$ досяжні всі інші вершини графа;

• вершина $v$ досяжна з будь-якої іншої вершини. Іншими словами, з будь-якої вершини існує шлях до $v$, що еквівалентно досяжності по зворотних ребрах.

Зафіксуємо вершину v = 1 і перевіримо виконання цих умов.

Реалізація алгоритму

Вхідний граф зберігаємо в списку суміжності $g$. Зворотний граф зберігаємо в списку суміжності $gr$.

vector<vector<int> > g, gr;
vector<int> used;

Функція dfs1 виконує обхід графа в глибину.

void dfs1(int v)
{
  used[v] = 1;
  for (int to : g[v])
    if (!used[to]) dfs1(to);
}

Функція dfs2 виконує обхід графа в глибину на зворотному графі.

void dfs2(int v)
{
  used[v] = 1;
  for (int to : gr[v])
    if (!used[to]) dfs2(to);
}

Основна частина програми. Читаємо вхідні дані. Будуємо зворотний граф.

scanf("%d %d", &n, &m);
g.resize(n + 1);
gr.resize(n + 1);
for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  gr[b].push_back(a);
}

Запускаємо пошук в глибину в вихідному графі, починаючи з вершини $1$.

used.resize(n + 1);
dfs1(1);
for (i = 1; i <= n; i++)
  if (used[i] == 0) break;

Якщо вершина $i$ недосяжна (used[i] = 0), то переміщення між містами $1$ і $i$ неможливе.

if (i <= n)
{
  printf("NO\n%d %d\n", 1, i);
  return 0;
}

Запускаємо пошук в глибину на зворотному графі, починаючи з вершини $1$.

used.clear();
used.resize(n + 1);
dfs2(1);
for (i = 1; i <= n; i++)
  if (used[i] == 0) break;

Якщо вершина $i$ недосяжна з $1$ в зворотному графі (used[i] = 0), то переміщення між містами $i$ і $1$ неможливе.

if (i <= n)
{
  printf("NO\n%d %d\n", i, 1);
  return 0;
}

Граф є сильно зв'язним. Виводимо повідомлення "YES".

printf("YES\n");