시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 188 89 69 46.000%

문제

한동이는 경상도내를 돌아다니면서 열심히 일하는 영업사원이다. 예전에는 자기가 원하는 도시만 골라서 다닐 수 있었지만 시대가 바뀌어서 이제 그렇게는 하지 못하게 되었다. 시대가 바뀜에 따라, 한동이는 회사에서 돌아야 할 도시의 목록을 받고, 그 목록대로 도시를 여행한다. 회사에서 주는 여행지 목록은 정말 안타깝게도 최적화되어 있지가 않다. 여행을 떠나기 전에 한동이는 모든 도시를 방문하는데 걸리는 최소의 시간을 알고싶어하는데, 한동이는 경영학과라 컴퓨터를 하지 못 하기 때문에 여러분이 한동이를 도와주자.

포항 시내의 도시들은 1부터 n까지 번호 지어져 있다. 한동이는 항상 포항시청에서 여행을 시작하고, 포항시청의 번호는 항상 1번이다. 모든 도시들은 양방향 도로로 연결되어있는데 한 도시에서 바로 길이 이어져있는 다른 도시로 이동하는데는 항상 1의 시간이 걸린다. 포항시청에서는 어떤 도시든지 갈 수 있다. 또한 포항의 도로는 굉장히 잘 되어있어서 도로끼리 사이클을 만들지 않는다.

여러분의 목표는 한동이가 모든 도시를 방문하는데 걸리는 최소의 시간을 출력하는 것이다.

입력

입력의 첫 줄에는 포항에 있는 도시의 숫자 n이 주어진다. 1 ≤ n ≤ 30,000. 

다음 n-1줄에는 도시를 잇는 도로가 주어진다. 각 줄에는 정수 a와 b가 주어진다. 이는 a도시와 b도시를 잇는 도로가 존재한다는 의미이다. (1 ≤ a,b ≤ n; a≠b)

n+1번째 줄에는 정수 m이 주어지는데, 이는 한동이가 방문해야 할 도시의 숫자를 의미한다. 1 ≤ m ≤ 5,000 그 후 m개의 줄에는 한 줄에 하나씩 한동이가 방문해야 할 도시의 숫자가 순서대로 주어진다.

출력

첫 줄에 한동이가 방문해야 할 모든 도시를 방문 할 수 있는 최소 시간을 출력한다.

예제 입력 1

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

예제 출력 1

7
W3sicHJvYmxlbV9pZCI6IjgwMTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NWNcdWIzZDlcdWM3NzRcdWIyOTQgXHVjNjAxXHVjNWM1XHVjMGFjXHVjNmQwISIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNTVjXHViM2Q5XHVjNzc0XHViMjk0IFx1YWNiZFx1YzBjMVx1YjNjNFx1YjBiNFx1Yjk3YyBcdWIzY2NcdWM1NDRcdWIyZTRcdWIyYzhcdWJhNzRcdWMxMWMgXHVjNWY0XHVjMmVjXHVkNzg4IFx1Yzc3Y1x1ZDU1OFx1YjI5NCBcdWM2MDFcdWM1YzVcdWMwYWNcdWM2ZDBcdWM3NzRcdWIyZTQuIFx1YzYwOFx1YzgwNFx1YzVkMFx1YjI5NCBcdWM3OTBcdWFlMzBcdWFjMDAgXHVjNmQwXHVkNTU4XHViMjk0IFx1YjNjNFx1YzJkY1x1YjljYyBcdWFjZThcdWI3N2NcdWMxMWMgXHViMmU0XHViMmQwIFx1YzIxOCBcdWM3ODhcdWM1YzhcdWM5YzBcdWI5Y2MgXHVjMmRjXHViMzAwXHVhYzAwIFx1YmMxNFx1YjAwY1x1YzViNFx1YzExYyBcdWM3NzRcdWM4MWMgXHVhZGY4XHViODA3XHVhYzhjXHViMjk0IFx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NThcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0LiBcdWMyZGNcdWIzMDBcdWFjMDAgXHViYzE0XHViMDFjXHVjNWQwIFx1YjUzMFx1Yjc3YywgXHVkNTVjXHViM2Q5XHVjNzc0XHViMjk0IFx1ZDY4Y1x1YzBhY1x1YzVkMFx1YzExYyBcdWIzY2NcdWM1NDRcdWM1N2MgXHVkNTYwIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWJhYTlcdWI4NWRcdWM3NDQgXHViYzFiXHVhY2UwLCBcdWFkZjggXHViYWE5XHViODVkXHViMzAwXHViODVjIFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM1ZWNcdWQ1ODlcdWQ1NWNcdWIyZTQuIFx1ZDY4Y1x1YzBhY1x1YzVkMFx1YzExYyBcdWM4ZmNcdWIyOTQgXHVjNWVjXHVkNTg5XHVjOWMwIFx1YmFhOVx1Yjg1ZFx1Yzc0MCBcdWM4MTVcdWI5ZDAgXHVjNTQ4XHVkMGMwXHVhZTVkXHVhYzhjXHViM2M0IFx1Y2Q1Y1x1YzgwMVx1ZDY1NFx1YjQxOFx1YzViNCBcdWM3ODhcdWM5YzBcdWFjMDAgXHVjNTRhXHViMmU0LiBcdWM1ZWNcdWQ1ODlcdWM3NDQgXHViNWEwXHViMDk4XHVhZTMwIFx1YzgwNFx1YzVkMCBcdWQ1NWNcdWIzZDlcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWJjMjlcdWJiMzhcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjNTRjXHVhY2UwXHVjMmY2XHVjNWI0XHVkNTU4XHViMjk0XHViMzcwLCBcdWQ1NWNcdWIzZDlcdWM3NzRcdWIyOTQgXHVhY2JkXHVjNjAxXHVkNTU5XHVhY2ZjXHViNzdjIFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1Yjk3YyBcdWQ1NThcdWM5YzAgXHViYWJiIFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjNWVjXHViN2VjXHViZDg0XHVjNzc0IFx1ZDU1Y1x1YjNkOVx1Yzc3NFx1Yjk3YyBcdWIzYzRcdWM2NDBcdWM4ZmNcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1ZDNlY1x1ZDU2ZCBcdWMyZGNcdWIwYjRcdWM3NTggXHViM2M0XHVjMmRjXHViNGU0XHVjNzQwIDFcdWJkODBcdWQxMzAgblx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzggXHVjOWMwXHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVkNTVjXHViM2Q5XHVjNzc0XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWQzZWNcdWQ1NmRcdWMyZGNcdWNjYWRcdWM1ZDBcdWMxMWMgXHVjNWVjXHVkNTg5XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWNlMCwgXHVkM2VjXHVkNTZkXHVjMmRjXHVjY2FkXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCBcdWQ1NmRcdWMwYzEgMVx1YmM4OFx1Yzc3NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1YjRlNFx1Yzc0MCBcdWM1OTFcdWJjMjlcdWQ1YTUgXHViM2M0XHViODVjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNFx1Yzc4OFx1YjI5NFx1YjM3MCBcdWQ1NWMgXHViM2M0XHVjMmRjXHVjNWQwXHVjMTFjIFx1YmMxNFx1Yjg1YyBcdWFlMzhcdWM3NzQgXHVjNzc0XHVjNWI0XHVjODM4XHVjNzg4XHViMjk0IFx1YjJlNFx1Yjk3OCBcdWIzYzRcdWMyZGNcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0XHViMzcwXHViMjk0IFx1ZDU2ZFx1YzBjMSAxXHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjNzhcdWI5YjBcdWIyZTQuIFx1ZDNlY1x1ZDU2ZFx1YzJkY1x1Y2NhZFx1YzVkMFx1YzExY1x1YjI5NCBcdWM1YjRcdWI1YTQgXHViM2M0XHVjMmRjXHViNGUwXHVjOWMwIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTBcdWQ1NWMgXHVkM2VjXHVkNTZkXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YjI5NCBcdWFkNDlcdWM3YTVcdWQ3ODggXHVjNzk4IFx1YjQxOFx1YzViNFx1Yzc4OFx1YzViNFx1YzExYyBcdWIzYzRcdWI4NWNcdWIwN2NcdWI5YWMgXHVjMGFjXHVjNzc0XHVkMDc0XHVjNzQ0IFx1YjljY1x1YjRlNFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzVlY1x1YjdlY1x1YmQ4NFx1Yzc1OCBcdWJhYTlcdWQ0NWNcdWIyOTQgXHVkNTVjXHViM2Q5XHVjNzc0XHVhYzAwIFx1YmFhOFx1YjRlMCBcdWIzYzRcdWMyZGNcdWI5N2MgXHViYzI5XHViYjM4XHVkNTU4XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWNkNWNcdWMxOGNcdWM3NTggXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQzZWNcdWQ1NmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWMyMmJcdWM3OTAgblx1Yzc3NCZuYnNwO1x1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsxICZsZTsgbiAmbGU7IDMwLDAwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIG4tMVx1YzkwNFx1YzVkMFx1YjI5NCBcdWIzYzRcdWMyZGNcdWI5N2MgXHVjNzg3XHViMjk0IFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODE1XHVjMjE4IGFcdWM2NDAgYlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjI5NCBhXHViM2M0XHVjMmRjXHVjNjQwIGJcdWIzYzRcdWMyZGNcdWI5N2MgXHVjNzg3XHViMjk0IFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTRcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LiZuYnNwOygxICZsZTsgYSxiICZsZTsgbjsgYSZuZTtiKTxcL3A+XHJcblxyXG48cD5uKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxNVx1YzIxOCBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCwgXHVjNzc0XHViMjk0IFx1ZDU1Y1x1YjNkOVx1Yzc3NFx1YWMwMCBcdWJjMjlcdWJiMzhcdWQ1NzRcdWM1N2MgXHVkNTYwIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiAxICZsZTsgbSAmbGU7IDUsMDAwJm5ic3A7XHVhZGY4IFx1ZDZjNCBtXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWQ1NWNcdWIzZDlcdWM3NzRcdWFjMDAgXHViYzI5XHViYjM4XHVkNTc0XHVjNTdjIFx1ZDU2MCBcdWIzYzRcdWMyZGNcdWM3NTggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQ1NWNcdWIzZDlcdWM3NzRcdWFjMDAgXHViYzI5XHViYjM4XHVkNTc0XHVjNTdjIFx1ZDU2MCBcdWJhYThcdWI0ZTAgXHViM2M0XHVjMmRjXHViOTdjIFx1YmMyOVx1YmIzOCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWMxOGMgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI4MDEyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQnl0ZWFzYXIgdGhlIFRyYXZlbGxpbmcgU2FsZXNtYW4iLCJkZXNjcmlwdGlvbiI6IjxwPkEgc2FsZXNtYW4gQnl0ZWFzYXIgd29ya3MgaGFyZCB0cmF2ZWxsaW5nIG92ZXIgQnl0ZW90aWEuIEluIHBhc3QgdGltZXMgdHJhdmVsbGluZyBzYWxlc21lbiBjb3VsZCBjaG9vc2Ugb24gdGhlaXIgb3duIHRvd25zIHRoZXkgd2FudGVkIHRvIHZpc2l0IGFuZCBvcmRlciB0byBkbyBzbywgYnV0IHRob3NlIHRpbWVzIGFyZSBub3cgZ29uZSBmb3JldmVyLiBGcm9tIHRoZSB0aW1lIHRoZSBDZW50cmFsIENvbnRyb2xsaW5nIE9mZmljZSBmb3IgVHJhdmVsbGluZyBTYWxlc21lbiB3YXMgZXN0YWJsaXNoZWQgZXZlcnkgc2FsZXNtYW4gZ2V0cyBmcm9tIHRoZSBPZmZpY2UgYSBsaXN0IG9mIHRvd25zIHRvIHZpc2l0IGFuZCB0aGUgb3JkZXIgb2YgaGlzIHRvdXIuIEFzIGl0IHVzdWFsbHkgaGFwcGVucyB3aXRoIGNlbnRyYWwgb2ZmaWNlcywgdGhlIGltcG9zZWQgb3JkZXIgb2YgdmlzaXRpbmcgdG93bnMgaGFzIG5vdCBtdWNoIGluIGNvbW1vbiB3aXRoIGFuIG9wdGltYWwgb3JkZXIuIEJlZm9yZSBsZWF2aW5nIGZvciBoaXMgdG91ciBCeXRlYXNhciB3b3VsZCBsaWtlIHRvIGtub3cgYXQgbGVhc3QgaG93IG11Y2ggdGltZSBpdCB3aWxsIHRha2UgaGltIHRvIHZpc2l0IGFsbCB0aGUgdG93bnMuIEl0IGlzIHlvdXIgdGFzayB0byBjb21wdXRlIHRoaXMuPFwvcD5cclxuXHJcbjxwPlRoZSB0b3ducyBvZiBCeXRlb3RpYSBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIG4uIFRoZSBjYXBpdGFsIG9mIEJ5dGVvdGlhIGhhcyB0aGUgbnVtYmVyIDEsIGFuZCB0aGlzIGlzIHRoZSBwbGFjZSBCeXRlYXNhciBzdGFydHMgb24gaGlzIGpvdXJuZXkgZnJvbS4gVGhlIHRvd25zIGFyZSBjb25uZWN0ZWQgYnkgYSBuZXR3b3JrIG9mIHR3by13YXkgcm9hZHMuIEEgdHJpcCBiZXR3ZWVuIHR3byB0b3ducyBkaXJlY3RseSBjb25uZWN0ZWQgYnkgYSByb2FkIGFsd2F5cyB0YWtlcyAxIHVuaXQgb2YgdGltZS4gRnJvbSB0aGUgY2FwaXRhbCBvbmUgY2FuIHJlYWNoIGFueSBvdGhlciBCeXRlb3RpYW4gdG93bi4gSG93ZXZlciwgdGhlIHJvYWQgbmV0d29yayBoYWQgYmVlbiBkZXNpZ25lZCB2ZXJ5IHRocmlmdGlseSwgc28gdGhlIHJvYWRzIG5ldmVyIGZvcm0gY3ljbGVzLjxcL3A+XHJcblxyXG48cD4mbHQ7VGFzayZndDs8YnIgXC8+XHJcbldyaXRlIGEgcHJvZ3JhbSB3aGljaDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCB0aGUgZGVzY3JpcHRpb24gb2YgdGhlIHJvYWQgbmV0d29yayBpbiBCeXRlb3RpYSBhbmQgdGhlIGxpc3Qgb2YgdG93bnMgdGhhdCBCeXRlYXNhciBoYXMgdG8gdmlzaXQsPFwvbGk+XHJcblx0PGxpPmNvbXB1dGVzIHRoZSB0b3RhbCB0aW1lIG9mIEJ5dGVhc2FyJiMzOTtzIHRyaXAsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgcmVzdWx0IHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPkluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCB0aGVyZSBpcyBvbmUgaW50ZWdlciBuIGVxdWFsIHRvIHRoZSBudW1iZXIgb2YgdG93bnMgaW4gQnl0ZW90aWEsIDEgJmxlOyBuICZsZTsgMzAsMDAwLiBJbiB0aGUgZm9sbG93aW5nIG4tMSBsaW5lcyB0aGUgbmV0d29yayBvZiByb2FkcyBpcyBkZXNjcmliZWQuIEluIGVhY2ggb2YgdGhlc2UgbGluZXMgdGhlcmUgYXJlIHR3byBpbnRlZ2VycyBhIGFuZCBiICgxICZsZTsgYSxiICZsZTsgbjsgYSZuZTtiKSwgbWVhbmluZyB0aGF0IHRoZSB0b3ducyBhIGFuZCBiIGFyZSBjb25uZWN0ZWQgYnkgYSByb2FkLiBJbiB0aGUgbGluZSBuKzEgdGhlcmUgaXMgb25lIGludGVnZXIgbSBlcXVhbCB0byB0aGUgbnVtYmVyIG9mIHRvd25zIEJ5dGVhc2FyIHNob3VsZCB2aXNpdCwgMSAmbGU7IG0gJmxlOyA1LDAwMC4gSW4gdGhlIGZvbGxvd2luZyBtIGxpbmVzIHRoZXJlIGFyZSBudW1iZXJzIG9mIHN1Y2Nlc3NpdmUgdG93bnMgb24gQnl0ZWFzYXImIzM5O3Mgcm91dGUgLSBvbmUgbnVtYmVyIHBlciBsaW5lLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiB0aGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiB0aGUgc3RhbmRhcmQgb3V0cHV0IHRoZXJlIHNob3VsZCBiZSBvbmUgaW50ZWdlciBlcXVhbCB0byB0aGUgdG90YWwgdGltZSBvZiBCeXRlYXNhciYjMzk7cyB0cmlwLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=