TikTok is organizing a grand TikTok event and wants to optimize the content delivery routes for the users.
They have numServers
servers numbered from 1 to numServers
. The servers will be arranged in a sequence as follows: [1, 2, 3, ..., numServers
].
The company has a list of numDisconnectedPairs
pairs of servers that are not directly connected. Any pair not present in this list are directly connected.
A subsegment of the route starting from server start
and ending at server end
is [start
, start
+1, start
+2, ..., end
]. A subsegment of the route is called good when all pairs of servers in that segment are directly connected.
TikTok wants to know how many pairs (start
, end
) there are (1 ≤ start
≤ end
≤ numServers
), such that the subsegment starting from server start
and ending at server end
is good.
Note: Servers can be reused across different subsegments. Each subsegment is considered independently, so a server can be part of multiple “good” subsegments. For example, if a server 3 is part of a “good” subsegment [2, 3, 4], it can still be reused in another “good” subsegment, like [3, 4, 5].
Example 1:
Input: numServers = 4, numDisconnectedPairs = 2, disconnectedPairs = [[1, 2], [2, 3]]
Output: 5
Explanation:Disconnected Pairs:
(1, 2) are not directly connected. (2, 3) are not directly connected.
The good subsegments are:
- [1]: Only one server, so it’s automatically “good”.
- [2]: Only one server, so it’s automatically “good”.
- [3]: Only one server, so it’s automatically “good”.
- [4]: Only one server, so it’s automatically “good”.
- [3, 4]: Both servers 3 and 4 are directly connected.
- 2 ≤
numServers
≤ 10^5 - 0 ≤
numDisconnectedPairs
≤ 10^5 - 1 ≤
numDisconnectedPairs
count ≤ 10^5 - 1 ≤ xi, yi ≤
numDisconnectedPairs
. - xi != yi

input:
output: