2024-10-28-soltuion-cf1027f

小清新好题。连边 $a_i,b_i$ 如果一个连通块 $m > n$ 显然无解否则只剩下是树或者基环树。基环树的情况顶满最大值，树的情况是次小值。

// Problem: Session in BSU
// URL: https://www.luogu.com.cn/problem/CF1027F
// Writer: WRuperD
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 1e6 + 10;

int a[MAX], b[MAX];
int lsh[MAX * 2];
bool vis[MAX << 1];
int cnt, cnt2;
int maxn, maxn2;

vector <int> g[MAX << 1];

void dfs(int u){
	vis[u] = 1;
	cnt++;
	if(maxn < u){
		maxn2 = maxn;
		maxn = u;
	}else{
		maxn2 = max(maxn2, u);
	}
	for(int v : g[u]){
		cnt2++;
		if(!vis[v])	dfs(v);
	}
}

void solve(){
	int n = read();
	for(int i = 1; i <= n; i++){
		a[i] = read(), b[i] = read();
		lsh[2 * i - 1] = a[i], lsh[2 * i] = b[i];
	}
	sort(lsh + 1, lsh + 2 * n + 1);
	int m = unique(lsh + 1, lsh + 2 * n + 1) - lsh - 1;
	for(int i = 1; i <= n; i++)	a[i] = lower_bound(lsh + 1, lsh + m + 1, a[i]) - lsh;
	for(int i = 1; i <= n; i++)	b[i] = lower_bound(lsh + 1, lsh + m + 1, b[i]) - lsh;
	for(int i = 1; i <= n; i++){
		g[a[i]].pb(b[i]);
		g[b[i]].pb(a[i]);
	}
	int ans = 0;
	for(int i = 1; i <= m; i++){
		if(!vis[i]){
			cnt = cnt2 = 0;
			maxn = maxn2 = 0;
			dfs(i);
			cnt2 /= 2;
			if(cnt == cnt2 + 1){
				ans = max(ans, maxn2);
			}else if(cnt == cnt2){
				ans = max(ans, maxn);
			}else{
				puts("-1");
				exit(0);
			}
			// write(cnt), put(), write(cnt2), endl;
		}
	}
	// write(ans), endl;
	write(lsh[ans]), endl;
}

signed main(){
	int t = 1;
	while(t--)	solve();
	return 0;
}