Description：

给定一个有向无环图，每条边长度都是 $1$ ，找到一个点，使得删掉这个点后剩余的图中的最长路径最短。

$1\leqslant n\leqslant 5\times 10^5$

Solution：

既然是 $DAG$ ，那就先跑一个拓扑排序，新建一个源和汇，然后发现对于一条路径能更新除了这条路径上的点之外的点，那么就可以枚举每条边，用从源点到他的最长链 $+$ 他到汇点的最长链 $+1$ 来更新拓扑序在边两端点之间，不包括两个端点的所有点的答案，这个可以用线段树维护拓扑序打标记实现，但是这样漏掉了一种情况，就是原来的路径的开始和结尾被删掉了，所以还要枚举每个点作为开始和结尾，用源点到他的最长链和他到汇点的最长链分别更新前缀和后缀。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 500010

#define MAXM 1000010

struct edges

{

	int u,v;

}es[MAXM];

int cnt = 0;

struct edge

{

	int to,nxt;

}e[MAXM];

int edgenum = 0;

int lin[MAXN] = {0};

int ind[MAXN] = {0},oud[MAXN] = {0};

void add(int a,int b)

{

	++ind[b];++oud[a];

	es[++cnt] = (edges){a,b};

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	return;

}

int st,en;

int topo[MAXN],pos[MAXN],tot = 0;

int lef[MAXN],rig[MAXN];

struct node

{

	int lc,rc;

	int maxv;

	node(){maxv = 0xc0c0c0c0;}

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void add(int rt,int L,int R,int k,int l,int r)

{

	if(L > R)return;

	if(t[rt].maxv >= k)return;

	if(L <= l && r <= R)

	{

		t[rt].maxv = k;

		return;

	}

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	return;

}

int ans[MAXN];

void pushdown(int rt)

{

	t[t[rt].lc].maxv = max(t[t[rt].lc].maxv,t[rt].maxv);

	t[t[rt].rc].maxv = max(t[t[rt].rc].maxv,t[rt].maxv);

	return;

}

void pt(int rt,int l,int r)

{

	if(l == r)

	{

		ans[l] = t[rt].maxv;

		return;

	}

	pushdown(rt);

	pt(t[rt].lc,l,mid);

	pt(t[rt].rc,mid + 1,r);

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		a = rd();b = rd();

		add(a,b);

	}

	queue<int> q;

	memset(lef,0xc0,sizeof(lef));

	memset(rig,0xc0,sizeof(rig));

	st = n + 1;en = st + 1;

	for(int i = 1;i <= n;++i)

		if(ind[i] == 0)add(st,i);

	for(int i = 1;i <= n;++i)

		if(oud[i] == 0)add(i,en);

	q.push(st);

	while(!q.empty())

	{

		int k = q.front();q.pop();

		topo[++tot] = k;pos[k] = tot;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			--ind[e[i].to];

			if(ind[e[i].to] == 0)q.push(e[i].to);

		}

	}

	lef[st] = 0;rig[en] = 0;

	for(int k = 1;k <= n + 2;++k)

		for(int i = lin[topo[k]];i != 0;i = e[i].nxt)

			if(lef[e[i].to] < lef[topo[k]] + 1)

				lef[e[i].to] = lef[topo[k]] + 1;

	for(int k = n + 2;k >= 1;--k)

		for(int i = lin[topo[k]];i != 0;i = e[i].nxt)

			if(rig[e[i].to] + 1 > rig[topo[k]])

				rig[topo[k]] = rig[e[i].to] + 1;

	build(root,1,n + 2);

	for(int i = 1;i <= cnt;++i)

	{

		add(root,pos[es[i].u] + 1,pos[es[i].v] - 1,lef[es[i].u] + rig[es[i].v] + 1,1,n + 2);

	}

	for(int i = 1;i <= n;++i)add(root,2,pos[i] - 1,rig[i] + 1,1,n + 2);

	for(int i = 1;i <= n;++i)add(root,pos[i] + 1,n + 1,lef[i] + 1,1,n + 2);

	pt(root,1,n + 2);

	int ans1 = 0x3f3f3f3f,ans2;

	for(int i = 2;i <= n + 1;++i)

	{

		if(ans[i] < ans1)

		{

			ans1 = ans[i];

			ans2 = i;

		}

	}

	cout << topo[ans2] << " " << ans1 - 2 << endl;

	return 0;

}