Road network

#include <stdio.h>
#include <iostream>
#include <memory.h>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

#define sqr(a) ((a) * (a))
#define pi 3.1415926535897932384626433832795
const double EPS = 1e-12;
#define TASK "l"
//#define CONTEST 1
#define MAXN 100005
#define MAXE 400005

int fst[MAXN], nxt[MAXE], en[MAXE];
int was[MAXN];
int cnt;
int A[MAXE], B[MAXE];
int n, m;
vector <int> ts;

void AddEdge(int a, int b)
{
	nxt[cnt] = fst[a];
	fst[a] = cnt;
	en[cnt] = b;
	cnt++;	
}

void dfs(int x)
{
	was[x] = 1;

	for(int i = fst[x]; i != -1; i = nxt[i])
	{
		if(was[en[i]] != 1)
			dfs(en[i]);
	}	

	ts.push_back(x);
}

void Load()
{
	cin >> n >> m;
	for(int i = 0; i < m; i++)
	{
		cin >> A[i] >> B[i];
		AddEdge(B[i], A[i]);
	}
}

void Solve()
{
	for(int i = 1; i <= n; i++)
	{
		if (was[i] != 1) dfs(i);
	}
	reverse(ts.begin(), ts.end());

	cnt = 0;
	memset(fst, -1, sizeof(fst));
	memset(was, 0, sizeof(was));
	for(int i = 0; i < m; i++)
		AddEdge(A[i], B[i]);

	bool ok = true;
	int ind = 0;
	dfs(ts[0]);
	for(int i = 1; i <= n; i++)
	{
		if(was[i] != 1)
		{
			ok = false;
			ind = i;
			break;
		} 
	}

	if (ok)
		cout << "YES" << endl;
	else
	{
		cout << "NO" << endl;
		cout << ts[0] << " " << ind << endl;
	}
}

int main()
{
#ifdef CONTEST
	freopen(TASK".in", "r", stdin);
	freopen(TASK".out", "w", stdout);
#endif
	memset(fst, -1, sizeof(fst));
	Load();
	Solve();

	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED