32152번 - 성호와 두산이 서브태스크다국어

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

문제

빨간색 구슬과 파란색 구슬이 각각 $N$개씩 있다. 성호와 두산이는 이 구슬을 가지고 게임을 한다. 먼저 게임을 시작하기 전에 구슬을 $N$개씩 나누어 가진다. 각자 나누어 가진 구슬을 정점으로 한 트리를 만들고, 루트가 될 구슬을 하나 정한다. 이 구슬이 1번이 된다.

게임은 성호부터 시작하며, 자신의 차례에는 다음과 같은 행동을 한다.

  • 자신의 트리에서 리프인 구슬을 하나 제거한다. 자신의 트리에 제거할 구슬이 없다면 게임을 종료한다.
  • 다음 차례는 제거한 구슬이 빨간색이라면 성호, 파란색이라면 두산이가 된다. 이 과정을 반복한다.

성호와 두산이가 만든 트리가 주어진다. 게임이 종료되었을 때 게임 전체에 남아 있는 구슬의 개수로 가능한 최솟값과 최댓값을 구하시오.

입력

첫 번째 줄에 자연수 $N$이 주어진다.

두 번째 줄에 성호가 가져간 $N$개의 구슬의 색깔을 나타내는 정수가 공백으로 구분되어 주어진다. $i$번째 정수는 $i$번 구슬의 색깔을 나타내며, $0$은 빨간색, $1$은 파란색 구슬임을 의미한다. ($1 \leq i \leq N$)

세 번째 줄부터 $N-1$개의 줄에 걸쳐 성호가 만든 트리의 간선이 연결하는 구슬 번호 두 개가 공백으로 구분되어 주어진다.

$N+2$ 번째 줄에 두산이가 가져간 $N$개의 구슬의 색깔을 나타내는 정수가 공백으로 구분되어 주어진다. $i$번째 정수는 $i$번 구슬의 색깔을 나타내며, $0$은 빨간색, $1$은 파란색 구슬임을 의미한다. ($1 \leq i \leq N$)

$N+3$ 번째 줄부터 $N-1$개의 줄에 걸쳐 두산이가 만든 트리의 간선이 연결하는 구슬 번호 두 개가 공백으로 구분되어 주어진다.

출력

게임이 종료되었을 때 게임 전체에 남아 있는 구슬의 개수로 가능한 최솟값과 최댓값을 공백으로 구분해 출력한다.

제한

  • $1 \leq N \leq 100,000$
  • 빨간색 구슬이 총 $N$개 있고, 파란색 구슬이 총 $N$개 있다.
  • 각자의 구슬 번호는 $1$부터 $N$까지이며, 서로 다르다.
  • 성호와 두산이가 구슬을 연결한 간선은 각각 트리 구조를 이룬다.

서브태스크 1 (20점)

성호와 두산이가 만든 트리의 $i$번째 간선은 $i$번 정점과 $i+1$번 정점을 연결한다. ($1 \leq i \leq N-1$)

서브태스크 2 (30점)

성호와 두산이가 만든 트리의 $i$번째 간선은 $1$번 정점과 $i+1$번 정점을 연결한다. ($1 \leq i \leq N-1$)

서브태스크 3 (50점)

추가 제약 조건 없음.

예제 입력 1 

4
0 1 0 1
1 2
1 3
4 2
1 0 0 1
3 2
1 4
2 1

예제 출력 1 

1 2

다음은 가능한 게임의 한 경우이다.

  1. 성호가 3번 구슬을 제거한다.
  2. 성호가 4번 구슬을 제거한다.
  3. 두산이가 3번 구슬을 제거한다.
  4. 성호가 2번 구슬을 제거한다.
  5. 두산이가 2번 구슬을 제거한다.
  6. 성호가 1번 구슬을 제거한다.
  7. 게임이 종료되고, 구슬은 두산이에게 2개 남아 있다.

예제 입력 2 

12
1 1 0 0 1 0 1 0 1 0 0 1
1 2
1 3
2 4
2 5
2 6
5 9
5 10
7 11
7 12
3 7
3 8
1 1 1 0 1 1 0 1 0 0 0 0
1 2
1 3
2 4
2 5
2 6
5 9
5 10
7 11
3 7
3 8
7 12

예제 출력 2 

2 6
W3sicHJvYmxlbV9pZCI6IjMyMTUyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMTMxXHVkNjM4XHVjNjQwIFx1YjQ1MFx1YzBiMFx1Yzc3NCIsImRlc2NyaXB0aW9uIjoiPHA+XHViZTY4XHVhYzA0XHVjMGM5IFx1YWQ2Y1x1YzJhY1x1YWNmYyBcdWQzMGNcdWI3ODBcdWMwYzkgXHVhZDZjXHVjMmFjXHVjNzc0IFx1YWMwMVx1YWMwMSAkTiRcdWFjMWNcdWM1MjkgXHVjNzg4XHViMmU0LiBcdWMxMzFcdWQ2MzhcdWM2NDAgXHViNDUwXHVjMGIwXHVjNzc0XHViMjk0IFx1Yzc3NCBcdWFkNmNcdWMyYWNcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NWNcdWIyZTQuIFx1YmEzY1x1YzgwMCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHVhZTMwIFx1YzgwNFx1YzVkMCBcdWFkNmNcdWMyYWNcdWM3NDQgJE4kXHVhYzFjXHVjNTI5IFx1YjA5OFx1YjIwNFx1YzViNCBcdWFjMDBcdWM5YzRcdWIyZTQuIFx1YWMwMVx1Yzc5MCBcdWIwOThcdWIyMDRcdWM1YjQgXHVhYzAwXHVjOWM0IFx1YWQ2Y1x1YzJhY1x1Yzc0NCBcdWM4MTVcdWM4MTBcdWM3M2NcdWI4NWMgXHVkNTVjIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFjZTAsIFx1YjhlOFx1ZDJiOFx1YWMwMCBcdWI0MjAgXHVhZDZjXHVjMmFjXHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWM4MTVcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWFkNmNcdWMyYWNcdWM3NzQgMVx1YmM4OFx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWMxMzFcdWQ2MzhcdWJkODBcdWQxMzAgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTcwLCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjYzI4XHViODQwXHVjNWQwXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVkNTg5XHViM2Q5XHVjNzQ0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM3OTBcdWMyZTBcdWM3NTggXHVkMmI4XHViOWFjXHVjNWQwXHVjMTFjIFx1YjlhY1x1ZDUwNFx1Yzc3OCBcdWFkNmNcdWMyYWNcdWM3NDQgXHVkNTU4XHViMDk4IFx1YzgxY1x1YWM3MFx1ZDU1Y1x1YjJlNC4gXHVjNzkwXHVjMmUwXHVjNzU4IFx1ZDJiOFx1YjlhY1x1YzVkMCBcdWM4MWNcdWFjNzBcdWQ1NjAgXHVhZDZjXHVjMmFjXHVjNzc0IFx1YzVjNlx1YjJlNFx1YmE3NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjODg1XHViOGNjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWIyZTRcdWM3NGMgXHVjYzI4XHViODQwXHViMjk0IFx1YzgxY1x1YWM3MFx1ZDU1YyBcdWFkNmNcdWMyYWNcdWM3NzQgXHViZTY4XHVhYzA0XHVjMGM5XHVjNzc0XHViNzdjXHViYTc0IFx1YzEzMVx1ZDYzOCwgXHVkMzBjXHViNzgwXHVjMGM5XHVjNzc0XHViNzdjXHViYTc0IFx1YjQ1MFx1YzBiMFx1Yzc3NFx1YWMwMCBcdWI0MWNcdWIyZTQuIFx1Yzc3NCBcdWFjZmNcdWM4MTVcdWM3NDQgXHViYzE4XHViY2Y1XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzEzMVx1ZDYzOFx1YzY0MCBcdWI0NTBcdWMwYjBcdWM3NzRcdWFjMDAgXHViOWNjXHViNGUwIFx1ZDJiOFx1YjlhY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWM4ODVcdWI4Y2NcdWI0MThcdWM1YzhcdWM3NDQgXHViNTRjIFx1YWM4Y1x1Yzc4NCBcdWM4MDRcdWNjYjRcdWM1ZDAgXHViMGE4XHVjNTQ0IFx1Yzc4OFx1YjI5NCBcdWFkNmNcdWMyYWNcdWM3NTggXHVhYzFjXHVjMjE4XHViODVjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWNkNWNcdWMxOWZcdWFjMTJcdWFjZmMgXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc5MFx1YzVmMFx1YzIxOCAkTiRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMxMzFcdWQ2MzhcdWFjMDAgXHVhYzAwXHVjODM4XHVhYzA0ICROJFx1YWMxY1x1Yzc1OCBcdWFkNmNcdWMyYWNcdWM3NTggXHVjMGM5XHVhZTU0XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMThcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICRpJFx1YmM4OFx1YzlmOCBcdWM4MTVcdWMyMThcdWIyOTQgJGkkXHViYzg4IFx1YWQ2Y1x1YzJhY1x1Yzc1OCBcdWMwYzlcdWFlNTRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwLCAkMCRcdWM3NDAgXHViZTY4XHVhYzA0XHVjMGM5LCAkMSRcdWM3NDAgXHVkMzBjXHViNzgwXHVjMGM5IFx1YWQ2Y1x1YzJhY1x1Yzc4NFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuICgkMSBcXGxlcSBpIFxcbGVxIE4kKTxcL3A+XHJcblxyXG48cD5cdWMxMzggXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCAkTi0xJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YzEzMVx1ZDYzOFx1YWMwMCBcdWI5Y2NcdWI0ZTAgXHVkMmI4XHViOWFjXHVjNzU4IFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVhZDZjXHVjMmFjIFx1YmM4OFx1ZDYzOCBcdWI0NTAgXHVhYzFjXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD4kTisyJCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MFx1YzBiMFx1Yzc3NFx1YWMwMCBcdWFjMDBcdWM4MzhcdWFjMDQgJE4kXHVhYzFjXHVjNzU4IFx1YWQ2Y1x1YzJhY1x1Yzc1OCBcdWMwYzlcdWFlNTRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJGkkXHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOFx1YjI5NCAkaSRcdWJjODggXHVhZDZjXHVjMmFjXHVjNzU4IFx1YzBjOVx1YWU1NFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAsICQwJFx1Yzc0MCBcdWJlNjhcdWFjMDRcdWMwYzksICQxJFx1Yzc0MCBcdWQzMGNcdWI3ODBcdWMwYzkgXHVhZDZjXHVjMmFjXHVjNzg0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gKCQxIFxcbGVxIGkgXFxsZXEgTiQpPFwvcD5cclxuXHJcbjxwPiROKzMkIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgJE4tMSRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWI0NTBcdWMwYjBcdWM3NzRcdWFjMDAgXHViOWNjXHViNGUwIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YWQ2Y1x1YzJhYyBcdWJjODhcdWQ2MzggXHViNDUwIFx1YWMxY1x1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjOGNcdWM3ODRcdWM3NzQgXHVjODg1XHViOGNjXHViNDE4XHVjNWM4XHVjNzQ0IFx1YjU0YyBcdWFjOGNcdWM3ODQgXHVjODA0XHVjY2I0XHVjNWQwIFx1YjBhOFx1YzU0NCBcdWM3ODhcdWIyOTQgXHVhZDZjXHVjMmFjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjg1YyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjZDVjXHVjMTlmXHVhYzEyXHVhY2ZjIFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTc0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDEgXFxsZXEgTiBcXGxlcSAxMDAsMDAwJDxcL2xpPlxyXG5cdDxsaT5cdWJlNjhcdWFjMDRcdWMwYzkgXHVhZDZjXHVjMmFjXHVjNzc0IFx1Y2QxZCAkTiRcdWFjMWMgXHVjNzg4XHVhY2UwLCBcdWQzMGNcdWI3ODBcdWMwYzkgXHVhZDZjXHVjMmFjXHVjNzc0IFx1Y2QxZCAkTiRcdWFjMWMgXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFjMDFcdWM3OTBcdWM3NTggXHVhZDZjXHVjMmFjIFx1YmM4OFx1ZDYzOFx1YjI5NCAkMSRcdWJkODBcdWQxMzAgJE4kXHVhZTRjXHVjOWMwXHVjNzc0XHViYTcwLCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWMxMzFcdWQ2MzhcdWM2NDAgXHViNDUwXHVjMGIwXHVjNzc0XHVhYzAwIFx1YWQ2Y1x1YzJhY1x1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NWMgXHVhYzA0XHVjMTIwXHVjNzQwIFx1YWMwMVx1YWMwMSBcdWQyYjhcdWI5YWMgXHVhZDZjXHVjODcwXHViOTdjIFx1Yzc3NFx1YjhlY1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2sxIjoiPHA+XHVjMTMxXHVkNjM4XHVjNjQwIFx1YjQ1MFx1YzBiMFx1Yzc3NFx1YWMwMCBcdWI5Y2NcdWI0ZTAgXHVkMmI4XHViOWFjXHVjNzU4ICRpJFx1YmM4OFx1YzlmOCBcdWFjMDRcdWMxMjBcdWM3NDAgJGkkXHViYzg4IFx1YzgxNVx1YzgxMFx1YWNmYyAkaSsxJFx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTVjXHViMmU0LiAoJDEgXFxsZXEgaSBcXGxlcSBOLTEkKTxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+XHVjMTMxXHVkNjM4XHVjNjQwIFx1YjQ1MFx1YzBiMFx1Yzc3NFx1YWMwMCBcdWI5Y2NcdWI0ZTAgXHVkMmI4XHViOWFjXHVjNzU4ICRpJFx1YmM4OFx1YzlmOCBcdWFjMDRcdWMxMjBcdWM3NDAgJDEkXHViYzg4IFx1YzgxNVx1YzgxMFx1YWNmYyAkaSsxJFx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTVjXHViMmU0LiAoJDEgXFxsZXEgaSBcXGxlcSBOLTEkKTxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+XHVjZDk0XHVhYzAwIFx1YzgxY1x1YzU3ZCBcdWM4NzBcdWFjNzQgXHVjNWM2XHVjNzRjLjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5cdWIyZTRcdWM3NGNcdWM3NDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YWM4Y1x1Yzc4NFx1Yzc1OCBcdWQ1NWMgXHVhY2JkXHVjNmIwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YzEzMVx1ZDYzOFx1YWMwMCAzXHViYzg4IFx1YWQ2Y1x1YzJhY1x1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzEzMVx1ZDYzOFx1YWMwMCA0XHViYzg4IFx1YWQ2Y1x1YzJhY1x1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjQ1MFx1YzBiMFx1Yzc3NFx1YWMwMCAzXHViYzg4IFx1YWQ2Y1x1YzJhY1x1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzEzMVx1ZDYzOFx1YWMwMCAyXHViYzg4IFx1YWQ2Y1x1YzJhY1x1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjQ1MFx1YzBiMFx1Yzc3NFx1YWMwMCAyXHViYzg4IFx1YWQ2Y1x1YzJhY1x1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzEzMVx1ZDYzOFx1YWMwMCAxXHViYzg4IFx1YWQ2Y1x1YzJhY1x1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWM4ODVcdWI4Y2NcdWI0MThcdWFjZTAsIFx1YWQ2Y1x1YzJhY1x1Yzc0MCBcdWI0NTBcdWMwYjBcdWM3NzRcdWM1ZDBcdWFjOGMgMlx1YWMxYyBcdWIwYThcdWM1NDQgXHVjNzg4XHViMmU0LjxcL2xpPlxyXG48XC9vbD4ifSx7InByb2JsZW1faWQiOiIzMjE1MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFsaWNlIGFuZCBCb2IiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGFyZSAkTiQgcmVkIG1hcmJsZXMgYW5kICROJCBibHVlIG1hcmJsZXMuIEFsaWNlIGFuZCBCb2Igd2lsbCBwbGF5IGEgZ2FtZSB1c2luZyB0aGVzZSBtYXJibGVzLiBGaXJzdCwgdGhleSBzcGxpdCB0aGUgbWFyYmxlcyBhbmQgc3RhcnQgd2l0aCAkTiQgbWFyYmxlcyBlYWNoLiBUaGVuLCBlYWNoIHBlcnNvbiBjcmVhdGVzIGEgdHJlZSB1c2luZyBtYXJibGVzIGFzIG5vZGVzLCBhbmQgc2VsZWN0cyBvbmUgbWFyYmxlIGFzIHRoZSByb290LiBUaGUgc2FpZCByb290IG1hcmJsZSYjMzk7cyBpbmRleCB3aWxsIGJlIDEuPFwvcD5cclxuXHJcbjxwPlRoZSBnYW1lIGJlZ2lucyB3aXRoIEFsaWNlJiMzOTtzIHR1cm4uIEVhY2ggcGxheWVyLCBkdXJpbmcgdGhlaXIgdHVybiwgdGFrZXMgdGhlIGZvbGxvd2luZyBhY3Rpb24ocyk6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+UmVtb3ZlIG9uZSBsZWFmLW5vZGUgbWFyYmxlIGZyb20gdGhlIHBsYXllciYjMzk7cyBvd24gdHJlZS4gSWYgbm8gbWFyYmxlcyBjYW4gYmUgcmVtb3ZlZCBmcm9tIHRoZSZuYnNwO3RyZWUsIHRoZW4gdGhlIGdhbWUgZW5kcy48XC9saT5cclxuXHQ8bGk+QWZ0ZXIgdGhlIHJlbW92YWwgb2YgYSByZWQgbWFyYmxlIChhIGJsdWUgbWFyYmxlLCByZXNwZWN0aXZlbHkpLCB0aGUgbmV4dCB0dXJuIHdpbGwgYmUgcGxheWVkIGJ5IEFsaWNlIChCb2IsIHJlc3BlY3RpdmVseSkuJm5ic3A7VGhpcyBwcm9jZXNzIHJlcGVhdHMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+QWxpY2UmIzM5O3MgYW5kIEJvYiYjMzk7cyB0cmVlcyBhcmUgZ2l2ZW4gYXMgaW5wdXQuIENvbXB1dGUgdGhlIG1pbmltdW0gYW5kIG1heGltdW0gcG9zc2libGUgbnVtYmVycyBvZiByZW1haW5pbmcgbWFyYmxlcyZuYnNwO2F0IHRoZSBlbmQgb2YgdGhlIGdhbWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCB3aWxsIGNvbnRhaW4gJE4kLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgd2lsbCBjb250YWluIHRoZSBjb2xvcnMgb2YgJE4kIG1hcmJsZXMgdGFrZW4gYnkgQWxpY2UsIHNlcGFyYXRlZCBieSB3aGl0ZXNwYWNlLiBUaGUgJGkkLXRoIHZhbHVlIGlzIHRoZSBjb2xvciBvZiB0aGUgJGkkLXRoIG1hcmJsZSwgJDAkIG1lYW5pbmcgcmVkIGFuZCAkMSQgbWVhbmluZyBibHVlLiZuYnNwOygkMSBcXGxlcSBpIFxcbGVxIE4kKTxcL3A+XHJcblxyXG48cD5TdGFydGluZyB3aXRoIHRoZSB0aGlyZCBsaW5lLCBlYWNoIG9mJm5ic3A7dGhlIG5leHQgJE4tMSQgbGluZXMgd2lsbCBjb250YWluIGFuIGVkZ2UgY29ubmVjdGluZyB0d28gbWFyYmxlcywmbmJzcDtzZXBhcmF0ZWQgYnkgd2hpdGVzcGFjZSwmbmJzcDtpbiB0aGUgdHJlZSBtYWRlIGJ5IEFsaWNlLjxcL3A+XHJcblxyXG48cD5UaGUgJE4rMiQtdGggbGluZSB3aWxsIGNvbnRhaW4gdGhlIGNvbG9ycyBvZiAkTiQgbWFyYmxlcyB0YWtlbiBieSBCb2IsIHNlcGFyYXRlZCBieSB3aGl0ZXNwYWNlLiBUaGUgJGkkLXRoIHZhbHVlIGlzIHRoZSBjb2xvciBvZiB0aGUgJGkkLXRoIG1hcmJsZSwgJDAkIG1lYW5pbmcgcmVkIGFuZCAkMSQgbWVhbmluZyBibHVlLiZuYnNwOygkMSBcXGxlcSBpIFxcbGVxIE4kKTxcL3A+XHJcblxyXG48cD5TdGFydGluZyB3aXRoIHRoZSAkTiszJC10aCZuYnNwO2xpbmUsIGVhY2ggb2YmbmJzcDt0aGUgbmV4dCAkTi0xJCBsaW5lcyB3aWxsIGNvbnRhaW4gYW4gZWRnZSBjb25uZWN0aW5nIHR3byBtYXJibGVzLCZuYnNwO3NlcGFyYXRlZCBieSB3aGl0ZXNwYWNlLCZuYnNwO2luIHRoZSB0cmVlIG1hZGUgYnkgQm9iLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbWluaW11bSBhbmQgbWF4aW11bSBwb3NzaWJsZSBudW1iZXJzIG9mIG1hcmJsZXMgdGhhdCByZW1haW4gYXQgdGhlIGVuZCBvZiB0aGUgZ2FtZSwgc2VwYXJhdGVkIGJ5IHdoaXRlc3BhY2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMSBcXGxlcSZuYnNwO04gXFxsZXEmbmJzcDsxMDAsMDAwJDxcL2xpPlxyXG5cdDxsaT5UaGVyZSB3aWxsIGJlICROJCByZWQgbWFyYmxlcyBhbmQgJE4kIGJsdWUgbWFyYmxlcy48XC9saT5cclxuXHQ8bGk+TWFyYmxlcyBhcmUgbnVtYmVyZWQgZnJvbSAkMSQgdG8gJE4kLCBhbmQgYXJlIGRpc3RpbmN0LjxcL2xpPlxyXG5cdDxsaT5BbGljZSYjMzk7cyBlZGdlcyBhbmQgQm9iJiMzOTtzIGVkZ2VzLCByZXNwZWN0aXZlbHksIHdpbGwgcmVzdWx0IGluIHZhbGlkIHRyZWVzLjxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD5JbiBBbGljZSYjMzk7cyB0cmVlIGFuZCBpbiBCb2ImIzM5O3MgdHJlZSwgcmVzcGVjdGl2ZWx5LCB0aGUgJGkkLXRoIGVkZ2UgY29ubmVjdHMgdGhlICRpJC10aCBtYXJibGUgYW5kICRpKzEkLXRoIG1hcmJsZS4mbmJzcDsoJDEgXFxsZXEmbmJzcDtpIFxcbGVxJm5ic3A7Ti0xJCk8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPkluIEFsaWNlJiMzOTtzIHRyZWUgYW5kIGluIEJvYiYjMzk7cyB0cmVlLCByZXNwZWN0aXZlbHksIHRoZSAkaSQtdGggZWRnZSBjb25uZWN0cyB0aGUmbmJzcDskMSQtc3QmbmJzcDttYXJibGUgYW5kICRpKzEkLXRoIG1hcmJsZS4mbmJzcDsoJDEgXFxsZXEmbmJzcDtpIFxcbGVxJm5ic3A7Ti0xJCk8XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPlRoZXJlIGFyZSBubyBhZGRpdGlvbmFsIGNvbnN0cmFpbnRzLjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5UaGUgZm9sbG93aW5nIGlzIG9uZSBwb3NzaWJsZSBvdXRjb21lIG9mIHRoZSBnYW1lOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkFsaWNlIHJlbW92ZXMgTWFyYmxlICMzLjxcL2xpPlxyXG5cdDxsaT5BbGljZSByZW1vdmVzIE1hcmJsZSAjNC48XC9saT5cclxuXHQ8bGk+Qm9iIHJlbW92ZXMgTWFyYmxlICMzLjxcL2xpPlxyXG5cdDxsaT5BbGljZSByZW1vdmVzIE1hcmJsZSAjMi48XC9saT5cclxuXHQ8bGk+Qm9iIHJlbW92ZXMgTWFyYmxlICMyLjxcL2xpPlxyXG5cdDxsaT5BbGljZSByZW1vdmVzIE1hcmJsZSAjMS48XC9saT5cclxuXHQ8bGk+VGhlIGdhbWUgZW5kcywgYW5kIHRoZXJlIHJlbWFpbiB0d28gbWFyYmxlcyBpbiBCb2ImIzM5O3MgdHJlZS48XC9saT5cclxuPFwvb2w+XHJcbiJ9XQ==

출처

채점 및 기타 정보

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

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)