시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB101353135.632%

문제

JOI합중국에는 $N$개의 도시가 있어서, 1번부터 $N$번까지의 번호가 붙어있다. 또한, JOI합중국에는 $N-1$개의 국도가 있다. $i$ 번째($1 \le i \le N-1$) 국도는 $A_i$번 도시와 $B_i$번 도시를 양방향으로 잇는다. 어떤 두 도시에 대해서도, 국도 몇개를 이용하면 서로 오가는 것이 가능하다.

현재, JOI합중국은 1번부터 $K$번까지의 번호가 붙어있는 $K$개의 주로 나뉘어 있다. $j$번 ($1 \le j \le N$)도시는 $S_j$번 주에 속한다. 모든 주에는 적어도 하나의 도시가 속해 있다.

JOI합중국의 대통령인 $K$이사장은, 이 나라가 분열하지 않을까 걱정이 되었다. 다음 조건을 모두 만족하도록 모든 도시를 2개의 그룹 $X$, $Y$로 나누는 것이 가능할 때, JOI합중국은 분열가능한 상태라고 말한다.

  • 모든 도시는 그룹 $X$혹은 그룹 $Y$에 속한다.
  • 그룹 $X$에는 적어도 하나의 도시가 속해 있다.
  • 그룹 $Y$에는 적어도 하나의 도시가 속해 있다.
  • 모든 주에 대해서, 그 주에 있는 모든 도시는 모두 같은 그룹에 속해 있다.
  • 그룹 $X$에 속한 어떤 두 도시에 대해서도, 그룹 $X$에 속한 도시만을 경유해서 서로 오가는 것이 가능하다.
  • 그룹 $Y$에 속한 어떤 두 도시에 대해서도, 그룹 $Y$에 속한 도시만을 경유해서 서로 오가는 것이 가능하다.

$K$이사장은, JOI합중국이 분열가능하지 않은 상태를 만들기 위해, 주를 합병하려고 한다. 한번의 합병은 두개의 주를 골라서 합치는 것을 말한다. 새로운 주는, 기존의 두 주에 속해 있던 도시 들이 속해있다. K이사장은 주를 최소한의 횟수만큼 합병하여 JOI합중국을 분열가능하지 않은 상태로 만들고 싶어한다.

도시와 국도의 위치, 현재 어떤 도시가 어떤 주에 속해있는가에 대한 상태가 주어졌을 때, JOI 합중국이 분열가능하지 않은 상태로 만들기 위한 합병의 최소 횟수를 구하는 프로그램을 작성하여라.

입력

표준 입력에서 다음과 같은 형식으로 주어진다. 모든 값은 정수이다.

$N$ $K$

$A_1$ $B_1$

$\vdots$

$A_{N-1}$ $B_{N-1}$

$S_1$

$\vdots$

$S_N$

출력

JOI합중국을 분열가능하지 않은 상태로 만들기 위한 합병의 최소횟수를 표준 출력의 첫째 줄에 출력하여라.

제한

  • $1 \le N \le 500\ 000$.
  • $1 \le K \le N$.
  • $1 \le A_i \le N$ ($1 \le i \le N-1$).
  • $1 \le B_i \le N$ ($1 \le i \le N-1$).
  • 어떤 두 도시에 대해서도, 국도 몇개를 이용하면 서로 오가는 것이 가능하다.
  • $1 \le S_j \le K$ ($1 \le j \le N$)
  • 모든 $k$ ($1 \le k \le N$)에 대해, $S_j = k$를 만족하는 $j$ ($1 \le j \le N$)가 존재한다.

서브태스크

번호 배점 제한
1 10

N ≤ 100, K ≤ 7.

2 24

N ≤ 3 000.

3 14

N ≤ 100 000, K ≤ 50.

4 22

N ≤ 100 000. At the initial situation, one can travel between any two cities belonging to the same state by using at most 100 highways.

5 30

No additional constraints.

예제 입력 1

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

예제 출력 1

1

이 예제에서는, 처음의 상태는 분열가능하다. 예를 들면, 1번, 2번, 3번, 4번 도시를 그룹 $X$라 하고, 5번 도시를 그룹 $Y$라고 하면 된다.

3번 주와 4번 주를 합병할 경우 분열가능하지 않은 상태가 된다. 그러므로 답은 1이다.

예제 입력 2

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

예제 출력 2

0

 이 예제에서는, 처음의 상태는 분열가능하지 않다. 그러므로 답은 0이다.

예제 입력 3

2 2
1 2
1
2

예제 출력 3

1
W3sicHJvYmxlbV9pZCI6IjE3Njc4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNTY5XHViY2QxIiwiZGVzY3JpcHRpb24iOiI8cD5KT0lcdWQ1NjlcdWM5MTFcdWFkNmRcdWM1ZDBcdWIyOTQgJE4kXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1YWMwMCBcdWM3ODhcdWM1YjRcdWMxMWMsIDFcdWJjODhcdWJkODBcdWQxMzAgJE4kXHViYzg4XHVhZTRjXHVjOWMwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YjYxMFx1ZDU1YywgSk9JXHVkNTY5XHVjOTExXHVhZDZkXHVjNWQwXHViMjk0ICROLTEkXHVhYzFjXHVjNzU4IFx1YWQ2ZFx1YjNjNFx1YWMwMCBcdWM3ODhcdWIyZTQuICRpJCBcdWJjODhcdWM5ZjgoJDEgXFxsZSBpIFxcbGUgTi0xJCkgXHVhZDZkXHViM2M0XHViMjk0ICRBX2kkXHViYzg4IFx1YjNjNFx1YzJkY1x1YzY0MCAkQl9pJFx1YmM4OCBcdWIzYzRcdWMyZGNcdWI5N2MgXHVjNTkxXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1Yzc4N1x1YjI5NFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1YjQ1MCBcdWIzYzRcdWMyZGNcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjXHViM2M0LCBcdWFkNmRcdWIzYzQgXHViYTg3XHVhYzFjXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YmE3NCBcdWMxMWNcdWI4NWMgXHVjNjI0XHVhYzAwXHViMjk0IFx1YWM4M1x1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzdhYywgSk9JXHVkNTY5XHVjOTExXHVhZDZkXHVjNzQwIDFcdWJjODhcdWJkODBcdWQxMzAgJEskXHViYzg4XHVhZTRjXHVjOWMwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1YjRcdWM3ODhcdWIyOTQgJEskXHVhYzFjXHVjNzU4IFx1YzhmY1x1Yjg1YyBcdWIwOThcdWIyNThcdWM1YjQgXHVjNzg4XHViMmU0LiAkaiRcdWJjODggKCQxIFxcbGUgaiBcXGxlIE4kKVx1YjNjNFx1YzJkY1x1YjI5NCAkU19qJFx1YmM4OCBcdWM4ZmNcdWM1ZDAgXHVjMThkXHVkNTVjXHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjOGZjXHVjNWQwXHViMjk0IFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NThcdWIwOThcdWM3NTggXHViM2M0XHVjMmRjXHVhYzAwIFx1YzE4ZFx1ZDU3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkpPSVx1ZDU2OVx1YzkxMVx1YWQ2ZFx1Yzc1OCBcdWIzMDBcdWQxYjVcdWI4MzlcdWM3NzggJEskXHVjNzc0XHVjMGFjXHVjN2E1XHVjNzQwLCBcdWM3NzQgXHViMDk4XHViNzdjXHVhYzAwIFx1YmQ4NFx1YzVmNFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDRcdWFlNGMgXHVhYzcxXHVjODE1XHVjNzc0IFx1YjQxOFx1YzVjOFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWJhYThcdWI0NTAgXHViOWNjXHVjODcxXHVkNTU4XHViM2M0XHViODVkIFx1YmFhOFx1YjRlMCBcdWIzYzRcdWMyZGNcdWI5N2MgMlx1YWMxY1x1Yzc1OCBcdWFkZjhcdWI4ZjkgJFgkLCAkWSRcdWI4NWMgXHViMDk4XHViMjA0XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NjAgXHViNTRjLCBKT0lcdWQ1NjlcdWM5MTFcdWFkNmRcdWM3NDAgPHN0cm9uZz5cdWJkODRcdWM1ZjRcdWFjMDBcdWIyYTU8XC9zdHJvbmc+XHVkNTVjIFx1YzBjMVx1ZDBkY1x1Yjc3Y1x1YWNlMCBcdWI5ZDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1YjI5NCBcdWFkZjhcdWI4ZjkgJFgkXHVkNjM5XHVjNzQwIFx1YWRmOFx1YjhmOSAkWSRcdWM1ZDAgXHVjMThkXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFkZjhcdWI4ZjkgJFgkXHVjNWQwXHViMjk0IFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NThcdWIwOThcdWM3NTggXHViM2M0XHVjMmRjXHVhYzAwIFx1YzE4ZFx1ZDU3NCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWRmOFx1YjhmOSAkWSRcdWM1ZDBcdWIyOTQgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWIzYzRcdWMyZGNcdWFjMDAgXHVjMThkXHVkNTc0IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViYWE4XHViNGUwIFx1YzhmY1x1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YWRmOCBcdWM4ZmNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWIzYzRcdWMyZGNcdWIyOTQgXHViYWE4XHViNDUwIFx1YWMxOVx1Yzc0MCBcdWFkZjhcdWI4ZjlcdWM1ZDAgXHVjMThkXHVkNTc0IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhZGY4XHViOGY5ICRYJFx1YzVkMCBcdWMxOGRcdWQ1NWMgXHVjNWI0XHViNWE0IFx1YjQ1MCBcdWIzYzRcdWMyZGNcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjXHViM2M0LCBcdWFkZjhcdWI4ZjkgJFgkXHVjNWQwIFx1YzE4ZFx1ZDU1YyBcdWIzYzRcdWMyZGNcdWI5Y2NcdWM3NDQgXHVhY2JkXHVjNzIwXHVkNTc0XHVjMTFjIFx1YzExY1x1Yjg1YyBcdWM2MjRcdWFjMDBcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhZGY4XHViOGY5ICRZJFx1YzVkMCBcdWMxOGRcdWQ1NWMgXHVjNWI0XHViNWE0IFx1YjQ1MCBcdWIzYzRcdWMyZGNcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjXHViM2M0LCBcdWFkZjhcdWI4ZjkgJFkkXHVjNWQwIFx1YzE4ZFx1ZDU1YyBcdWIzYzRcdWMyZGNcdWI5Y2NcdWM3NDQgXHVhY2JkXHVjNzIwXHVkNTc0XHVjMTFjIFx1YzExY1x1Yjg1YyBcdWM2MjRcdWFjMDBcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4kSyRcdWM3NzRcdWMwYWNcdWM3YTVcdWM3NDAsIEpPSVx1ZDU2OVx1YzkxMVx1YWQ2ZFx1Yzc3NCBcdWJkODRcdWM1ZjRcdWFjMDBcdWIyYTVcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0LCBcdWM4ZmNcdWI5N2MgXHVkNTY5XHViY2QxXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkNTVjXHViYzg4XHVjNzU4IFx1ZDU2OVx1YmNkMVx1Yzc0MCBcdWI0NTBcdWFjMWNcdWM3NTggXHVjOGZjXHViOTdjIFx1YWNlOFx1Yjc3Y1x1YzExYyBcdWQ1NjlcdWNlNThcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjlkMFx1ZDU1Y1x1YjJlNC4gXHVjMGM4XHViODVjXHVjNmI0IFx1YzhmY1x1YjI5NCwgXHVhZTMwXHVjODc0XHVjNzU4IFx1YjQ1MCBcdWM4ZmNcdWM1ZDAgXHVjMThkXHVkNTc0IFx1Yzc4OFx1YjM1OCBcdWIzYzRcdWMyZGMgXHViNGU0XHVjNzc0IFx1YzE4ZFx1ZDU3NFx1Yzc4OFx1YjJlNC4gS1x1Yzc3NFx1YzBhY1x1YzdhNVx1Yzc0MCBcdWM4ZmNcdWI5N2MgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzU4IFx1ZDY5Zlx1YzIxOFx1YjljY1x1ZDA3YyBcdWQ1NjlcdWJjZDFcdWQ1NThcdWM1ZWMgSk9JXHVkNTY5XHVjOTExXHVhZDZkXHVjNzQ0IFx1YmQ4NFx1YzVmNFx1YWMwMFx1YjJhNVx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjMGMxXHVkMGRjXHViODVjIFx1YjljY1x1YjRlNFx1YWNlMCBcdWMyZjZcdWM1YjRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNjNFx1YzJkY1x1YzY0MCBcdWFkNmRcdWIzYzRcdWM3NTggXHVjNzA0XHVjZTU4LCBcdWQ2MDRcdWM3YWMgXHVjNWI0XHViNWE0IFx1YjNjNFx1YzJkY1x1YWMwMCBcdWM1YjRcdWI1YTQgXHVjOGZjXHVjNWQwIFx1YzE4ZFx1ZDU3NFx1Yzc4OFx1YjI5NFx1YWMwMFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjMGMxXHVkMGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIEpPSSBcdWQ1NjlcdWM5MTFcdWFkNmRcdWM3NzQgXHViZDg0XHVjNWY0XHVhYzAwXHViMmE1XHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWMwYzFcdWQwZGNcdWI4NWMgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWQ1NjlcdWJjZDFcdWM3NTggXHVjZDVjXHVjMThjIFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1ZDQ1Y1x1YzkwMCBcdWM3ODVcdWI4MjVcdWM1ZDBcdWMxMWMgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQ2MTVcdWMyZGRcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVhYzEyXHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JE4kICRLJDxcL3A+XHJcblxyXG48cD4kQV8xJCAkQl8xJDxcL3A+XHJcblxyXG48cD4kXFx2ZG90cyQ8XC9wPlxyXG5cclxuPHA+JEFfe04tMX0kICRCX3tOLTF9JDxcL3A+XHJcblxyXG48cD4kU18xJDxcL3A+XHJcblxyXG48cD4kXFx2ZG90cyQ8XC9wPlxyXG5cclxuPHA+JFNfTiQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5KT0lcdWQ1NjlcdWM5MTFcdWFkNmRcdWM3NDQgXHViZDg0XHVjNWY0XHVhYzAwXHViMmE1XHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWMwYzFcdWQwZGNcdWI4NWMgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWQ1NjlcdWJjZDFcdWM3NTggXHVjZDVjXHVjMThjXHVkNjlmXHVjMjE4XHViOTdjIFx1ZDQ1Y1x1YzkwMCBcdWNkOWNcdWI4MjVcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQxIFxcbGUgTiBcXGxlIDUwMFxcIDAwMCQuPFwvbGk+XHJcblx0PGxpPiQxIFxcbGUgSyBcXGxlIE4kLjxcL2xpPlxyXG5cdDxsaT4kMSBcXGxlIEFfaSBcXGxlIE4kICgkMSBcXGxlIGkgXFxsZSBOLTEkKS48XC9saT5cclxuXHQ8bGk+JDEgXFxsZSBCX2kgXFxsZSBOJCAoJDEgXFxsZSBpIFxcbGUgTi0xJCkuPFwvbGk+XHJcblx0PGxpPlx1YzViNFx1YjVhNCBcdWI0NTAgXHViM2M0XHVjMmRjXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExY1x1YjNjNCwgXHVhZDZkXHViM2M0IFx1YmE4N1x1YWMxY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWJhNzQgXHVjMTFjXHViODVjIFx1YzYyNFx1YWMwMFx1YjI5NCBcdWFjODNcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT4kMSBcXGxlIFNfaiBcXGxlIEskICgkMSBcXGxlIGogXFxsZSBOJCk8XC9saT5cclxuXHQ8bGk+XHViYWE4XHViNGUwICRrJCAoJDEgXFxsZSBrIFxcbGUgTiQpXHVjNWQwIFx1YjMwMFx1ZDU3NCwgJFNfaiA9IGskXHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCAkaiQgKCQxIFxcbGUgaiBcXGxlIE4kKVx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPk4gJmxlOyAxMDAsIEsgJmxlOyA3LjxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+TiAmbGU7IDMgMDAwLjxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+TiAmbGU7IDEwMCAwMDAsIEsgJmxlOyA1MC48XC9wPlxyXG4iLCJzdWJ0YXNrNCI6IjxwPk4gJmxlOyAxMDAgMDAwLiBBdCB0aGUgaW5pdGlhbCBzaXR1YXRpb24sIG9uZSBjYW4gdHJhdmVsIGJldHdlZW4gYW55IHR3byBjaXRpZXMgYmVsb25naW5nIHRvIHRoZSBzYW1lIHN0YXRlIGJ5IHVzaW5nIGF0IG1vc3QgMTAwIGhpZ2h3YXlzLjxcL3A+XHJcbiIsInN1YnRhc2s1IjoiPHA+Tm8gYWRkaXRpb25hbCBjb25zdHJhaW50cy48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+XHVjNzc0IFx1YzYwOFx1YzgxY1x1YzVkMFx1YzExY1x1YjI5NCwgXHVjYzk4XHVjNzRjXHVjNzU4IFx1YzBjMVx1ZDBkY1x1YjI5NCBcdWJkODRcdWM1ZjRcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQsIDFcdWJjODgsIDJcdWJjODgsIDNcdWJjODgsIDRcdWJjODggXHViM2M0XHVjMmRjXHViOTdjIFx1YWRmOFx1YjhmOSAkWCRcdWI3N2MgXHVkNTU4XHVhY2UwLCA1XHViYzg4IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWFkZjhcdWI4ZjkgJFkkXHViNzdjXHVhY2UwIFx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjNcdWJjODggXHVjOGZjXHVjNjQwJm5ic3A7NFx1YmM4OCBcdWM4ZmNcdWI5N2MgXHVkNTY5XHViY2QxXHVkNTYwIFx1YWNiZFx1YzZiMCBcdWJkODRcdWM1ZjRcdWFjMDBcdWIyYTVcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWI0MWNcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YmJjMFx1Yjg1YyBcdWIyZjVcdWM3NDAgMVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHA+Jm5ic3A7XHVjNzc0IFx1YzYwOFx1YzgxY1x1YzVkMFx1YzExY1x1YjI5NCwgXHVjYzk4XHVjNzRjXHVjNzU4IFx1YzBjMVx1ZDBkY1x1YjI5NCBcdWJkODRcdWM1ZjRcdWFjMDBcdWIyYTVcdWQ1NThcdWM5YzAgXHVjNTRhXHViMmU0LiBcdWFkZjhcdWI3ZWNcdWJiYzBcdWI4NWMgXHViMmY1XHVjNzQwIDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMTc2NzgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNZXJnZXJzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBhcmUgTiBjaXRpZXMgbnVtYmVyZWQgZnJvbSAxIHRvIE4gYW5kIE4gJm1pbnVzOyAxIGhpZ2h3YXlzIG51bWJlcmVkIGZyb20gMSB0byBOICZtaW51czsgMSBpbiB0aGUgVW5pdGVkIFN0YXRlcyBvZiBKT0kuIFRoZSBpLXRoIGhpZ2h3YXkgKDEgJmxlOyBpICZsZTsgTiAmbWludXM7IDEpIGNvbm5lY3RzIGJldHdlZW4gdGhlIGNpdHkgQTxzdWI+aTxcL3N1Yj4gYW5kIHRoZSBjaXR5IEI8c3ViPmk8XC9zdWI+IGJpZGlyZWN0aW9uYWxseS4gT25lIGNhbiB0cmF2ZWwgYmV0d2VlbiBhbnkgdHdvIGNpdGllcyBieSB1c2luZyB0aGUgaGlnaHdheXMuPFwvcD5cclxuXHJcbjxwPkN1cnJlbnRseSwgdGhlIFVuaXRlZCBTdGF0ZXMgb2YgSk9JIGlzIGNvbnN0aXR1dGVkIG9mIEsgc3RhdGVzIG51bWJlcmVkIGZyb20gMSB0byBLLiBUaGUgY2l0eSBqICgxICZsZTsgaiAmbGU7IE4pIGJlbG9uZ3MgdG8gdGhlIHN0YXRlIFM8c3ViPmo8XC9zdWI+LiBBbnkgc3RhdGUgaGFzIGF0IGxlYXN0IG9uZSBjaXR5LjxcL3A+XHJcblxyXG48cD5Nci4gSywgdGhlIHByZXNpZGVudCBvZiB0aGUgVW5pdGVkIFN0YXRlcyBvZiBKT0ksIGlzIGFmcmFpZCBvZiBzZXBhcmF0aW9uIG9mIHRoaXMgY291bnRyeS4gVGhlIFVuaXRlZCBTdGF0ZXMgb2YgSk9JIGlzIHNhaWQgdG8gYmUgPHN0cm9uZz5zZXBhcmFibGU8XC9zdHJvbmc+IGlmIG9uZSBjYW4gZGl2aWRlIGFsbCBjaXRpZXMgaW50byBHcm91cCBYIGFuZCBHcm91cCBZIHNvIHRoYXQgdGhlIGZvbGxvd2luZyBjb25kaXRpb25zIGFyZSBzYXRpc2ZpZWQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+QW55IGNpdHkgYmVsb25ncyB0byBlaXRoZXIgR3JvdXAgWCBvciBHcm91cCBZLjxcL2xpPlxyXG5cdDxsaT5Hcm91cCBYIGhhcyBhdCBsZWFzdCBvbmUgY2l0eS48XC9saT5cclxuXHQ8bGk+R3JvdXAgWSBoYXMgYXQgbGVhc3Qgb25lIGNpdHkuPFwvbGk+XHJcblx0PGxpPkZvciBhbnkgc3RhdGUsIGFsbCBjaXRpZXMgYmVsb25naW5nIHRvIHRoZSBzdGF0ZSBiZWxvbmdzIHRoZSBzYW1lIGdyb3VwLjxcL2xpPlxyXG5cdDxsaT5PbmUgY2FuIHRyYXZlbCBiZXR3ZWVuIGFueSB0d28gY2l0aWVzIGJlbG9uZ2luZyB0byBHcm91cCBYIG9ubHkgdmlhIGNpdGllcyBiZWxvbmdpbmcgdG8gR3JvdXAgWCBieSB1c2luZyB0aGUgaGlnaHdheXMuPFwvbGk+XHJcblx0PGxpPk9uZSBjYW4gdHJhdmVsIGJldHdlZW4gYW55IHR3byBjaXRpZXMgYmVsb25naW5nIHRvIEdyb3VwIFkgb25seSB2aWEgY2l0aWVzIGJlbG9uZ2luZyB0byBHcm91cCBZIGJ5IHVzaW5nIHRoZSBoaWdod2F5cy48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Nci4gSyBpcyBnb2luZyB0byBtZXJnZSBzdGF0ZXMgdG8gbWFrZSB0aGUgVW5pdGVkIFN0YXRlcyBvZiBKT0kgbm90IHNlcGFyYWJsZS4gV2hlbiBoZSBtZXJnZXMgc3RhdGVzLCBoZSBjaG9vc2VzIHR3byBzdGF0ZXMgYW5kIHVuaWZpZXMgdGhlIHN0YXRlcyBpbnRvIGEgc3RhdGUuIFRoZSBjaXRpZXMgYmVsb25naW5nIHRvIHRoZSB1bmlmaWVkIHN0YXRlIGFyZSB0aGUgY2l0aWVzIGJlbG9uZ2luZyB0byBlaXRoZXIgb2YgdGhlIHR3byBzdGF0ZXMuIE1yLiBLIHdhbnRzIHRvIG1ha2UgdGhlIFVuaXRlZCBTdGF0ZXMgb2YgSk9JIG5vdCBzZXBhcmFibGUgYnkgbWVyZ2luZyBzdGF0ZXMgYXMgZmV3IHRpbWVzIGFzIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5Ob3RlIHRoYXQgaWYgdGhlIFVuaXRlZCBTdGF0ZXMgb2YgSk9JIGhhcyBvbmx5IG9uZSBzdGF0ZSwgaXQgaXMgbm90IHNlcGFyYWJsZS48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoLCBnaXZlbiBpbmZvcm1hdGlvbiBhYm91dCBjaXRpZXMsIGhpZ2h3YXlzIGFuZCBzdGF0ZXMsIGNhbGN1bGF0ZXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1lcmdlcnMgdG8gbWFrZSB0aGUgVW5pdGVkIFN0YXRlcyBvZiBKT0kgbm90IHNlcGFyYWJsZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlJlYWQgdGhlIGZvbGxvd2luZyBkYXRhIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0LiBBbGwgdGhlIHZhbHVlcyBpbiB0aGUgaW5wdXQgYXJlIGludGVnZXJzLjxcL3A+XHJcblxyXG48cHJlPlxyXG5OIEtcclxuQTxzdWI+MTxcL3N1Yj4gQjxzdWI+MTxcL3N1Yj5cclxuOlxyXG5BPHN1Yj5OJm1pbnVzOzE8XC9zdWI+IEI8c3ViPk4mbWludXM7MTxcL3N1Yj5cclxuUzxzdWI+MTxcL3N1Yj5cclxuOlxyXG5TPHN1Yj5OPFwvc3ViPjxcL3ByZT5cclxuIiwib3V0cHV0IjoiPHA+V3JpdGUgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1lcmdlcnMgdG8gbWFrZSB0aGUgVW5pdGVkIFN0YXRlcyBvZiBKT0kgbm90IHNlcGFyYWJsZSB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IE4gJmxlOyA1MDAgMDAwXHVmZjBlPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBLICZsZTsgTlx1ZmYwZTxcL2xpPlxyXG5cdDxsaT4xICZsZTsgQTxzdWI+aTxcL3N1Yj4gJmxlOyBOICgxICZsZTsgaSAmbGU7IE4gJm1pbnVzOyAxKVx1ZmYwZTxcL2xpPlxyXG5cdDxsaT4xICZsZTsgQjxzdWI+aTxcL3N1Yj4gJmxlOyBOICgxICZsZTsgaSAmbGU7IE4gJm1pbnVzOyAxKVx1ZmYwZTxcL2xpPlxyXG5cdDxsaT5PbmUgY2FuIHRyYXZlbCBiZXR3ZWVuIGFueSB0d28gY2l0aWVzIGJ5IHVzaW5nIHRoZSBoaWdod2F5cy48XC9saT5cclxuXHQ8bGk+MSAmbGU7IFM8c3ViPmo8XC9zdWI+ICZsZTsgSyAoMSAmbGU7IGogJmxlOyBOKVx1ZmYwZTxcL2xpPlxyXG5cdDxsaT5Gb3IgYW55IGsgKDEgJmxlOyBrICZsZTsgSyksIHRoZXJlIGV4aXN0cyBqICgxICZsZTsgaiAmbGU7IE4pIHN1Y2ggdGhhdCBTPHN1Yj5qPFwvc3ViPiA9IGsuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPk4gJmxlOyAxMDAsIEsgJmxlOyA3LjxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+TiAmbGU7IDMgMDAwLjxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+TiAmbGU7IDEwMCAwMDAsIEsgJmxlOyA1MC48XC9wPlxyXG4iLCJzdWJ0YXNrNCI6IjxwPk4gJmxlOyAxMDAgMDAwLiBBdCB0aGUgaW5pdGlhbCBzaXR1YXRpb24sIG9uZSBjYW4gdHJhdmVsIGJldHdlZW4gYW55IHR3byBjaXRpZXMgYmVsb25naW5nIHRvIHRoZSBzYW1lIHN0YXRlIGJ5IHVzaW5nIGF0IG1vc3QgMTAwIGhpZ2h3YXlzLjxcL3A+XHJcbiIsInN1YnRhc2s1IjoiPHA+Tm8gYWRkaXRpb25hbCBjb25zdHJhaW50cy48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+SW4gdGhpcyBzYW1wbGUsIGF0IHRoZSBpbml0aWFsIHNpdHVhdGlvbiwgdGhlIFVuaXRlZCBTdGF0ZXMgb2YgSk9JIGlzIHNlcGFyYWJsZS4gRm9yIGV4YW1wbGUsIGlmIG9uZSBncm91cHMgdGhlIGNpdGllcyAxLCAyLCAzIGFuZCA0IGFzIEdyb3VwIFggYW5kIHRoZSBjaXR5IDUgYXMgR3JvdXAgWSwgdGhlIGNvbmRpdGlvbnMgb2Ygc2VwYXJhYmlsaXR5IGFyZSBzYXRpc2ZpZWQuPFwvcD5cclxuXHJcbjxwPklmIE1yLiBLIG1lcmdlcyB0aGUgc3RhdGUgMyBhbmQgdGhlIHN0YXRlIDQsIHRoZSBVbml0ZWQgU3RhdGVzIG9mIEpPSSBiZWNvbWVzIG5vdCBzZXBhcmFibGUuIFNvIHRoZSBhbnN3ZXIgaXMgMS48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHA+SW4gdGhpcyBzYW1wbGUsIGF0IHRoZSBpbml0aWFsIHNpdHVhdGlvbiwgdGhlIFVuaXRlZCBTdGF0ZXMgb2YgSk9JIGlzIG5vdCBzZXBhcmFibGUuIFNvIHRoZSBhbnN3ZXIgaXMgMC48XC9wPlxyXG4ifV0=

출처

Camp > JOI Spring Training Camp > JOI 2018/2019 Spring Training Camp 4-2번

  • 문제를 번역한 사람: ho94949

채점 및 기타 정보

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