As the name of the task implies, you are asked to do some work with segments and trees.

Recall that a tree is a connected undirected graph such that there is exactly one simple path between every pair of its vertices.

You are given $n$ segments $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$, $l_i < r_i$ for every $i$. It is guaranteed that all segments' endpoints are integers, and all endpoints are unique — there is no pair of segments such that they start in the same point, end in the same point or one starts in the same point the other one ends.

Let's generate a graph with $n$ vertices from these segments. Vertices $v$ and $u$ are connected by an edge if and only if segments $[l_v, r_v]$ and $[l_u, r_u]$ intersect and neither of it lies fully inside the other one.

For example, pairs $([1, 3], [2, 4])$ and $([5, 10], [3, 7])$ will induce the edges but pairs $([1, 2], [3, 4])$ and $([5, 7], [3, 10])$ will not.

Determine if the resulting graph is a tree or not.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$) — the number of segments.

The $i$-th of the next $n$ lines contain the description of the $i$-th segment — two integers $l_i$ and $r_i$ ($1 \le l_i < r_i \le 2n$).

It is guaranteed that all segments borders are pairwise distinct. 


-----Output-----

Print "YES" if the resulting graph is a tree and "NO" otherwise.


-----Examples-----
Input
6
9 12
2 11
1 3
6 10
5 7
4 8

Output
YES

Input
5
1 3
2 4
5 9
6 8
7 10

Output
NO

Input
5
5 8
3 6
2 9
7 10
1 4

Output
NO



-----Note-----

The graph corresponding to the first example:

[Image]

The graph corresponding to the second example:

[Image]

The graph corresponding to the third example:

[Image]

Difficulty: HARD
Tags: Tree algorithms

Graph algorithms

Data structures

Spanning trees
Skill types: Data structures

Starter code:

Solutions:
import sys

class BIT:

	def __init__(self, n):
		self.n = n
		self.tree = [0] * n

	def _F(self, i):
		return i & i + 1

	def _getSum(self, r):
		result = 0
		while r >= 0:
			result += self.tree[r]
			r = self._F(r) - 1
		return result

	def getSum(self, l, r):
		return self._getSum(r) - self._getSum(l - 1)

	def _H(self, i):
		return i | i + 1

	def add(self, i, value):
		while i < self.n:
			self.tree[i] += value
			i = self._H(i)
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
n = int(input())
segm = [0] * (2 * n + 1)
edge = [0] * (2 * n + 1)
for i in range(n):
	(l, r) = map(int, input().split())
	segm[l] = segm[r] = i
	edge[l] = edge[r] = r
opened = BIT(2 * n + 1)
g = [[] for _ in range(n)]
ctr = 0
for e in range(1, 2 * n + 1):
	r = edge[e]
	if e == r:
		opened.add(e, -1)
	else:
		opened.add(r, 1)
		add = opened.getSum(0, r - 1)
		ctr += add
		if ctr > n - 1:
			print('NO')
			sys.exit()
		for k in range(add):
			L = 0
			R = r - 1
			while L + 1 < R:
				m = L + R >> 1
				if opened.getSum(0, m) > k:
					R = m
				else:
					L = m
			i = segm[e]
			j = segm[R]
			g[i].append(j)
			g[j].append(i)
visited = [False] * n
stack = [0]
while stack:
	v = stack.pop()
	if not visited[v]:
		visited[v] = True
		for to in g[v]:
			stack.append(to)
print('YES' if all(visited) else 'NO')


import sys
input = sys.stdin.readline

def main():
	N = int(input())
	LR = [list(map(int, input().split())) for _ in range(N)]
	A = [None] * (2 * N + 1)
	for (i, (l, r)) in enumerate(LR):
		A[l] = i
		A[r] = i
	graph = [[] for _ in range(N)]
	num_of_edge = 0
	q = []
	for n in range(1, 2 * N + 1):
		p = A[n]
		if LR[p][0] == n:
			q.append(p)
		else:
			tmp = []
			while True:
				np = q.pop()
				if np == p:
					break
				else:
					tmp.append(np)
			while tmp:
				np = tmp.pop()
				q.append(np)
				num_of_edge += 1
				graph[np].append(p)
				graph[p].append(np)
			if num_of_edge > N:
				return False
	if num_of_edge != N - 1:
		return False
	q = [0]
	checked = [False] * N
	checked[0] = True
	while q:
		qq = []
		for p in q:
			for np in graph[p]:
				if not checked[np]:
					checked[np] = True
					qq.append(np)
		q = qq
	for p in range(N):
		if not checked[p]:
			return False
	return True
print('YES' if main() else 'NO')


import sys

class segmTree:

	def __init__(self, size=None, array=None):
		if array is not None:
			size = len(array)
		N = 1
		while N < size:
			N <<= 1
		self.N = N
		self.tree = [0] * (2 * self.N)
		if array is not None:
			for i in range(size):
				self.tree[i + self.N] = array[i]
			self.build()

	def build(self):
		for i in range(self.N - 1, 0, -1):
			self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

	def add(self, i, value=1):
		i += self.N
		while i > 0:
			self.tree[i] += value
			i >>= 1

	def findNonzero(self, l, r):
		N = self.N
		l += N
		r += N
		cand = []
		while l < r:
			if l & 1:
				cand.append(l)
				l += 1
			if r & 1:
				r -= 1
				cand.append(r)
			l >>= 1
			r >>= 1
		nonzeros = []
		while cand:
			i = cand.pop()
			if self.tree[i]:
				if i < N:
					cand.append(i << 1)
					cand.append(i << 1 | 1)
				else:
					nonzeros.append(i - N)
		return nonzeros
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
n = int(input())
segm = [0] * (2 * n + 1)
edge = [0] * (2 * n + 1)
for i in range(n):
	(l, r) = map(int, input().split())
	segm[l] = segm[r] = i
	edge[l] = edge[r] = r
opened = segmTree(size=2 * n + 1)
g = [[] for _ in range(n)]
ctr = 0
for e in range(1, 2 * n + 1):
	r = edge[e]
	if e == r:
		opened.add(e, -1)
	else:
		opened.add(r, 1)
		for R in opened.findNonzero(0, r):
			ctr += 1
			if ctr >= n:
				print('NO')
				sys.exit()
			i = segm[r]
			j = segm[R]
			g[i].append(j)
			g[j].append(i)
visited = [False] * n
stack = [0]
while stack:
	v = stack.pop()
	if not visited[v]:
		visited[v] = True
		for to in g[v]:
			stack.append(to)
print('YES' if all(visited) else 'NO')


import sys
from heapq import heapify, heappush, heappop

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.par = [i for i in range(n + 1)]
		self.rank = [0] * (n + 1)
		self.size = [1] * (n + 1)
		self.tree = [True] * (n + 1)

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			self.tree[x] = False
			return
		if not self.tree[x] or not self.tree[y]:
			self.tree[x] = self.tree[y] = False
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
			self.size[y] += self.size[x]
		else:
			self.par[y] = x
			self.size[x] += self.size[y]
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def is_same(self, x, y):
		return self.find(x) == self.find(y)

	def get_size(self, x=None):
		if x is not None:
			return self.size[self.find(x)]
		else:
			res = set()
			for i in range(self.n + 1):
				res.add(self.find(i))
			return len(res) - 1

	def is_tree(self, x):
		return self.tree[self.find(x)]
N = INT()
segs = [0] * (N * 2 + 1)
for i in range(N):
	(l, r) = MAP()
	segs[l] = i + 1
	segs[r] = -(i + 1)
que = []
edges = []
for (i, a) in enumerate(segs):
	if a > 0:
		heappush(que, (-i, a))
	else:
		a = -a
		tmp = []
		while que:
			(j, b) = heappop(que)
			if a == b:
				break
			tmp.append((j, b))
			edges.append((a, b))
			if len(edges) >= N:
				NO()
				exit()
		for (j, b) in tmp:
			heappush(que, (j, b))
uf = UnionFind(N)
for (a, b) in edges:
	uf.union(a, b)
if uf.get_size() != 1 or not uf.is_tree(1):
	NO()
else:
	YES()


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class BIT_RSQ:

	def __init__(self, n):
		self.n = n
		self.data = [0] * (n + 2)

	def add(self, i, v):
		while i <= self.n:
			self.data[i] += v
			i += i & -i

	def sum(self, i):
		ret = 0
		while i > 0:
			ret += self.data[i]
			i -= i & -i
		return ret

	def query(self, l, r):
		return self.sum(r) - self.sum(l - 1)

	def lowerBound(self, w):
		if w <= 0:
			return 0
		(x, k) = (0, 2 ** self.n.bit_length())
		while k:
			if x + k <= self.n and self.data[x + k] < w:
				w -= self.data[x + k]
				x += k
			k >>= 1
		return x + 1
n = int(input())
edges = [0] * (2 * n)
c = [0] * (2 * n)
BIT = BIT_RSQ(2 * n)
uf = [-1] * n

def root(x):
	if uf[x] < 0:
		return x
	uf[x] = root(uf[x])
	return uf[x]

def unite(x, y):
	(rx, ry) = (root(x), root(y))
	if rx == ry:
		return False
	if uf[rx] > uf[ry]:
		(rx, ry) = (ry, rx)
	uf[rx] += uf[ry]
	uf[ry] = rx
	return True
for i in range(n):
	(a, b) = list(map(int, input().split()))
	(a, b) = (a - 1, b - 1)
	c[a] = c[b] = i
	edges[a] = b
	edges[b] = b
for i in reversed(list(range(2 * n))):
	j = edges[i]
	if j == i:
		BIT.add(j + 1, 1)
	else:
		BIT.add(j + 1, -1)
		cnt = BIT.sum(j + 1)
		while cnt:
			k = BIT.lowerBound(cnt)
			if not unite(c[j], c[k - 1]):
				print('NO')
				return
			cnt -= 1
if sum((i < 0 for i in uf)) == 1:
	print('YES')
else:
	print('NO')


import sys
from array import array
from typing import Dict, List, Tuple, TypeVar, Generic, Sequence, Union

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

class UnionFind(object):
	__slots__ = ['nodes']

	def __init__(self, n: int):
		self.nodes = [-1] * n

	def size(self, x: int) -> int:
		return -self.nodes[self.find(x)]

	def find(self, x: int) -> int:
		if self.nodes[x] < 0:
			return x
		else:
			self.nodes[x] = self.find(self.nodes[x])
			return self.nodes[x]

	def unite(self, x: int, y: int) -> bool:
		(root_x, root_y, nodes) = (self.find(x), self.find(y), self.nodes)
		if root_x != root_y:
			if nodes[root_x] > nodes[root_y]:
				(root_x, root_y) = (root_y, root_x)
			nodes[root_x] += nodes[root_y]
			nodes[root_y] = root_x
		return root_x != root_y

def main():
	from heapq import heappush, heappop
	n = int(input())
	(seg_l, seg_r) = ([0] * n, [0] * n)
	for (i, (l, r)) in enumerate((map(int, input().split()) for _ in range(n))):
		seg_l[i] = l
		seg_r[i] = r
	order = sorted(range(n), key=lambda i: seg_l[i])
	hq: List[Tuple[int, int]] = []
	edge_cnt = 0
	uf = UnionFind(n)
	for i in order:
		while hq and hq[0][0] < seg_l[i]:
			heappop(hq)
		tmp = []
		while hq and hq[0][0] < seg_r[i]:
			uf.unite(i, hq[0][1])
			edge_cnt += 1
			tmp.append(heappop(hq))
			if edge_cnt >= n:
				print('NO')
				exit()
		while tmp:
			heappush(hq, tmp.pop())
		heappush(hq, (seg_r[i], i))
	if edge_cnt == n - 1 and uf.size(0) == n:
		print('YES')
	else:
		print('NO')
main()