Contiguous Photo Segmentation

Farmer John wants to take photos of his n dairy cows, which are arranged in a line and numbered from 1 to n. Each photo can capture a contiguous block of cows. Every cow must appear in at least one photo. However, there are k pairs of cows that do not get along; these pairs refuse to appear together in the same photo.

For example, if a forbidden pair is given as \((i,j)\) with \(i<j\), then any photo (i.e. contiguous interval) that includes both cow \(i\) and cow \(j\) is invalid. Your task is to determine the minimum number of photos needed such that every cow is covered by at least one valid photo.

Formal Statement:

You are given an integer n and an integer k. Then k lines follow, each containing two integers \(u\) and \(v\) (with \(1 \le u < v \le n\)), indicating that cows \(u\) and \(v\) cannot be captured together in a single photo. Find the minimum number of contiguous intervals (photos) needed to cover all cows such that no interval contains both endpoints of any forbidden pair.

Hint: Notice that a single cow can always be photographed by itself. In a valid contiguous segment (photo), no forbidden pair exists. Thus, the problem reduces to partitioning the sequence of cows into the fewest possible contiguous conflict‐free segments.

inputFormat

The first line contains two integers \(n\) and \(k\) where \(n\) is the number of cows and \(k\) is the number of forbidden pairs.

Each of the next k lines contains two integers \(u\) and \(v\) (with \(1 \le u < v \le n\)), representing a pair of cows that refuse to appear together in one photo.

outputFormat

Output a single integer representing the minimum number of photos required.

sample

5 2
1 3
2 5

2