시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (하단 참고) 256 MB 6 6 4 100.000%

문제

사내 N명의 임직원이 심심풀이 선물 교환 이벤트를 열기로 했다. 임직원은 1부터 N까지 번호가 매겨져있다.

총 M쌍의 임직원쌍이 선택되었고, 각 쌍의 임직원은 둘 중 한 사람이 선물을 주고 다른 사람이 받아야 한다 (서로 줄 수 없다).

구체적으로 M개의 (X[i], Y[i]) 쌍이 선택되었고, 각 쌍에 대해 X[i]가 Y[i]에게 선물을 주거나 Y[i]가 X[i]에게 선물을 주어야만 한다.

다만, 선물을 주고 받는 재미를 더하기 위해 아래와 같은 규칙을 정했다:

  • 각 임직원 i에 대하여, 임직원 i가 (다른 사람에게) 주는 선물의 수와 (다른 사람으로부터) 받는 선물의 수의 차이가 2미만이어야 한다

임직원쌍이 M개 있으므로 누가 누구에게 선물을 줄지 정하는 방법은 2M 가지 존재하는데, 이는 길이가 M인 0-1 문자열로 나타낼 수 있다 (이를 선물 문자열이라 하자).

구체적으로, X[i] 가 Y[i]에게 선물을 주는 경우를 '0'으로 나타내고 반대의 경우를 '1'로 나타내자.

예를 들어, N = 3, M = 2이고 임직원 쌍이 (2, 1) 과 (3, 1)이라 하자 (즉, X = [2, 3], Y = [1, 1])

  1. 선물 문자열이 00인 경우: 임직원 2와 임직원 3이 임직원 1에게 선물을 준다. 이 경우 임직원 1이 선물을 2개 받고 0개 주어서 규칙을 어긴다.
  2. 선물 문자열이 01인 경우: 임직원 2가 임직원 1에게, 임직원 1이 임직원 3에게 선물을 준다. 이 경우 규칙을 어기지 않는다.
  3. 선물 문자열이 10인 경우: 임직원 1이 임직원 2에게, 임직원 3이 임직원 1에게 선물을 준다. 이 경우 규칙을 어기지 않는다.
  4. 선물 문자열이 11인 경우: 임직원 1이 임직원 2와 임직원 3에게 선물을 준다. 이 경우 임직원 1이 규칙을 어긴다.

임직원의 수 N과 M개의 임직원 쌍이 주어졌을 때, 위 규칙을 어기지 않는 선물 문자열을 찾으시오.

위 예제의 경우 "01" 과 "10" 중 어느 것을 찾아도 정답이다.

입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 줄은 두 개의 정수 N과 M을 공백으로 구분하여 담고있다.

다음 M줄에 걸쳐서 임직원 쌍이 공백으로 구분되어 주어진다 (즉, X[i], Y[i]가 공백으로 구분되어 주어진다).

한 테스트 케이스 내에서 같은 쌍의 임직원은 최대 한 번만 입력으로 주어진다 (즉 x y가 한 번 입력으로 주어지면,x y 혹은 y x는 같은 테스트 케이스 내에서 다시 주어지지 않는다).

출력

각 테스트 케이스에 대해 규칙을 어기지 않는 (길이 M인) 선물 문자열 중 하나를 출력한다.

제한

  • 1 ≤ T ≤ 10
  • 2 ≤ N ≤ 1,000
  • 1 ≤ M ≤ min(100,000, N*(N-1)/2)

예제 입력 1

5
3 2
2 1
3 1
3 3
1 2
2 3
1 3
4 4
1 2
1 3
2 3
2 4
4 5
2 1
1 3
2 3
2 4
4 1
6 3
1 2
3 4
5 6

예제 출력 1

01
001
0100
11011
000
W3sicHJvYmxlbV9pZCI6IjE5NTk2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMTIwXHViYjNjIFx1YWQ1MFx1ZDY1OCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGFjXHViMGI0IE5cdWJhODVcdWM3NTggXHVjNzg0XHVjOWMxXHVjNmQwXHVjNzc0IFx1YzJlY1x1YzJlY1x1ZDQ4MFx1Yzc3NCBcdWMxMjBcdWJiM2MgXHVhZDUwXHVkNjU4IFx1Yzc3NFx1YmNhNFx1ZDJiOFx1Yjk3YyBcdWM1ZjRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWM3ODRcdWM5YzFcdWM2ZDBcdWM3NDAgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzhcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2QxZCBNXHVjMzBkXHVjNzU4IFx1Yzc4NFx1YzljMVx1YzZkMFx1YzMwZFx1Yzc3NCBcdWMxMjBcdWQwZGRcdWI0MThcdWM1YzhcdWFjZTAsIFx1YWMwMSBcdWMzMGRcdWM3NTggXHVjNzg0XHVjOWMxXHVjNmQwXHVjNzQwIFx1YjQ1OCBcdWM5MTEgXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWMxMjBcdWJiM2NcdWM3NDQgXHVjOGZjXHVhY2UwIFx1YjJlNFx1Yjk3OCBcdWMwYWNcdWI3OGNcdWM3NzQgXHViYzFiXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNCAoXHVjMTFjXHViODVjIFx1YzkwNCBcdWMyMTggXHVjNWM2XHViMmU0KS48XC9wPlxyXG5cclxuPHA+XHVhZDZjXHVjY2I0XHVjODAxXHVjNzNjXHViODVjIE1cdWFjMWNcdWM3NTggKFhbaV0sIFlbaV0pIFx1YzMwZFx1Yzc3NCBcdWMxMjBcdWQwZGRcdWI0MThcdWM1YzhcdWFjZTAsIFx1YWMwMSBcdWMzMGRcdWM1ZDAgXHViMzAwXHVkNTc0Jm5ic3A7WFtpXVx1YWMwMCBZW2ldXHVjNWQwXHVhYzhjIFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWM4ZmNcdWFjNzBcdWIwOTggWVtpXVx1YWMwMCBYW2ldXHVjNWQwXHVhYzhjIFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWM4ZmNcdWM1YjRcdWM1N2NcdWI5Y2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWI5Y2MsIFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWM4ZmNcdWFjZTAgXHViYzFiXHViMjk0IFx1YzdhY1x1YmJmOFx1Yjk3YyBcdWIzNTRcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YzgxNVx1ZDU4OFx1YjJlNDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWFjMDEgXHVjNzg0XHVjOWMxXHVjNmQwIGlcdWM1ZDAgXHViMzAwXHVkNTU4XHVjNWVjLCBcdWM3ODRcdWM5YzFcdWM2ZDAgaVx1YWMwMCAoXHViMmU0XHViOTc4IFx1YzBhY1x1Yjc4Y1x1YzVkMFx1YWM4YykgXHVjOGZjXHViMjk0IFx1YzEyMFx1YmIzY1x1Yzc1OCBcdWMyMThcdWM2NDAgKFx1YjJlNFx1Yjk3OCBcdWMwYWNcdWI3OGNcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzApIFx1YmMxYlx1YjI5NCBcdWMxMjBcdWJiM2NcdWM3NTggXHVjMjE4XHVjNzU4IFx1Y2MyOFx1Yzc3NFx1YWMwMCAyXHViYmY4XHViOWNjXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Yzc4NFx1YzljMVx1YzZkMFx1YzMwZFx1Yzc3NCBNXHVhYzFjIFx1Yzc4OFx1YzczY1x1YmJjMFx1Yjg1YyBcdWIyMDRcdWFjMDAgXHViMjA0XHVhZDZjXHVjNWQwXHVhYzhjIFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWM5MDRcdWM5YzAgXHVjODE1XHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCAyPHN1cD5NPFwvc3VwPiBcdWFjMDBcdWM5YzAgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0XHViMzcwLCBcdWM3NzRcdWIyOTQgXHVhZTM4XHVjNzc0XHVhYzAwIE1cdWM3NzggMC0xIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNCAoXHVjNzc0XHViOTdjIFx1YzEyMFx1YmIzYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWI3N2MgXHVkNTU4XHVjNzkwKS48XC9wPlxyXG5cclxuPHA+XHVhZDZjXHVjY2I0XHVjODAxXHVjNzNjXHViODVjLCBYW2ldIFx1YWMwMCBZW2ldXHVjNWQwXHVhYzhjIFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWM4ZmNcdWIyOTQgXHVhY2JkXHVjNmIwXHViOTdjICYjMzk7MCYjMzk7XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWNlMCBcdWJjMThcdWIzMDBcdWM3NTggXHVhY2JkXHVjNmIwXHViOTdjICYjMzk7MSYjMzk7XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgTiA9IDMsIE0gPSAyXHVjNzc0XHVhY2UwIFx1Yzc4NFx1YzljMVx1YzZkMCBcdWMzMGRcdWM3NzQgKDIsIDEpIFx1YWNmYyAoMywgMSlcdWM3NzRcdWI3N2MgXHVkNTU4XHVjNzkwIChcdWM5ODksIFggPSBbMiwgM10sIFkgPSBbMSwgMV0pPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHVjMTIwXHViYjNjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCAwMFx1Yzc3OCBcdWFjYmRcdWM2YjA6Jm5ic3A7XHVjNzg0XHVjOWMxXHVjNmQwIDJcdWM2NDAgXHVjNzg0XHVjOWMxXHVjNmQwIDNcdWM3NzQgXHVjNzg0XHVjOWMxXHVjNmQwIDFcdWM1ZDBcdWFjOGMgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YzkwMFx1YjJlNC4gXHVjNzc0IFx1YWNiZFx1YzZiMCBcdWM3ODRcdWM5YzFcdWM2ZDAgMVx1Yzc3NCBcdWMxMjBcdWJiM2NcdWM3NDQgMlx1YWMxYyBcdWJjMWJcdWFjZTAgMFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWMxMWMgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YzViNFx1YWUzNFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMTIwXHViYjNjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCAwMVx1Yzc3OCBcdWFjYmRcdWM2YjA6IFx1Yzc4NFx1YzljMVx1YzZkMCAyXHVhYzAwIFx1Yzc4NFx1YzljMVx1YzZkMCAxXHVjNWQwXHVhYzhjLCBcdWM3ODRcdWM5YzFcdWM2ZDAgMVx1Yzc3NCBcdWM3ODRcdWM5YzFcdWM2ZDAgM1x1YzVkMFx1YWM4YyBcdWMxMjBcdWJiM2NcdWM3NDQgXHVjOTAwXHViMmU0LiBcdWM3NzQgXHVhY2JkXHVjNmIwIFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWM1YjRcdWFlMzBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWMxMjBcdWJiM2MgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IDEwXHVjNzc4IFx1YWNiZFx1YzZiMDogXHVjNzg0XHVjOWMxXHVjNmQwIDFcdWM3NzQgXHVjNzg0XHVjOWMxXHVjNmQwIDJcdWM1ZDBcdWFjOGMsIFx1Yzc4NFx1YzljMVx1YzZkMCAzXHVjNzc0IFx1Yzc4NFx1YzljMVx1YzZkMCAxXHVjNWQwXHVhYzhjIFx1YzEyMFx1YmIzY1x1Yzc0NCBcdWM5MDBcdWIyZTQuIFx1Yzc3NCBcdWFjYmRcdWM2YjAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YzViNFx1YWUzMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzEyMFx1YmIzYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgMTFcdWM3NzggXHVhY2JkXHVjNmIwOiBcdWM3ODRcdWM5YzFcdWM2ZDAgMVx1Yzc3NCBcdWM3ODRcdWM5YzFcdWM2ZDAgMlx1YzY0MCBcdWM3ODRcdWM5YzFcdWM2ZDAgM1x1YzVkMFx1YWM4YyBcdWMxMjBcdWJiM2NcdWM3NDQgXHVjOTAwXHViMmU0LiBcdWM3NzQgXHVhY2JkXHVjNmIwIFx1Yzc4NFx1YzljMVx1YzZkMCAxXHVjNzc0IFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWM1YjRcdWFlMzRcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjNzg0XHVjOWMxXHVjNmQwXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIE1cdWFjMWNcdWM3NTggXHVjNzg0XHVjOWMxXHVjNmQwIFx1YzMwZFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3MDQgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YzViNFx1YWUzMFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjMTIwXHViYjNjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWNjM2VcdWM3M2NcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YzcwNCBcdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwICZxdW90OzAxJnF1b3Q7IFx1YWNmYyAmcXVvdDsxMCZxdW90OyBcdWM5MTEgXHVjNWI0XHViMjkwIFx1YWM4M1x1Yzc0NCBcdWNjM2VcdWM1NDRcdWIzYzQgXHVjODE1XHViMmY1XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YzkwNFx1Yzc0MCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBOXHVhY2ZjIE1cdWM3NDQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWIyZjRcdWFjZTBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMFx1YzExYyBcdWM3ODRcdWM5YzFcdWM2ZDAgXHVjMzBkXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0IChcdWM5ODksIFhbaV0sIFlbaV1cdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQpLjxcL3A+XHJcblxyXG48cD5cdWQ1NWMgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWIwYjRcdWM1ZDBcdWMxMWMgXHVhYzE5XHVjNzQwIFx1YzMwZFx1Yzc1OCBcdWM3ODRcdWM5YzFcdWM2ZDBcdWM3NDAgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWJjODhcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCAoXHVjOTg5IHgmbmJzcDt5XHVhYzAwIFx1ZDU1YyBcdWJjODggXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCx4IHkgXHVkNjM5XHVjNzQwIHkgeFx1YjI5NCBcdWFjMTlcdWM3NDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWIwYjRcdWM1ZDBcdWMxMWMgXHViMmU0XHVjMmRjIFx1YzhmY1x1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCZuYnNwO1x1YWRkY1x1Y2U1OVx1Yzc0NCBcdWM1YjRcdWFlMzBcdWM5YzAgXHVjNTRhXHViMjk0IChcdWFlMzhcdWM3NzQgTVx1Yzc3OCkmbmJzcDtcdWMxMjBcdWJiM2MgXHViYjM4XHVjNzkwXHVjNWY0IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgVCAmbGU7IDEwPFwvbGk+XHJcblx0PGxpPjIgJmxlOyBOICZsZTsgMSwwMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IE0gJmxlOyBtaW4oMTAwLDAwMCwgTiooTi0xKVwvMik8XC9saT5cclxuPFwvdWw+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjE5NTk2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR2lmdCBFeGNoYW5nZSIsImRlc2NyaXB0aW9uIjoiPHA+TiBlbXBsb3llZXMgYXJlIHBhcnRpY2lwYXRpbmcgaW4gYSBHaWZ0IEV4Y2hhbmdlIGV2ZW50LiBFbXBsb3llZXMgYXJlIGxhYmVsZWQgYXMgMSwgMiwgLi4uLCBOLjxcL3A+XHJcblxyXG48cD5NIHBhaXJzIG9mIGVtcGxveWVlcyBoYXZlIGJlZW4gY2hvc2VuIHN1Y2ggdGhhdCBvbmUgZW1wbG95ZWUgbXVzdCBnaXZlIGEgZ2lmdCB0byB0aGUgb3RoZXIgZW1wbG95ZWUgaW4gZWFjaCBwYWlyLjxcL3A+XHJcblxyXG48cD5Gb3JtYWxseSwgdGhlcmUgYXJlIE0gcGFpcnMgKFhbaV0sIFlbaV0pLCBhbmQgZWl0aGVyIFhbaV0gc2hvdWxkIGdpdmUgWVtpXSBhIGdpZnQmbmJzcDtvciBZW2ldIHNob3VsZCBnaXZlIFhbaV0gYSBnaWZ0LjxcL3A+XHJcblxyXG48cD5UbyBtYWtlIHRoaXMgZXZlbnQgbW9yZSBmdW4sIHRoZSBmb2xsb3dpbmcgcnVsZSB3aWxsIGJlIGVuZm9yY2VkOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkZvciBlYWNoIGVtcGxveWVlIGksIHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIG51bWJlciBvZiBnaWZ0cyBlbXBsb3llZSBpIGdpdmVzIGFuZCB0aGUgbnVtYmVyIG9mIGdpZnRzIGVtcGxveWVlIGkgcmVjZWl2ZXMgbXVzdCBiZSBsZXNzIHRoYW4gMi48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5BcyB0aGVyZSBhcmUgTSBwYWlycywgdGhlcmUgYXJlIGV4YWN0bHkgMjxzdXA+TTxcL3N1cD4gd2F5cyB0byBkZWNpZGUgd2hvIGdpdmVzIGEgZ2lmdCB0byB3aG9tLCB3aGljaCBjYW4gYmUgcmVwcmVzZW50ZWQgYnkgYSAwLTEgc3RyaW5nIG9mIGxlbmd0aCBNIChsZXQgdXMgY2FsbCBzdWNoIHN0cmluZ3MgJnF1b3Q7Z2lmdCBzdHJpbmdzJnF1b3Q7KS48XC9wPlxyXG5cclxuPHA+U3BlY2lmaWNhbGx5LCBpZiBYW2ldIGdpdmVzIGEgZ2lmdCB0byBZW2ldLCB3ZSB1c2UgJiMzOTswJiMzOTsgYW5kIHRoZSByZXZlcnNlIHdheSBpcyAmIzM5OzEmIzM5Oy48XC9wPlxyXG5cclxuPHA+Rm9yIGluc3RhbmNlLCBjb25zaWRlciBOID0gMywgTSA9IDIgd2l0aCAoMiwgMSkgYW5kICgzLCAxKSBiZWluZyB0aGUgcGFpcnMgKHRoYXQgaXMsIFggPSBbMiwgM10gYW5kIFkgPSBbMSwgMV0pLjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPldoZW4gdGhlIGdpZnQgc3RyaW5nIGlzIDAwOiBFbXBsb3llZSAyIGFuZCBlbXBsb3llZSAzIGdpdmUgYSBnaWZ0IHRvIGVtcGxveWVlIDEuIEluIHRoaXMgY2FzZSwgZW1wbG95ZWUgMSByZWNlaXZlcyB0d28gZ2lmdHMgYW5kIGdpdmVzIHplcm8gZ2lmdHMsIHNvIHRoaXMgdmlvbGF0ZXMgdGhlIHJ1bGUuPFwvbGk+XHJcblx0PGxpPldoZW4gdGhlIGdpZnQgc3RyaW5nIGlzIDAxOiBFbXBsb3llZSAyIGdpdmVzIGEgZ2lmdCB0byBlbXBsb3llZSAxIGFuZCBlbXBsb3llZSAxIGdpdmVzIGEgZ2lmdCB0byBlbXBsb3llZSAzLiBUaGlzIGRvZXMgbm90IHZpb2xhdGUgdGhlIHJ1bGUuPFwvbGk+XHJcblx0PGxpPldoZW4gdGhlIGdpZnQgc3RyaW5nIGlzIDEwOiBFbXBsb3llZSAxJm5ic3A7Z2l2ZXMgYSBnaWZ0IHRvIGVtcGxveWVlIDIgYW5kIGVtcGxveWVlIDMgZ2l2ZXMgYSBnaWZ0IHRvIGVtcGxveWVlIDEuJm5ic3A7VGhpcyBkb2VzIG5vdCB2aW9sYXRlIHRoZSBydWxlLjxcL2xpPlxyXG5cdDxsaT5XaGVuIHRoZSBnaWZ0IHN0cmluZyBpcyAxMTogRW1wbG95ZWUgMSBnaXZlcyBhIGdpZnQmbmJzcDtib3RoIHRvIGVtcGxveWVlIDIgYW5kIHRvIGVtcGxveWVlIDMuIEVtcGxveWVlIDEgdmlvbGF0ZXMgdGhlIHJ1bGUuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+R2l2ZW4gTiBhbmQgTSBwYWlycywgZmluZCBhbnkmbmJzcDtnaWZ0IHN0cmluZyB0aGF0IHdvdWxkIG5vdCB2aW9sYXRlIHRoZSBydWxlLjxcL3A+XHJcblxyXG48cD5JbiB0aGUgZXhhbXBsZSBhYm92ZSwgYm90aCAmcXVvdDswMSZxdW90OyBhbmQmbmJzcDsmcXVvdDsxMCZxdW90OyBhcmUgY29ycmVjdCBhbnN3ZXJzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgd2lsbCBjb250YWluIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgVC48XC9wPlxyXG5cclxuPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCB0aGUgZmlyc3QgbGluZSB3aWxsIGNvbnRhaW4gTiBhbmQgTSBzZXBhcmF0ZWQgYnkgYSB3aGl0ZXNwYWNlLjxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBNIGxpbmVzIHdpbGwgY29udGFpbiBYW2ldIGFuZCBZW2ldIHNlcGFyYXRlZCBieSBhIHdoaXRlc3BhY2UuPFwvcD5cclxuXHJcbjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgdGhlIHNhbWUgcGFpciBvZiBlbXBsb3llZXMgd2lsbCBiZSBnaXZlbiBhcyBpbnB1dCBhdCBtb3N0IG9uY2UgKHRoYXQgaXMsIGlmICZxdW90O3ggeSZxdW90OyBpcyBnaXZlbiBhcyBpbnB1dCwgdGhlbiBuZWl0aGVyICZxdW90O3ggeSZxdW90OyBub3IgJnF1b3Q7eSB4JnF1b3Q7IHdpbGwgYmUgZ2l2ZW4gYXMgaW5wdXQgaW4gdGhlIHNhbWUgdGVzdCBjYXNlKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCB0aGUgZ2lmdCBzdHJpbmcgKG9mIGxlbmd0aCBNKSB0aGF0IGRvZXMgbm90IHZpb2xhdGUgdGhlIHJ1bGUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgVCAmbGU7IDEwPFwvbGk+XHJcblx0PGxpPjIgJmxlOyBOICZsZTsgMSwwMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IE0gJmxlOyBtaW4oMTAwLDAwMCwgTiooTi0xKVwvMik8XC9saT5cclxuPFwvdWw+XHJcbiJ9XQ==

시간 제한

  • Java 8: 2 초
  • Python 3: 4 초
  • PyPy3: 4 초
  • Java 8 (OpenJDK): 2 초
  • Java 11: 2 초
  • Python 2: 4 초
  • PyPy2: 4 초
  • Kotlin (JVM): 2 초
  • Java 15: 2 초