Approach

Let Parsa's interval be [l, r]. It must overlap every given interval [l_i, r_i].

For overlap with all intervals:

• r must be at least max_start = max(l_i), otherwise it misses the interval that starts latest.
• l must be at most min_end = min(r_i), otherwise it misses the interval that ends earliest.

So valid choices are all intervals [l, r] (with 1 <= l <= r <= m) except:

1. Intervals with l > min_end.
2. Intervals with r < max_start.

Count total intervals in [1, m]: total = m * (m + 1) // 2.

Count invalid type 1: type1 = (m - min_end) * (m - min_end + 1) // 2.

Count invalid type 2: type2 = (max_start - 1) * max_start // 2.

These two invalid sets can overlap, so add back the intersection once (inclusion-exclusion):

overlap_dist = max(0, max_start - min_end - 1) overlap = overlap_dist * (overlap_dist + 1) // 2.

Final answer: total - type1 - type2 + overlap.

Time complexity is O(n).

Solution (Python)

n, m = list(map(int, input().split()))
points = [list(map(int, input().split())) for _ in range(n-1)]

assert 2 <= n <= 200000
assert 1 <= m <= 200000
assert all(1 <= l <= r <= m for l, r in points)

min_end = min(p[1] for p in points)
max_start = max(p[0] for p in points)
overlap_dist = max(0, max_start - min_end - 1)
total = m * (m + 1) // 2
type1 = (m - min_end) * (m - min_end + 1) // 2
type2 = (max_start - 1) * max_start // 2
overlap = overlap_dist * (overlap_dist + 1) // 2
print(total - type1 - type2 + overlap)