문제
정수 $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$ 이하의 양의 정수를 모두 포함해야 한다.
출력
조건을 만족하는 수열 $X$에 대해 $N$개의 정수 $X_1, X_2, \cdots, X_N$을 출력한다.
답이 여러 개 존재한다면 아무거나 출력해도 상관없다.
제한
- 3ドル \leq N \leq 1000$
- 1ドル \leq M \leq 1000$
- 1ドル \leq L_i \leq R_i \leq N$
$K$가 3보다 큰 수열은 존재하지 않음을 증명할 수 있다.
$K$가 2보다 큰 수열은 존재하지 않음을 증명할 수 있다.
W3sicHJvYmxlbV9pZCI6IjI3OTg2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkM2M5XHViYzk0XHVkNTVjIFx1YWQ2Y1x1YzEzMVx1YzgwMSBcdWJiMzhcdWM4MWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzgxNVx1YzIxOCAkTiRcdWFjZmMgJE0kXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBcdWMzMGQgJChMXzEsIFJfMSksIChMXzIsIFJfMiksIFxcY2RvdHMgKExfTSwgUl9NKSAkXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHVjODFjIFx1YzU0NFx1Yjc5OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViYTc0XHVjMTFjIFx1YWMxMiAkSyRcdWI5N2MgXHVjZDVjXHViMzAwXHVkNjU0XHVjMmRjXHVkMGE0XHViMjk0IFx1YzIxOFx1YzVmNCAkWCRcdWI5N2MgXHVjYzNlXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kWCRcdWIyOTQgJEskIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4ICROJFx1YWMxY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgXHVjODE1XHVjMjE4IFx1YzMwZCAkKExfaSwgUl9pKSRcdWM1ZDAgXHViMzAwXHVkNTc0LCAkWF97TF9pfSwgWF97TF9pKzF9LCBcXGNkb3RzLCBYX3tSX2ktMX0sIFhfe1JfaX0kXHVjNzQwICRLJCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjk3YyA8c3Ryb25nPlx1YmFhOFx1YjQ1MDxcL3N0cm9uZz4gXHVkM2VjXHVkNTY4XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4ICROJFx1YWNmYyAkTSRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD4kaSArIDEkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVjODE1XHVjMjE4ICRMX2kkXHVjNjQwICRSX2kkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxIFxcbGUgaSBcXGxlIE4pJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjMjE4XHVjNWY0ICRYJFx1YzVkMCBcdWIzMDBcdWQ1NzQgJE4kXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCAkWF8xLCBYXzIsIFxcY2RvdHMsIFhfTiRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZjVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTRcdWJhNzQgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YjNjNCBcdWMwYzFcdWFkMDBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQzIFxcbGVxIE4gXFxsZXEgMTAwMCQ8XC9saT5cclxuXHQ8bGk+JDEgXFxsZXEgTSBcXGxlcSAxMDAwJDxcL2xpPlxyXG5cdDxsaT4kMSBcXGxlcSBMX2kgXFxsZXEgUl9pIFxcbGVxIE4kPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+JEskXHVhYzAwIDNcdWJjZjRcdWIyZTQgXHVkMDcwIFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzRjXHVjNzQ0IFx1Yzk5ZFx1YmE4NVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzIiOiI8cD4kSyRcdWFjMDAgMlx1YmNmNFx1YjJlNCBcdWQwNzAgXHVjMjE4XHVjNWY0XHVjNzQwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NGNcdWM3NDQgXHVjOTlkXHViYTg1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjc5ODYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBbm90aGVyIENvbnN0cnVjdGl2ZSBQcm9ibGVtIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIGdpdmVuIGFuIGludGVnZXIgJE4kIGFuZCAkTSQgcGFpcnMgb2YgaW50ZWdlcnMgJChMXzEsIFJfMSksIChMXzIsIFJfMiksIFxcY2RvdHMgKExfTSwgUl9NKSAkLiBOb3cgeW91IHdhbnQgdG8gZmluZCBhbiBhcnJheSAkWCQgdGhhdCBzYXRpc2ZpZXMgdGhlIGJlbG93IGNvbmRpdGlvbnMgYW5kIG1heGltaXplcyB0aGUgdmFsdWUgJEskLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiRYJCBjb25zaXN0cyBvZiAkTiQgcG9zaXRpdmUgaW50ZWdlcnMuIEVhY2ggaW50ZWdlciBpcyBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gJEskLjxcL2xpPlxyXG5cdDxsaT5Gb3IgZXZlcnkgcGFpciAkKExfaSwgUl9pKSQsICRYX3tMX2l9LCBYX3tMX2krMX0sIFxcY2RvdHMsIFhfe1JfaS0xfSwgWF97Ul9pfSQgc2hvdWxkIGluY2x1ZGUgZXZlcnkgcG9zaXRpdmUgaW50ZWdlcnMgbGVzcyB0aGFuIG9yIGVxdWFsIHRvICRLJC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzICROJCBhbmQgJE0kLjxcL3A+XHJcblxyXG48cD5UaGUgJGkrMSQtdGggbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgJExfaSQgYW5kICRSX2kkLiAkKDEgXFxsZSBpIFxcbGUgTikkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgJE4kIGludGVnZXJzICRYXzEsIFhfMiwgXFxjZG90cywgWF9OJCB3aGVyZSAkWCQgaXMgYW4gYXJyYXkgd2hpY2ggc2F0aXNmaWVzIGFsbCBjb25kaXRpb25zLjxcL3A+XHJcblxyXG48cD5JZiB0aGVyZSBhcmUgbXVsdGlwbGUgc29sdXRpb25zLCBwcmludCBhbnkgb2YgdGhlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQzIFxcbGVxIE4gXFxsZXEgMTAwMCQ8XC9saT5cclxuXHQ8bGk+JDEgXFxsZXEgTSBcXGxlcSAxMDAwJDxcL2xpPlxyXG5cdDxsaT4kMSBcXGxlcSBMX2kgXFxsZXEgUl9pIFxcbGVxIE4kPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+SXQgY2FuIGJlIHByb3ZlZCB0aGF0IG5vIGFycmF5IG1ha2VzICRLJCBncmVhdGVyIHRoYW4gJDMkLjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzIiOiI8cD5JdCBjYW4gYmUgcHJvdmVkIHRoYXQgbm8gYXJyYXkgbWFrZXMgJEskIGdyZWF0ZXImbmJzcDt0aGFuICQyJC48XC9wPlxyXG4ifV0=