Plain Constructive Problem

Interview

Time limit1sMemory limit1024 MB

Summary

Given N and M intervals, build a sequence of length N with the largest K such that every interval contains all values 1 to K.

Level: Easy3 of 10
Topics: Implementation, Math
Solved: No attempts yet

Problem

Given an integer $N$ and $M$ integer pairs $(L\_1, R\_1), (L\_2, R\_2), \cdots (L\_M, R\_M)$ , find the sequence $X$ that maximizes $K$ under the following conditions.

$X$ consists of $N$ positive integers, each at most $K$ .
For every pair $(L\_i, R\_i)$ , the subarray $X\_{L\_i}, X\_{L\_i+1}, \cdots, X\_{R\_i-1}, X\_{R\_i}$ must contain every positive integer at most $K$ .

Input

The first line contains two integers $N$ and $M$ .

The next $M$ lines each contain two integers $L\_i$ and $R\_i$ . $(1 \le i \le N)$

Output

For a sequence $X$ that satisfies the conditions, print the $N$ integers $X\_1, X\_2, \cdots, X\_N$ .

If multiple answers exist, print any of them.

Constraints

$3 \leq N \leq 1000$
$1 \leq M \leq 1000$
$1 \leq L\_i \leq R\_i \leq N$

Examples2

Example 1
Input
```
3 1
1 3
```
Expected output
```
1 2 3
```
Example 2
Input
```
3 2
1 2
2 3
```
Expected output
```
1 2 1
```