1187. Maximum Length of Pair Chain

Given pairs [a, b] with a < b, a pair [c, d] can follow [a, b] only if b < c. Return the length of the longest chain that can be formed (pairs may be used in any order). The input is JSON {pairs}.

Input: JSON {pairs}.

Output: Integer — the length of the longest chain.

Examples

Input: {"pairs":[[1,2],[2,3],[3,4]]}
Output: 2
Explanation: [1,2] -> [3,4].

Input: {"pairs":[[1,2],[7,8],[4,5]]}
Output: 3
Explanation: All three chain.

Input: {"pairs":[[1,5]]}
Output: 1
Explanation: Single pair.

Constraints

• 1<=n<=1000

Asked by