Let $ f(x) $ denote the number of segments containing integer point $ x \in [1, m] $.
Given:
- There are $ n $ segments $ [l_i, r_i] \subseteq [1, m] $, with $ 1 \leq l_i \leq r_i \leq m $.
- **No integer point belongs to all $ n $ segments**, i.e., $ \bigcap_{i=1}^n [l_i, r_i] = \emptyset $.
- Sasha learns $ f(x) $ for some subset of points $ x \in [1, m] $, without knowing $ n $ or the segments.
- Sasha wants to determine whether **there exists** a point contained in **all** segments (i.e., whether Teodor is lying).
- Teodor claims **no** such point exists.
- Sasha **cannot be sure** Teodor is telling the truth if **there exists** some alternative set of segments (with possibly different $ n' $) that produces the **same** $ f(x) $ values on the queried points, but **does have** a common intersection point.
We are to find the **maximum size** of a set $ S = \{ (x_i, f(x_i)) \} $, with all $ x_i $ distinct in $ [1, m] $, such that **it is still possible** that some point lies in all segments — i.e., Sasha **cannot rule out** that Teodor is lying.
---
### Key Insight:
The function $ f(x) $ is the **coverage count** at point $ x $. It is a piecewise constant function that changes only at segment endpoints.
The condition that **no point belongs to all segments** means:
$$
\min_{x \in [1,m]} f(x) < n
$$
But Sasha **does not know $ n $**. So he only sees the values $ f(x) $ at queried points.
Sasha **cannot be sure** Teodor is telling the truth if there exists **some** integer $ n' \geq 1 $ and some collection of $ n' $ segments such that:
1. The coverage function $ f'(x) $ matches $ f(x) $ on all queried points $ x_i $,
2. And $ \min_{x \in [1,m]} f'(x) = n' $ — meaning **every** queried point has coverage $ \leq n' $, but **some unqueried point** has coverage $ n' $, and **all segments contain that point**.
In other words:
Sasha **cannot distinguish** the true configuration from a **fake** one where **all segments share a common point**, and the coverage function matches on the queried points.
So we want the **largest** set of points $ \{x_1, \dots, x_k\} $ with known $ f(x_i) $, such that **there exists** a possible global coverage function $ f' $ (induced by some set of segments) where:
- $ f'(x_i) = f(x_i) $ for all queried $ x_i $,
- and $ \min_{x \in [1,m]} f'(x) = \max_{x \in [1,m]} f'(x) = n' $ — i.e., **all** points have the same coverage $ n' $, meaning **every point is in all $ n' $ segments**.
Wait — that would mean the entire interval is covered by $ n' $ identical segments. But that’s not necessary.
Actually, the **minimal** coverage over all points must equal the **maximum** coverage for there to be a common intersection. Because:
> A set of intervals has a common intersection **iff** the point with the **minimum** coverage is covered by **all** intervals — i.e., $ \min_x f(x) = n $.
So if Sasha sees a set of values $ f(x_i) $, and **for every possible extension** of $ f $ to the entire $ [1,m] $, it is possible that $ \min_x f(x) = \max_x f(x) $, then he cannot be sure.
But we want the **maximum** size of a set of points $ \{x_i\} $ such that **there exists** a valid extension where $ \min f(x) = \max f(x) $ — i.e., **all** points have the same coverage.
That is:
> What is the largest set of points $ S \subseteq [1,m] $, with values $ f(x_i) $, such that **there exists** a constant function $ f'(x) = c $ for all $ x \in [1,m] $, and $ f'(x_i) = f(x_i) $ for all $ x_i \in S $?
But $ f'(x) = c $ for all $ x $ means that **every integer point in $ [1,m] $** is covered by exactly $ c $ segments — which is only possible if all segments are the **full interval** $ [1,m] $, and there are $ c $ of them.
So:
The only way to have $ f'(x) = c $ for all $ x \in [1,m] $ is if **all segments are $ [1,m] $**.
Thus, the only constant coverage function possible is $ f(x) = c $ for all $ x \in [1,m] $, achieved by $ c $ copies of $ [1,m] $.
Therefore, Sasha **cannot be sure** Teodor is telling the truth **if and only if** the values $ f(x_i) $ he has seen are **all equal** to some constant $ c $, and **it is possible** that all segments are $ [1,m] $, i.e., $ f(x) = c $ everywhere.
So:
- If **all queried points** have the same coverage value $ c $, then Sasha **cannot rule out** that Teodor has drawn $ c $ copies of $ [1,m] $ — in which case **every point** is in all segments — meaning Teodor is lying.
- But if **any two queried points** have **different** coverage values, then it is **impossible** that all segments share a common point — because if they did, all points would have the same coverage $ n $.
Therefore:
> Sasha **can be sure** Teodor is telling the truth **iff** there exist **two queried points** $ x_1, x_2 $ with $ f(x_1) \ne f(x_2) $.
> Sasha **cannot be sure** if **all queried points** have the same coverage value.
So the **largest** set of points $ S $ such that Sasha **cannot be sure** is the **largest** subset of $ [1,m] $ where **all points have the same coverage**.
Thus, the answer is:
$$
\boxed{ \max_{c} \left| \left\{ x \in [1, m] : f(x) = c \right\} \right| }
$$
That is, the **maximum number of integer points in $ [1, m] $** that have the **same** coverage count.
---
### Algorithm:
1. Compute $ f(x) $ for all $ x \in [1, m] $ using a difference array (or sweep line).
2. Count frequency of each coverage value $ c $.
3. Return the maximum frequency.
---
### Example:
**Input:**
n=2, m=4
Segments: [1,2], [3,4]
Then:
f(1)=1, f(2)=1, f(3)=1, f(4)=1 → all coverage = 1 → max frequency = 4 → output 4.
**Another:**
n=3, m=6
Segments: [1,3], [2,4], [5,6]
f(1)=1, f(2)=2, f(3)=2, f(4)=1, f(5)=1, f(6)=1
Coverage counts:
1: x=1,4,5,6 → count=4
2: x=2,3 → count=2
Max = 4 → output 4.
But wait — the problem says in the **second example**, Sasha can ask 5 points and still not be sure, but not all 6.
So let’s check the second example.
The problem says:
> In second example Sasha can ask about 5 points e.g. 1,2,3,5,6, still not being sure if Teodor haven't lied to him. But once he knows information about all points in [1;6] segment, Sasha can be sure that Teodor haven't lied to him.
So if the true coverage is:
x: 1 2 3 4 5 6
f: 1 2 2 1 1 1
Sasha queries 5 points: say 1,2,3,5,6 → values: 1,2,2,1,1 → he sees values 1 and 2 → so he **can** be sure? But the problem says he **cannot** be sure.
Contradiction?
Wait — re-read:
> Sasha can ask about 5 points e.g. 1,2,3,5,6, still not being sure...
But he sees f(1)=1, f(2)=2, f(3)=2, f(5)=1, f(6)=1 — so he sees both 1 and 2.
Why can't he be sure?
Because he doesn’t know n. He sees max coverage = 2, min = 1.
He thinks: maybe there are 2 segments, and they are both [2,3] — then f(2)=f(3)=2, others=0 — but he sees f(1)=1, so that’s impossible.
Wait — maybe he considers: what if the true set of segments is **not** the given one, but a different one that produces the same coverage on queried points, but has a common intersection?
Can he construct a set of segments with **common intersection**, that matches the coverage on {1,2,3,5,6}?
Suppose he assumes there is a point common to all segments — say point 4.
He sees f(1)=1, f(2)=2, f(3)=2, f(5)=1, f(6)=1.
Can he find segments such that:
- All segments contain point 4? → so all segments must cover 4.
- Coverage at 1:1, 2:2, 3:2, 5:1, 6:1.
Suppose there are 2 segments:
Segment A: [2,5] → covers 2,3,4,5
Segment B: [1,3] → covers 1,2,3
Then coverage:
1:1, 2:2, 3:2, 4:1, 5:1, 6:0 → but f(6)=1 is observed → contradiction.
Another try: 3 segments.
Suppose all segments contain 4.
Let’s try:
- [1,4] → covers 1,2,3,4
- [2,5] → covers 2,3,4,5
- [4,6] → covers 4,5,6
Then coverage:
1:1, 2:2, 3:2, 4:3, 5:2, 6:1
But we need f(5)=1, f(6)=1 — here f(5)=2 — too high.
Try:
- [1,3]
- [3,5]
- [5,6]
But then 4 is only covered by [3,5] — so if we require **all segments contain 4**, then [1,3] cannot exist.
So to have all segments contain 4, every segment must satisfy $ l_i \leq 4 \leq r_i $.
So possible segments:
We need to cover:
x=1: count=1 → only one segment covers 1 → so one segment must start at 1 and extend to ≥4
x=2: count=2 → two segments cover 2 → so two segments must have l_i ≤2
x=3: count=2 → two segments cover 3
x=5: count=1 → one segment covers 5 → so one segment must end at 5 or later, but only one
x=6: count=1 → one segment ends at 6
So let’s try:
Segment 1: [1,6] → covers 1,2,3,4,5,6
Segment 2: [2,5] → covers 2,3,4,5
Segment 3: [4,6] → covers 4,5,6
Coverage:
1:1, 2:2, 3:2, 4:3, 5:3, 6:2 → doesn’t match.
We need f(5)=1, f(6)=1 — so only one segment covers 5 and 6.
So only one segment can extend to 6. But if all segments contain 4, then that segment must be [a,6] with a≤4.
To have f(5)=1, only one segment can cover 5 → so only one segment has r_i ≥5.
Similarly, f(6)=1 → only one segment has r_i ≥6 → so only one segment ends at 6 or beyond.
So the only segment that can cover 5 or 6 is one segment: say [a,6], a≤4.
Then f(5)=1, f(6)=1 → good.
Now f(1)=1 → only one segment covers 1 → so only one segment has l_i ≤1 → so one segment must be [1,6].
Then f(2)=2 → two segments cover 2 → one is [1,6], so need one more segment covering 2 → say [2,4]
f(3)=2 → [1,6] and [2,4] cover 3 → good
f(4)=? → [1,6] and [2,4] → so f(4)=2
But we didn’t query 4! So we don’t care what f(4) is.
So the coverage we have:
x: 1 2 3 5 6
f: 1 2 2 1 1
Segments:
- [1,6]
- [2,4]
All segments contain 4?
[1,6] → yes
[2,4] → yes → so common point 4 exists!
And coverage on queried points matches.
So even though the true configuration has no common point, **there exists another configuration** with common point 4 that matches the observed coverage on {1,2,3,5,6}.
Thus, Sasha **cannot be sure**.
But if he queries **all 6 points**, then he sees f(4)=2, and the maximum coverage is 2, but min is 1 → so min < max → so **no point** can be in all segments → because if all segments contained some point x, then f(x) = n, and for any other point y, f(y) ≤ n, but if f(y) < n, then y is not in all segments → contradiction unless f(y)=n everywhere.
But here f(1)=1, f(2)=2 → so if n=2, then f(1)=1 < 2 → so point 1 is not in all segments → so no common point.
So if **all** points are queried, and min f(x) < max f(x), then Sasha knows: **no point is in all segments**.
So the condition for **Sasha being unsure** is:
There exists **some** constant c, and **some** assignment of segments such that:
- All segments contain a common point (say x0),
- The coverage function f’ on the queried points matches the true f on those points,
- And f’(x0) = n' = max coverage.
And this is possible **iff** the queried points do **not** include any point with coverage strictly less than the maximum coverage seen.
In other words:
Sasha is unsure if the **set of queried points** does **not** include a point with **minimum** coverage.
Wait — no.
Actually, from above:
Sasha is unsure if **there exists** a configuration with a common intersection that matches the observed coverage on queried points.
That configuration requires that **all segments contain some point x0**, so **every queried point** must be covered by **at most** n' segments, and **x0** must be covered by n' segments.
But if **all queried points** have coverage **equal to the maximum** observed value, then it’s possible that x0 is unqueried, and all segments contain x0, and the coverage at queried points is less than or equal to n', but we only see the max.
Wait — no.
Let’s define:
Let M = max{ f(x_i) | queried x_i }
If **all** queried points have f(x_i) = M, then it is possible that the true coverage everywhere is M (all segments are [1,m]), or that the coverage is M at queried points, and higher at unqueried points — but that’s impossible because coverage can’t be higher than n, and if a point has coverage > M, then M is not the max.
Actually, coverage is determined by the segments — so if a point x0 has coverage c, and all queried points have coverage ≤ c, then if c = M, and x0 is unqueried, then it’s possible that x0 has coverage M, and all segments contain x0.
But if **some** queried point has coverage < M, then since all segments containing x0 must cover that point, then f(x) ≥ n for all x — contradiction, because we have f(x) < M = n.
So:
> Sasha **can be sure** Teodor is truthful **iff** there exists a queried point x with f(x) < M, where M = max{ f(x_i) }.
> Sasha **cannot be sure** if **all** queried points have f(x_i) = M.
Therefore, the largest set of points where Sasha **cannot be sure** is the largest subset of [1,m] where **all points have the same coverage value**, and that value is the **global maximum** coverage.
Wait — not necessarily the global maximum.
Actually, the condition is:
Sasha is unsure if **there exists** a value c such that **all queried points have coverage c**, and **c is achievable as the coverage of a common intersection point** in some configuration.
But if all queried points have coverage c, then Sasha can assume:
- There are c segments, all equal to [1,m] → then every point has coverage c → so common intersection exists → Teodor is lying.
So **any** set of points where all have the same coverage c allows this fake explanation.
So the **maximum** size of such a set is the **maximum number of points** that have the **same coverage value**, regardless of what that value is.
Because if k points all have coverage c, then Sasha cannot rule out that the true picture is c copies of [1,m], which would have coverage c everywhere — so common intersection exists.
Therefore, the answer is:
> The **maximum frequency** of any coverage value over all points in [1,m].
---
### Final Answer:
Compute the coverage function $ f(x) $ for $ x = 1 $ to $ m $ using a difference array.
Count frequency of each coverage value.
Output the **maximum frequency**.
```python
n, m = map(int, input().split())
diff = [0] * (m + 2)
for _ in range(n):
l, r = map(int, input().split())
diff[l] += 1
diff[r + 1] -= 1
f = [0] * (m + 1)
cur = 0
for i in range(1, m + 1):
cur += diff[i]
f[i] = cur
from collections import Counter
freq = Counter(f[1:])
print(max(freq.values()))
```