花絮：
这场看起来打得还不错的样子……（别问我是用哪个号打的）。
然后听说这题的思想被出了好多次，女生赛也出过，quailty算法，然而当时没反应过来，而且时间不多啦。
题意：
有n个人，每个人有两个时间点可以参加考试，任意两人不能在同一时间点参加考试。问最迟考试的人的考试时间最早是多少？
$n\leq 10^6.$
题解：
离散化，将每人的两个时间点连边。题意可以转化为：给每条边定向满足任意一点入度至多为1，使得每条边指向的点的编号最大值最小。
要满足任意一点入度至多为1，原图必须是基环森林（每个连通块必须是基环树或树）。先判不合法的情况。然后对于每个连通块，如果是基环树，那么每个点一定有1的入度，用最大值更新答案；如果是树，那么最多使得根节点没有入度，其余点都有1的入度，所以把最大编号设为根，用次大值更新答案。每个连通块的值的最大值即为最终答案。
复杂度$\mathcal{O}(n\log n)$。
代码实现可能不是很简洁明了（好像可以用并查集维护），不过思路是没错的。
code:
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define ll long long
#define inf 1000000001
#define y1 y1___
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
char gc(){
static char buf[],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
ll read(){
char ch=gc();ll x=;int op=;
for (;!isdigit(ch);ch=gc()) if (ch=='-') op=-;
for (;isdigit(ch);ch=gc()) x=(x<<)+(x<<)+ch-'';
return x*op;
}
#define N 2000005
int n,sl,q[N],cnt=,head[N],num,Mx,Mx2,vis[N],dep[N],ans;
struct edge{int to,nxt;}e[N];
struct node{int x,y;}a[N];
void adde(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
void dfs(int u,int pr){
vis[u]=;
if (q[u]>Mx) Mx2=Mx,Mx=q[u];else Mx2=max(Mx2,q[u]);
for (int i=head[u];i;i=e[i].nxt) if ((i^)!=pr){
int v=e[i].to;
if (!vis[v]) dep[v]=dep[u]+,dfs(v,i);
else if (dep[u]>dep[v]) num++;
}
}
int main(){
n=read();int x,y;
rep (i,,n){
q[++sl]=a[i].x=read(),q[++sl]=a[i].y=read();
if (a[i].x>a[i].y) swap(a[i].x,a[i].y);
}
sort(&q[],&q[sl+]);sl=unique(&q[],&q[sl+])-q-;
rep (i,,n){
a[i].x=lower_bound(&q[],&q[sl+],a[i].x)-q;
a[i].y=lower_bound(&q[],&q[sl+],a[i].y)-q;
adde(a[i].x,a[i].y);adde(a[i].y,a[i].x);
}
rep (i,,sl) if (!vis[i]){
num=Mx=Mx2=;
dfs(i,);
if (num>) return puts("-1"),;
if (num==) ans=max(ans,Mx);else ans=max(ans,Mx2);
}
printf("%d\n",ans);
return ;
}