시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 128 MB156312417.778%

문제

한 달 가까이 구사과의 이상한 말들을 받아주느라 너무나 힘들었던 캇카흐는, 이제 대담한 복수를 하려고 합니다. 그 복수는 아니나 다를까, 멕카시나의 걸작, 후르츠 치킨을 구사과의 집으로 주문하는 것이죠!

구사과가 사는 곳은 매우 특이한 구조를 가지고 있습니다. 이 곳은 N개의 도시와 (N-1)개의 양방향 도로로 이루어져 있으며, 모든 도시 쌍 간에 그 두 도시를 잇는 경로가 존재합니다. 동쪽에 있는 도시들에는 멕카시나 가게들이 있고, 서쪽에 있는 도시들에는 구사과의 집들(맞아요, 구사과는 집이 여러 채 있는 부자에요!)이 있습니다. 물론 멕카시나도, 구사과의 집도 없는 도시도 있습니다.

그리고 이 곳에는 한 가지 더 특이한 점이 있습니다. 멕카시나가 있는 도시에서 구사과의 집으로 향하는 모든 경로는 어떤 특정한 도로를 지나도록 되어있습니다. 그 도로가 잇는 두 도시에는 멕카시나도, 구사과의 집도 없습니다.

캇카흐는 각 가게의 배달원들에게 연락하여, 그들이 어떻게 움직여야 하는지를 명령하려고 합니다. 구사과에게 들키지 않기 위해, 한 도로에 두 명 이상의 배달원(즉 둘 이상의 후르츠 치킨)이 동시에 있어서는 안 됩니다. 하지만 한 도시에 여러 명의 배달원이 대기하는 것은 가능합니다. 각각의 배달원들은 도로가 겹치지만 않는다면 동시에 이동이 가능합니다. 모든 도로를 지나는 데에는 1만큼의 시간이 걸립니다.

구사과에게 최대한 큰 정신적인 타격을 주기 위해서, 캇카흐는 후르츠 치킨이 서로 다른 구사과의 집으로 배달되기를 원합니다. 즉 어떤 두 치킨이 같은 집으로 배달되어서는 안 됩니다.

결전의 날이 왔습니다. 캇카흐는 모든 멕카시나 가게에 전화를 걸어, 오늘 영업하는 멕카시나 가게의 목록을 알아냈습니다. 캇카흐는 모든 후르츠 치킨이 배달되는 데에 필요한 시간을 최소화하고자 합니다. 구사과의 동네의 구조를 바탕으로, 치킨이 모두 배달되는 최소 시간을 구해주세요!

입력

입력의 첫 번째 줄에는 도시의 수 N, 멕카시나의 가게의 수 W, 그리고 구사과의 집의 수 Z가 주어집니다. (1 ≤ N, W, Z ≤ 106) 도시는 1부터 N까지의 번호가 붙어있으며, 멕카시나 가게가 있는 도시는 1번부터 W번까지이고, 구사과의 집이 있는 도시는 (N-Z+1)번부터 N번까지입니다.

그 뒤의 (N-1)개의 줄에는 구사과의 동네의 구조에 대한 설명이 주어집니다. 각각의 줄에는 1 이상 N 이하의 정수 a, b가 주어집니다. 이는 a번 도시와 b번 도시를 잇는 도로가 있다는 것을 나타냅니다.

그 다음 줄은 오늘 영업중인 멕카시나 가게의 수를 나타내는 1 이상 W 이하의 정수 P (1 ≤ p ≤ min(W, Z))가 주어집니다. 다음 줄에는 1 이상 W 이하의 서로 다른 P개의 정수가 주어집니다. 각각의 정수는 오늘 영업하는 멕카시나 가게가 있는 도시의 번호를 나타냅니다.

출력

첫 번째 줄에 모든 후르츠 치킨이 배달되는 데에 필요한 최소 시간을 출력하세요.

예제 입력 1

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

예제 출력 1

4

힌트

화살표는 치킨의 배달 과정을 나타냅니다. 제자리로 돌아오는 화살표는 배달원이 도로를 이용하기 위해 1의 시간만큼 기다렸음을 나타냅니다.

W3sicHJvYmxlbV9pZCI6Ijc5OTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2YzRcdWI5NzRcdWNlMjAgXHVjZTU4XHVkMGE4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NWMgXHViMmVjIFx1YWMwMFx1YWU0Y1x1Yzc3NCBcdWFkNmNcdWMwYWNcdWFjZmNcdWM3NTggXHVjNzc0XHVjMGMxXHVkNTVjIFx1YjlkMFx1YjRlNFx1Yzc0NCBcdWJjMWJcdWM1NDRcdWM4ZmNcdWIyOTBcdWI3N2MgXHViMTA4XHViYjM0XHViMDk4IFx1ZDc5OFx1YjRlNFx1YzVjOFx1YjM1OCBcdWNlODdcdWNlNzRcdWQ3NTBcdWIyOTQsIFx1Yzc3NFx1YzgxYyBcdWIzMDBcdWIyZjRcdWQ1NWMgXHViY2Y1XHVjMjE4XHViOTdjIFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1YWRmOCBcdWJjZjVcdWMyMThcdWIyOTQgXHVjNTQ0XHViMmM4XHViMDk4IFx1YjJlNFx1Yjk3Y1x1YWU0YywgXHViYTU1XHVjZTc0XHVjMmRjXHViMDk4XHVjNzU4IFx1YWM3OFx1Yzc5MSwmbmJzcDtcdWQ2YzRcdWI5NzRcdWNlMjAgXHVjZTU4XHVkMGE4XHVjNzQ0IFx1YWQ2Y1x1YzBhY1x1YWNmY1x1Yzc1OCBcdWM5ZDFcdWM3M2NcdWI4NWMgXHVjOGZjXHViYjM4XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YzhlMCE8XC9wPlxyXG5cclxuPHA+XHVhZDZjXHVjMGFjXHVhY2ZjXHVhYzAwIFx1YzBhY1x1YjI5NCBcdWFjZjNcdWM3NDAgXHViOWU0XHVjNmIwIFx1ZDJiOVx1Yzc3NFx1ZDU1YyBcdWFkNmNcdWM4NzBcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YzJiNVx1YjJjOFx1YjJlNC4gXHVjNzc0IFx1YWNmM1x1Yzc0MCZuYnNwO05cdWFjMWNcdWM3NTggXHViM2M0XHVjMmRjXHVjNjQwIChOLTEpXHVhYzFjXHVjNzU4IFx1YzU5MVx1YmMyOVx1ZDVhNSBcdWIzYzRcdWI4NWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViYWE4XHViNGUwIFx1YjNjNFx1YzJkYyBcdWMzMGQgXHVhYzA0XHVjNWQwIFx1YWRmOCBcdWI0NTAgXHViM2M0XHVjMmRjXHViOTdjIFx1Yzc4N1x1YjI5NCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTY5XHViMmM4XHViMmU0LiBcdWIzZDlcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjNjNFx1YzJkY1x1YjRlNFx1YzVkMFx1YjI5NCZuYnNwO1x1YmE1NVx1Y2U3NFx1YzJkY1x1YjA5OCZuYnNwO1x1YWMwMFx1YWM4Y1x1YjRlNFx1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1YzExY1x1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViM2M0XHVjMmRjXHViNGU0XHVjNWQwXHViMjk0IFx1YWQ2Y1x1YzBhY1x1YWNmY1x1Yzc1OCBcdWM5ZDFcdWI0ZTQoXHViOWRlXHVjNTQ0XHVjNjk0LCBcdWFkNmNcdWMwYWNcdWFjZmNcdWIyOTQgXHVjOWQxXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWNjNDQgXHVjNzg4XHViMjk0IFx1YmQ4MFx1Yzc5MFx1YzVkMFx1YzY5NCEpXHVjNzc0IFx1Yzc4OFx1YzJiNVx1YjJjOFx1YjJlNC4gXHViYjNjXHViODYwIFx1YmE1NVx1Y2U3NFx1YzJkY1x1YjA5OFx1YjNjNCwgXHVhZDZjXHVjMGFjXHVhY2ZjXHVjNzU4IFx1YzlkMVx1YjNjNCBcdWM1YzZcdWIyOTQgXHViM2M0XHVjMmRjXHViM2M0IFx1Yzc4OFx1YzJiNVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViOWFjXHVhY2UwIFx1Yzc3NCBcdWFjZjNcdWM1ZDBcdWIyOTQgXHVkNTVjIFx1YWMwMFx1YzljMCBcdWIzNTQgXHVkMmI5XHVjNzc0XHVkNTVjIFx1YzgxMFx1Yzc3NCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YmE1NVx1Y2U3NFx1YzJkY1x1YjA5OFx1YWMwMCBcdWM3ODhcdWIyOTQgXHViM2M0XHVjMmRjXHVjNWQwXHVjMTFjIFx1YWQ2Y1x1YzBhY1x1YWNmY1x1Yzc1OCBcdWM5ZDFcdWM3M2NcdWI4NWMgXHVkNWE1XHVkNTU4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWFjYmRcdWI4NWNcdWIyOTQgXHVjNWI0XHViNWE0IFx1ZDJiOVx1YzgxNVx1ZDU1YyBcdWIzYzRcdWI4NWNcdWI5N2MgXHVjOWMwXHViMDk4XHViM2M0XHViODVkIFx1YjQxOFx1YzViNFx1Yzc4OFx1YzJiNVx1YjJjOFx1YjJlNC4gXHVhZGY4IFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM3ODdcdWIyOTQgXHViNDUwIFx1YjNjNFx1YzJkY1x1YzVkMFx1YjI5NCBcdWJhNTVcdWNlNzRcdWMyZGNcdWIwOThcdWIzYzQsIFx1YWQ2Y1x1YzBhY1x1YWNmY1x1Yzc1OCBcdWM5ZDFcdWIzYzQgXHVjNWM2XHVjMmI1XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNlODdcdWNlNzRcdWQ3NTBcdWIyOTQgXHVhYzAxIFx1YWMwMFx1YWM4Y1x1Yzc1OCBcdWJjMzBcdWIyZWNcdWM2ZDBcdWI0ZTRcdWM1ZDBcdWFjOGMgXHVjNWYwXHViNzdkXHVkNTU4XHVjNWVjLCBcdWFkZjhcdWI0ZTRcdWM3NzQgXHVjNWI0XHViNWJiXHVhYzhjIFx1YzZjMFx1YzljMVx1YzVlY1x1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzBcdWI5N2MgXHViYTg1XHViODM5XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU2OVx1YjJjOFx1YjJlNC4gXHVhZDZjXHVjMGFjXHVhY2ZjXHVjNWQwXHVhYzhjIFx1YjRlNFx1ZDBhNFx1YzljMCBcdWM1NGFcdWFlMzAgXHVjNzA0XHVkNTc0LCBcdWQ1NWMgXHViM2M0XHViODVjXHVjNWQwIFx1YjQ1MCBcdWJhODUgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YmMzMFx1YjJlY1x1YzZkMChcdWM5ODkgXHViNDU4IFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWQ2YzRcdWI5NzRcdWNlMjAgXHVjZTU4XHVkMGE4KVx1Yzc3NCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVjNzg4XHVjNWI0XHVjMTFjXHViMjk0IFx1YzU0OCBcdWI0MjlcdWIyYzhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWQ1NWMgXHViM2M0XHVjMmRjXHVjNWQwIFx1YzVlY1x1YjdlYyBcdWJhODVcdWM3NTggXHViYzMwXHViMmVjXHVjNmQwXHVjNzc0IFx1YjMwMFx1YWUzMFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVhYzAwXHViMmE1XHVkNTY5XHViMmM4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViYzMwXHViMmVjXHVjNmQwXHViNGU0XHVjNzQwIFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWFjYjlcdWNlNThcdWM5YzBcdWI5Y2MgXHVjNTRhXHViMjk0XHViMmU0XHViYTc0IFx1YjNkOVx1YzJkY1x1YzVkMCBcdWM3NzRcdWIzZDlcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTY5XHViMmM4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHViM2M0XHViODVjXHViOTdjIFx1YzljMFx1YjA5OFx1YjI5NCBcdWIzNzBcdWM1ZDBcdWIyOTQgMVx1YjljY1x1ZDA3Y1x1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVhYzc4XHViOWJkXHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkNmNcdWMwYWNcdWFjZmNcdWM1ZDBcdWFjOGMgXHVjZDVjXHViMzAwXHVkNTVjIFx1ZDA3MCBcdWM4MTVcdWMyZTBcdWM4MDFcdWM3NzggXHVkMGMwXHVhY2E5XHVjNzQ0IFx1YzhmY1x1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMsIFx1Y2U4N1x1Y2U3NFx1ZDc1MFx1YjI5NCBcdWQ2YzRcdWI5NzRcdWNlMjAgXHVjZTU4XHVkMGE4XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzgmbmJzcDtcdWFkNmNcdWMwYWNcdWFjZmNcdWM3NTggXHVjOWQxXHVjNzNjXHViODVjIFx1YmMzMFx1YjJlY1x1YjQxOFx1YWUzMFx1Yjk3YyBcdWM2ZDBcdWQ1NjlcdWIyYzhcdWIyZTQuJm5ic3A7XHVjOTg5IFx1YzViNFx1YjVhNCBcdWI0NTAgXHVjZTU4XHVkMGE4XHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWM5ZDFcdWM3M2NcdWI4NWMgXHViYzMwXHViMmVjXHViNDE4XHVjNWI0XHVjMTFjXHViMjk0IFx1YzU0OCBcdWI0MjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNiMFx1YzgwNFx1Yzc1OCBcdWIwYTBcdWM3NzQgXHVjNjU0XHVjMmI1XHViMmM4XHViMmU0LiBcdWNlODdcdWNlNzRcdWQ3NTBcdWIyOTQgXHViYWE4XHViNGUwIFx1YmE1NVx1Y2U3NFx1YzJkY1x1YjA5OCBcdWFjMDBcdWFjOGNcdWM1ZDAgXHVjODA0XHVkNjU0XHViOTdjIFx1YWM3OFx1YzViNCwgXHVjNjI0XHViMjk4IFx1YzYwMVx1YzVjNVx1ZDU1OFx1YjI5NCBcdWJhNTVcdWNlNzRcdWMyZGNcdWIwOTggXHVhYzAwXHVhYzhjXHVjNzU4IFx1YmFhOVx1Yjg1ZFx1Yzc0NCBcdWM1NGNcdWM1NDRcdWIwYzhcdWMyYjVcdWIyYzhcdWIyZTQuIFx1Y2U4N1x1Y2U3NFx1ZDc1MFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVkNmM0XHViOTc0XHVjZTIwIFx1Y2U1OFx1ZDBhOFx1Yzc3NCBcdWJjMzBcdWIyZWNcdWI0MThcdWIyOTQgXHViMzcwXHVjNWQwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDVjXHVjMThjXHVkNjU0XHVkNTU4XHVhY2UwXHVjNzkwIFx1ZDU2OVx1YjJjOFx1YjJlNC4gXHVhZDZjXHVjMGFjXHVhY2ZjXHVjNzU4IFx1YjNkOVx1YjEyNFx1Yzc1OCBcdWFkNmNcdWM4NzBcdWI5N2MgXHViYzE0XHVkMGQ1XHVjNzNjXHViODVjLCBcdWNlNThcdWQwYThcdWM3NzQgXHViYWE4XHViNDUwIFx1YmMzMFx1YjJlY1x1YjQxOFx1YjI5NCBcdWNkNWNcdWMxOGMgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU3NFx1YzhmY1x1YzEzOFx1YzY5NCE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIzYzRcdWMyZGNcdWM3NTggXHVjMjE4IE4sIFx1YmE1NVx1Y2U3NFx1YzJkY1x1YjA5OFx1Yzc1OCBcdWFjMDBcdWFjOGNcdWM3NTggXHVjMjE4IFcsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFkNmNcdWMwYWNcdWFjZmNcdWM3NTggXHVjOWQxXHVjNzU4IFx1YzIxOCBaXHVhYzAwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gKDEgJmxlOyBOLCBXLCBaICZsZTsgMTA8c3VwPjY8XC9zdXA+KSBcdWIzYzRcdWMyZGNcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1YjRcdWM3ODhcdWM3M2NcdWJhNzAsJm5ic3A7XHViYTU1XHVjZTc0XHVjMmRjXHViMDk4IFx1YWMwMFx1YWM4Y1x1YWMwMCBcdWM3ODhcdWIyOTQgXHViM2M0XHVjMmRjXHViMjk0Jm5ic3A7MVx1YmM4OFx1YmQ4MFx1ZDEzMCBXXHViYzg4XHVhZTRjXHVjOWMwXHVjNzc0XHVhY2UwLCBcdWFkNmNcdWMwYWNcdWFjZmNcdWM3NTggXHVjOWQxXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWIzYzRcdWMyZGNcdWIyOTQgKE4tWisxKVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwXHVjNzg1XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViNGE0XHVjNzU4IChOLTEpXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFkNmNcdWMwYWNcdWFjZmNcdWM3NTggXHViM2Q5XHViMTI0XHVjNzU4IFx1YWQ2Y1x1Yzg3MFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjMTI0XHViYTg1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCAxIFx1Yzc3NFx1YzBjMSBOIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM4MTVcdWMyMTggYSwgYlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuIFx1Yzc3NFx1YjI5NCBhXHViYzg4IFx1YjNjNFx1YzJkY1x1YzY0MCBiXHViYzg4IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM3ODdcdWIyOTQgXHViM2M0XHViODVjXHVhYzAwIFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHViMDk4XHVkMGMwXHViMGM1XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1Yzc0MCBcdWM2MjRcdWIyOTggXHVjNjAxXHVjNWM1XHVjOTExXHVjNzc4IFx1YmE1NVx1Y2U3NFx1YzJkY1x1YjA5OCBcdWFjMDBcdWFjOGNcdWM3NTggXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCAxIFx1Yzc3NFx1YzBjMSBXIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM4MTVcdWMyMTggUCAoMSAmbGU7IHAgJmxlOyZuYnNwO21pbihXLCBaKSlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IDEgXHVjNzc0XHVjMGMxIFcgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggUFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjODE1XHVjMjE4XHViMjk0IFx1YzYyNFx1YjI5OCBcdWM2MDFcdWM1YzVcdWQ1NThcdWIyOTQgXHViYTU1XHVjZTc0XHVjMmRjXHViMDk4IFx1YWMwMFx1YWM4Y1x1YWMwMCBcdWM3ODhcdWIyOTQgXHViM2M0XHVjMmRjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYzVcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYWE4XHViNGUwIFx1ZDZjNFx1Yjk3NFx1Y2UyMCBcdWNlNThcdWQwYThcdWM3NzQgXHViYzMwXHViMmVjXHViNDE4XHViMjk0IFx1YjM3MFx1YzVkMCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWMxMzhcdWM2OTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1ZDY1NFx1YzBiNFx1ZDQ1Y1x1YjI5NCBcdWNlNThcdWQwYThcdWM3NTggXHViYzMwXHViMmVjIFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYzVcdWIyYzhcdWIyZTQuIFx1YzgxY1x1Yzc5MFx1YjlhY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjRcdWIyOTQgXHVkNjU0XHVjMGI0XHVkNDVjXHViMjk0IFx1YmMzMFx1YjJlY1x1YzZkMFx1Yzc3NCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCAxXHVjNzU4IFx1YzJkY1x1YWMwNFx1YjljY1x1ZDA3YyBcdWFlMzBcdWIyZTRcdWI4MzhcdWM3NGNcdWM3NDQgXHViMDk4XHVkMGMwXHViMGM1XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC83OTkzXC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIyM3B4OyB3aWR0aDo0MDBweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNzk5MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVhc3QtV2VzdCIsImRlc2NyaXB0aW9uIjoiPHA+SW50ZXJuYXRpb25hbCBhZ3JlZW1lbnRzIHNpZ25lZCBieSB0aGUgQXdmdWxseSBWYXN0IFN0YXRlIGltcG9zZSBvbiBpdCB0cmFuc2l0IG9ibGlnYXRpb25zIC0gaXQgaGFzIHRvIGVuYWJsZSB0aGUgdHJhbnNwb3J0IG9mIG51Y2xlYXIgd2FzdGUgZnJvbSBpdHMgZWFzdGVybiBuZWlnaGJvdXJzIHBvd2VyIHBsYW50cyB0byByZWN5Y2xpbmcgZmFjaWxpdGllcyBpbiB0aGUgV2VzdCwgYnkgbWVhbnMgb2YgaXRzIHJhaWx3YXkgc3lzdGVtLiBFY29sb2dpY2FsIHJlYXNvbnMgaW1wb3NlIHN1Y2ggdHJhZmZpYyBvcmdhbml6YXRpb24sIHRoYXQgdGhlIHdhc3RlLWNhcnJ5aW5nIHRyYWlucyBsZWF2ZSB0aGUgdGVycml0b3J5IG9mIHRoZSBzdGF0ZSBhcyBxdWlja2x5IGFzIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5UaGUgcmFpbHdheSBuZXR3b3JrIGluIHRoaXMgY291bnRyeSBoYXMgYSB2ZXJ5IHBlY3VsaWFyIHN0cnVjdHVyZS4gSXQgY29uc2lzdHMgb2YgbiBjaXRpZXMgLSByYWlsd2F5IGp1bmN0aW9ucyBhbmQgbi0xIHR3by13YXkgcmFpbHdheSB0cmFjayBzZWdtZW50cywgY29ubmVjdGluZyB0aGUganVuY3Rpb25zLiBUcmFuc3BvcnQgaXMgcG9zc2libGUgYmV0d2VlbiBlYWNoIHBhaXIgb2YgY2l0aWVzLiBGdXJ0aGVybW9yZSwgdGhlcmUgaXMgYSBzZWN0aW9uIG9mIHRoZSByYWlsd2F5IHRyYWNrLCB3aG9zZSBlbmRzIGFyZSBub3QgYm9yZGVyIGNpdGllcyBhbmQgZXZlcnkgY29ubmVjdGlvbiBmcm9tIHRoZSBlYXN0ZXJuIHRvIHRoZSB3ZXN0ZXJuIGJvcmRlciBoYXMgdG8gbGVhZCB0aHJvdWdoIHRoYXQgdmVyeSBzZWN0aW9uLjxcL3A+XHJcblxyXG48cD5BbGwgd2FzdGUtY2FycnlpbmcgdHJhaW5zIGFycml2ZSBhdCB0aGUgZWFzdGVybiBib3JkZXIgb24gdGhlIHNhbWUgZGF5LCBiZWZvcmUgZGF3biwgYXQgZGlzdGluY3QgY2hlY2twb2ludHMsIGhvd2V2ZXIuIEZvciBzYWZldHkgcmVhc29ucyB0aGUgdHJhaW5zIG9ubHkgbW92ZSBkdXJpbmcgdGhlIGRheS4gT25seSBhIHNpbmdsZSB3YXN0ZS1jYXJyeWluZyB0cmFpbiBjYW4gbW92ZSBvbiBhIGdpdmVuIHRyYWNrIHNlY3Rpb24gYXQgYSB0aW1lLCBidXQgYW4gdW5saW1pdGVkIGFtb3VudCBvZiB0aGVtIGNhbiB3YWl0IGF0IGEganVuY3Rpb24uIEl0IHRha2VzIG9uZSBkYXkgZm9yIGEgdHJhaW4gdG8gdHJhdmVyc2UgYSBzZWN0aW9uIG9mIHRoZSB0cmFjay4gVGhlIHRyYWZmaWMgaGFzIHRvIGJlIG9yZ2FuaXplZCBpbiBzdWNoIGEgd2F5LCB0aGF0IGFsbG93cyBlYWNoIHdhc3RlLWNhcnJ5aW5nIHRyYWluIHRvIHJlYWNoIGEgZGlzdGluY3QgZGVzdGluYXRpb24gb24gdGhlIHdlc3Rlcm4gYm9yZGVyLjxcL3A+XHJcblxyXG48cD5Ib3cgbWFueSBkYXlzLCBhdCBsZWFzdCwgZG8gdGhlIHdhc3RlLWNhcnJ5aW5nIHRyYWlucyBoYXZlIHRvIHNwZW5kIG9uIHRoZSB0ZXJyaXRvcnkgb2YgdGhlIEF3ZnVsbHkgVmFzdCBTdGF0ZT88XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIHdyaXRlIGEgcHJvZ3JhbW1lIHdoaWNoOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0IGEgZGVzY3JpcHRpb24gb2YgdGhlIHJhaWx3YXkgbmV0d29yayBhbmQgYm9yZGVyIGNoZWNrcG9pbnRzIGF0IHdoaWNoIHRoZSB3YXN0ZS1jYXJyeWluZyB0cmFpbnMgaGF2ZSBhcnJpdmVkLDxcL2xpPlxyXG5cdDxsaT5maW5kcyB0aGUgbWluaW1hbCBudW1iZXIgb2YgZGF5cyB0aGUgdHJhbnNpdCBoYXMgdG8gbGFzdCw8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRoZSBzb2x1dGlvbiB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgMSAmbGU7IG4sIHcsIHogJmxlOyAxMDxzdXA+NjxcL3N1cD4sIG4gJmdlOyB3K3orMiwgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuIG4gZGVub3RlcyB0aGUgbnVtYmVyIG9mIGp1bmN0aW9ucyAod2hpY2ggYXJlIGxhYmVsbGVkIHdpdGggMSwmaGVsbGlwOyxuKSwgd2hpbGUgdyBhbmQgeiBkZW5vdGUgdGhlIG51bWJlciBvZiBib3JkZXIgY2hlY2twb2ludHMgb24gdGhlIGVhc3Rlcm4gYW5kIHdlc3Rlcm4gYm9yZGVyLCByZXNwZWN0aXZlbHkuIFRoZSBjaGVja3BvaW50cyBvbiB0aGUgZWFzdGVybiBib3JkZXIgYXJlIGxhYmVsbGVkIHdpdGggMSwmaGVsbGlwOyx3LCB3aGlsZSB0aG9zZSBvbiB0aGUgd2VzdGVybiBib3JkZXIgd2l0aCBuLXorMSwmaGVsbGlwOyxuLjxcL3A+XHJcblxyXG48cD5JbiB0aGUgZm9sbG93aW5nIG4tMSBsaW5lcyB0aGVyZSBpcyBhIGRlc2NyaXB0aW9uIG9mIHRoZSByYWlsd2F5IG5ldHdvcmsuIEVhY2ggbGluZSBjb250YWlucyB0d28gZGlzdGluY3QgaW50ZWdlcnMsIDEgJmxlOyBhLCBiICZsZTsgbiwgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiBUaGV5IGRlbm90ZSBqdW5jdGlvbnMgY29ubmVjdGVkIGJ5IGEgc2VjdGlvbiBvZiB0aGUgcmFpbHdheS48XC9wPlxyXG5cclxuPHA+VGhlIChuKzEpJnJzcXVvO3N0IGxpbmUgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBwLCAxICZsZTsgcCAmbGU7IHcsIDEgJmxlOyBwICZsZTsgeiwgZGVub3RpbmcgdGhlIG51bWJlciBvZiB3YXN0ZS1jYXJyeWluZyB0cmFpbnMuIEluIHRoZSBuZXh0IChhbmQgbGFzdCkgbGluZSBvZiB0aGUgaW5wdXQgdGhlcmUgYXJlIHAgZGlzdGluY3QgaW50ZWdlcnMsIGFsbCBvZiB3aGljaCBhcmUgbm90IGdyZWF0ZXIgdGhhbiB3LCBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcy4gVGhlc2UgYXJlIHRoZSBudW1iZXJzIG9mIGNoZWNrcG9pbnRzIG9uIHRoZSBlYXN0ZXJuIGJvcmRlciwgYXQgd2hpY2ggdGhlIHdhc3RlLWNhcnJ5aW5nIHRyYWlucyBoYXZlIGFycml2ZWQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgdGhlIG91dHB1dCBzaG91bGQgY29udGFpbiBleGFjdGx5IG9uZSBpbnRlZ2VyLCBkZW5vdGluZyB0aGUgbWluaW1hbCBhbW91bnQgb2YgZGF5cyB0aGUgd2FzdGUgaGF2ZSB0byBzcGVuZCBvbiB0aGUgdGVycml0b3J5IG9mIHRoZSBzdGF0ZS48XC9wPlxyXG4iLCJoaW50IjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvNzk5M1wvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjNweDsgd2lkdGg6NDAwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIGFycm93cyBkZW5vdGUgdGhlIG1vdmVtZW50IG9mIHRoZSB0cmFpbnMgaW4gY29uc2VjdXRpdmUgZGF5cyBmb3Igb25lIG9mIHRoZSBvcHRpbWFsIG9yZ2FuaXphdGlvbnMgb2YgdGhlIHJhaWx3YXkgdHJhZmZpYyAtIGEgbG9vcCBtZWFucyB0aGF0IG9uIGEgZ2l2ZW4gZGF5IHRoZSB0cmFpbiB3YWl0ZWQgYXQgdGhlIGp1bmN0aW9uLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Polish Olympiad in Informatics > POI 2003/2004 > Stage 3 1번