평범한 구성적 문제

면접 대비

시간 제한1초메모리 제한1024 MB

요약

길이 N의 수열과 M개의 구간이 주어질 때, 모든 구간에 1부터 K까지의 수가 모두 들어가도록 K를 최대로 하는 수열을 만듭니다.

문제

정수 $N$ 과 $M$ 개의 정수 쌍 $(L\_1, R\_1), (L\_2, R\_2), \cdots (L\_M, R\_M)$ 이 주어진다. 아래 조건을 만족하면서 값 $K$ 를 최대화하는 수열 $X$ 를 찾아야 한다.

$X$ 는 $K$ 이하의 양의 정수 $N$ 개로 구성되어 있다.
모든 정수 쌍 $(L\_i, R\_i)$ 에 대해, $X\_{L\_i}, X\_{L\_i+1}, \cdots, X\_{R\_i-1}, X\_{R\_i}$ 는 $K$ 이하의 양의 정수를 모두 포함해야 한다.

첫 번째 줄에 정수 $N$ 과 $M$ 이 주어진다.

$i + 1$ 번째 줄에 두 정수 $L\_i$ 와 $R\_i$ 가 주어진다. $(1 \le i \le N)$

조건을 만족하는 수열 $X$ 에 대해 $N$ 개의 정수 $X\_1, X\_2, \cdots, X\_N$ 을 출력한다.

답이 여러 개 존재한다면 아무거나 출력해도 된다.