시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB20211109.434%

문제

정점 $N$개, 간선 $M$개로 이루어진 단순 무방향 그래프 $G=(V,E)$가 주어진다. 그래프의 정점은 $1$ 이상 $N$ 이하의 번호를 가지며, 간선 역시 $1$ 이상 $M$ 이하의 번호를 가진다. 이때 다음 조건에 맞는 $\{1,2,\cdots ,N\}$의 순열 $\pi$를 찾자.

  • $1<i\le N$인 $i$에 대해 $1\le j<i$, $\{\pi_i,\pi_j\}\in E$인 $j$가 존재한다.
  • $1\le i<N$인 $i$에 대해 $i<j\le N$, $\{\pi_i,\pi_j\}\in E$인 $j$가 존재한다.

입력

첫째 줄에 정점의 개수 $N$, 간선의 개수 $M$이 공백으로 구분되어 주어진다.

둘째 줄부터 $M$개의 줄에 걸쳐 $i+1$번 줄에 $i$번 간선의 양 끝점 $u_i$, $v_i$가 공백으로 구분되어 주어진다.

출력

조건에 맞는 순열이 존재한다면 그러한 순열을 출력한다. 조건에 맞는 순열이 여러 가지라면 어떤 것을 출력해도 상관없다.

조건에 맞는 순열이 존재하지 않는다면 -1을 출력한다.

제한

  • $2\le N\le 10^5$
  • $1\le M\le 10^5$
  • $1\le u_i,v_i\le N$
  • $u_i\ne v_i$
  • $1\le i<j\le M$인 $i$, $j$에 대해서 $\{u_i,v_i\}\ne\{u_j,v_j\}$이다.
  • 주어지는 그래프는 연결되어 있다.

서브태스크

번호배점제한
110

$N, M \le 10$

230

$N, M \le 10^3$, 임의의 서로 다른 세 정점 $u$, $v$, $w$에 대해, 점 $u$에서 점 $v$를 거치지 않고 점 $w$로 이동하는 경로가 존재한다.

310

$N, M \le 10^3$

450

추가 제한 조건이 없다.

예제 입력 1

4 4
1 2
2 3
3 4
4 2

예제 출력 1

1 2 4 3

예제 입력 2

7 10
2 1
3 1
3 2
4 1
4 3
5 3
5 4
6 3
7 5
7 6

예제 출력 2

1 4 5 7 6 3 2

예제 입력 3

7 9
2 1
3 1
3 2
4 3
5 3
5 4
6 4
6 5
7 6

예제 출력 3

1 2 3 5 4 6 7

예제 입력 4

4 3
1 4
2 4
3 4

예제 출력 4

-1
W3sicHJvYmxlbV9pZCI6IjMxMDY5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMjFjXHVjNWY0IFx1YWRmOFx1Yjc5OFx1ZDUwNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjODE1XHVjODEwICROJFx1YWMxYywgXHVhYzA0XHVjMTIwICRNJFx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViMmU4XHVjMjFjIFx1YmIzNFx1YmMyOVx1ZDVhNSBcdWFkZjhcdWI3OThcdWQ1MDQgJEc9KFYsRSkkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YzgxNVx1YzgxMFx1Yzc0MCAkMSQgXHVjNzc0XHVjMGMxICROJCBcdWM3NzRcdWQ1NThcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YWMwMFx1YzljMFx1YmE3MCwgXHVhYzA0XHVjMTIwIFx1YzVlZFx1YzJkYyAkMSQgXHVjNzc0XHVjMGMxICRNJCBcdWM3NzRcdWQ1NThcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YWMwMFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNTRjIFx1YjJlNFx1Yzc0YyBcdWM4NzBcdWFjNzRcdWM1ZDAgXHViOWRlXHViMjk0ICRcXHsxLDIsXFxjZG90cyAsTlxcfSRcdWM3NTggXHVjMjFjXHVjNWY0ICRcXHBpJFx1Yjk3YyBcdWNjM2VcdWM3OTAuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JDEmbHQ7aVxcbGUgTiRcdWM3NzggJGkkXHVjNWQwIFx1YjMwMFx1ZDU3NCAkMVxcbGUgaiZsdDtpJCwgJFxce1xccGlfaSxcXHBpX2pcXH1cXGluIEUkXHVjNzc4ICRqJFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiQxXFxsZSBpJmx0O04kXHVjNzc4ICRpJFx1YzVkMCBcdWIzMDBcdWQ1NzQgJGkmbHQ7alxcbGUgTiQsICRcXHtcXHBpX2ksXFxwaV9qXFx9XFxpbiBFJFx1Yzc3OCAkaiRcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggJE4kLCBcdWFjMDRcdWMxMjBcdWM3NTggXHVhYzFjXHVjMjE4ICRNJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCAkTSRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCAkaSsxJFx1YmM4OCBcdWM5MDRcdWM1ZDAgJGkkXHViYzg4IFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWM1OTEgXHViMDVkXHVjODEwICR1X2kkLCAkdl9pJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4NzBcdWFjNzRcdWM1ZDAgXHViOWRlXHViMjk0IFx1YzIxY1x1YzVmNFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTRcdWJhNzQgXHVhZGY4XHViN2VjXHVkNTVjIFx1YzIxY1x1YzVmNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzg3MFx1YWM3NFx1YzVkMCBcdWI5ZGVcdWIyOTQgXHVjMjFjXHVjNWY0XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWI3N2NcdWJhNzQgXHVjNWI0XHViNWE0IFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NzRcdWIzYzQgXHVjMGMxXHVhZDAwXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4NzBcdWFjNzRcdWM1ZDAgXHViOWRlXHViMjk0IFx1YzIxY1x1YzVmNFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHViYTc0IDxjb2RlPi0xPFwvY29kZT5cdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMlxcbGUgTlxcbGUgMTBeNSQ8XC9saT5cclxuXHQ8bGk+JDFcXGxlIE1cXGxlIDEwXjUkPFwvbGk+XHJcblx0PGxpPiQxXFxsZSB1X2ksdl9pXFxsZSBOJDxcL2xpPlxyXG5cdDxsaT4kdV9pXFxuZSB2X2kkPFwvbGk+XHJcblx0PGxpPiQxXFxsZSBpJmx0O2pcXGxlIE0kXHVjNzc4ICRpJCwgJGokXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyAkXFx7dV9pLHZfaVxcfVxcbmVcXHt1X2osdl9qXFx9JFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YjI5NCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kTiwgTSBcXGxlIDEwJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JE4sIE0gXFxsZSAxMF4zJCwgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMTM4IFx1YzgxNVx1YzgxMCAkdSQsICR2JCwgJHckXHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVjODEwICR1JFx1YzVkMFx1YzExYyBcdWM4MTAgJHYkXHViOTdjIFx1YWM3MFx1Y2U1OFx1YzljMCBcdWM1NGFcdWFjZTAgXHVjODEwICR3JFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHVhY2JkXHViODVjXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPiROLCBNIFxcbGUgMTBeMyQ8XC9wPlxyXG4iLCJzdWJ0YXNrNCI6IjxwPlx1Y2Q5NFx1YWMwMCBcdWM4MWNcdWQ1NWMgXHVjODcwXHVhYzc0XHVjNzc0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIzMTA2OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdyYXBoIGFuZCBwZXJtdXRhdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgaXMgYW4gdW5kaXJlY3RlZCwgdW53ZWlnaHRlZCBzaW1wbGUgZ3JhcGggJEc9KFYsRSkkIHdpdGggJE4kIHZlcnRpY2VzIGFuZCAkTSQgZWRnZXMuIFRoZSB2ZXJ0aWNlcyBhcmUgbnVtYmVyZWQgZnJvbSAkMSQgdG8gJE4kLCBhbmQgdGhlIGVkZ2VzIGFyZSBhbHNvIG51bWJlcmVkIGZyb20gJDEkIHRvICRNJC4gWW91IHNob3VsZCBmaW5kIGEgcGVybXV0YXRpb24gJFxccGkkIG9mICRcXHsxLDIsXFxjZG90cyAsTlxcfSQgd2hpY2ggc2F0aXNmaWVzIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9ucy48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5Gb3IgYWxsIGludGVnZXIgJGkkIHN1Y2ggdGhhdCAkMSZsdDtpXFxsZSBOJCwgdGhlcmUgZXhpc3RzIGFuIGludGVnZXIgJGokIHN1Y2ggdGhhdCAkMVxcbGUgaiZsdDtpJCBhbmQgJFxce1xccGlfaSxcXHBpX2pcXH1cXGluIEUkLjxcL2xpPlxyXG5cdDxsaT5Gb3IgYWxsIGludGVnZXIgJGkkIHN1Y2ggdGhhdCAkMVxcbGUgaSZsdDtOJCwgdGhlcmUgZXhpc3RzIGFuIGludGVnZXIgJGokIHN1Y2ggdGhhdCAkaSZsdDtqXFxsZSBOJCBhbmQgJFxce1xccGlfaSxcXHBpX2pcXH1cXGluIEUkLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgJE4kIGFuZCAkTSQgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIG5vZGVzIGFuZCBlZGdlcyBpbiB0aGUgZ3JhcGguPFwvcD5cclxuXHJcbjxwPlRoZW4sICRNJCBsaW5lcyBmb2xsb3csIHN0YXJ0aW5nIGZyb20gdGhlIHNlY29uZCBsaW5lLiBUaGUgJGkrMSQtdGggbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgJHVfaSQgYW5kICR2X2kkLCB0aGUgaW5kZXggb2YgdHdvIG5vZGVzIGNvbm5lY3RlZCBieSB0aGUgJGkkLXRoIGVkZ2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SWYgdGhlcmUgYSBwZXJtdXRhdGlvbiBzYXRpc2Z5aW5nIHRoZSByZXF1aXJlbWVudHMgZXhpc3RzLCBwcmludCB0aGUgcGVybXV0YXRpb24uIElmIHRoZXJlIGFyZSBtdWx0aXBsZSBhbnN3ZXJzLCB5b3UgbWF5IHByaW50IGFueSBvZiB0aGVtLjxcL3A+XHJcblxyXG48cD5JZiBubyBwZXJtdXRhdGlvbnMgc2F0aXNmeSB0aGUgcmVxdWlyZW1lbnRzLCBwcmludCA8Y29kZT4tMTxcL2NvZGU+LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDJcXGxlIE5cXGxlIDEwXjUkPFwvbGk+XHJcblx0PGxpPiQxXFxsZSBNXFxsZSAxMF41JDxcL2xpPlxyXG5cdDxsaT4kMVxcbGUgdV9pLHZfaVxcbGUgTiQ8XC9saT5cclxuXHQ8bGk+JHVfaVxcbmUgdl9pJDxcL2xpPlxyXG5cdDxsaT5Gb3IgYWxsIGludGVnZXJzICRpJCBhbmQgJGokIHN1Y2ggdGhhdCAkMVxcbGUgaSZsdDtqXFxsZSBNJCwgJFxce3VfaSx2X2lcXH1cXG5lXFx7dV9qLHZfalxcfSQuPFwvbGk+XHJcblx0PGxpPlRoZSBnaXZlbiBncmFwaCBpcyBjb25uZWN0ZWQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiROLCBNIFxcbGUgMTAkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD4kTiwgTSBcXGxlIDEwXjMkLiBBZGRpdGlvbmFsbHksIGZvciBhbGwgdGhyZWUgZGlzdGluY3QgdmVydGljZXMgJHUkLCAkdiQsIGFuZCAkdyQsIHRoZXJlIGlzIGEgcGF0aCBmcm9tIHZlcnRleCAkdSQgdG8gdmVydGV4ICR2JCB3aGljaCBkb2VzIG5vdCBjb250YWluIHZlcnRleCAkdyQuPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD4kTiwgTSBcXGxlIDEwXjMkPFwvcD5cclxuIiwic3VidGFzazQiOiI8cD5UaGVyZSBhcmUgbm8gYWRkaXRpb25hbCBjb25zdHJhaW50cy48XC9wPlxyXG4ifV0=

출처

School > 서울과학고등학교 > SciOI 2023 A-4번

채점 및 기타 정보

  • 예제는 채점하지 않는다.