시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 61 35 29 61.702%

문제

울산광역시는 큰 도시라 고도로 발달했으면서도 복잡한 교통 체계를 가지고 있다. 울산광역시의 교통 체계는 정류장(정점)과 그 정류장을 잇는 도로(간선)들로 나타낼 수 있다. 정류장과 도로를 모은 그래프는 순환하는 경로가 발생하지 않는 형태이며, 서로 다른 두 정류장을 잇는 경로는 항상 만들 수 있다. 즉, 트리 모양이다.

이번에 교통과에 취직한 윤표는 버스 노선이 너무 많다고 생각해 이를 정리하기로 마음먹었다. 과감하게도, 윤표는 기존에 있던 버스 노선들을 모두 없애 버리고 버스 노선들을 새롭게 구성하려고 한다. 각각의 버스 노선은 다음과 같이 정의할 수 있다.

  1. 출발 정류장과 도착 정류장이 있다.
  2. 출발 정류장에서 도착 정류장에 가기까지 몇 개의 정류장을 정해진 순서대로 경유할 수 있다. 경유지의 수에는 제한이 없으며, 아무 정류장도 경유하지 않고 출발지에서 도착지로 바로 갈 수도 있다. 물론, 경유지를 지나가는 순서도 윤표가 정할 수 있다.
  3. 어떤 버스 노선이 K개의 정류장을 방문하고, 방문하는 정류장들을 순서대로 정류장 1, 정류장 2, … ,정류장 K라고 할 때, 정류장 i(1 ≤ i ≤ K-1)와 정류장 i+1 사이에는 도로가 존재해야 한다. 이때 정류장 i와 i+1을 잇는 도로는 이 버스 노선이 지나가는 도로라고 부른다.
  4. 같은 정류장을 여러 번 방문해서는 안된다. 즉, 출발지와 도착지, 그리고 모든 경유지는 다른 정류장이어야 한다.

윤표는 모든 도로에 적어도 하나 이상의 버스 노선이 지나가도록 버스 노선을 구성하고 싶다. (도로에서 노선이 지나가는 방향은 어떤 방향도 상관없다.) 또한, 윤표는 버스 노선의 개수가 최소화되기를 원한다. 윤표를 도와, 모든 도로에 적어도 하나 이상의 버스 노선이 지나가도록 할 때 버스 노선의 최소 개수를 구하는 프로그램을 작성하자.

입력

첫 번째 줄에 정류장의 수 N(2 ≤ N ≤ 200,000)가 주어지며 정류장은 0부터 N-1까지 고유한 번호를 가진다.

두 번째 줄부터 N번째 줄까지 도로로 연결된 두 정류장 쌍이 주어진다. 같은 도로가 여러 번 주어지지 않는다.

출력

버스 노선을 정리했을 때 노선의 최소 개수를 출력한다.

예제 입력 1

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

예제 출력 1

2

W3sicHJvYmxlbV9pZCI6IjE3ODQyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViYzg0XHVjMmE0IFx1YjE3OFx1YzEyMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNmI4XHVjMGIwXHVhZDExXHVjNWVkXHVjMmRjXHViMjk0IFx1ZDA3MCBcdWIzYzRcdWMyZGNcdWI3N2MgXHVhY2UwXHViM2M0XHViODVjIFx1YmMxY1x1YjJlY1x1ZDU4OFx1YzczY1x1YmE3NFx1YzExY1x1YjNjNCBcdWJjZjVcdWM3YTFcdWQ1NWMmbmJzcDtcdWFkNTBcdWQxYjUgXHVjY2I0XHVhY2M0XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzZiOFx1YzBiMFx1YWQxMVx1YzVlZFx1YzJkY1x1Yzc1OCBcdWFkNTBcdWQxYjUgXHVjY2I0XHVhY2M0XHViMjk0IFx1YzgxNVx1Yjk1OFx1YzdhNShcdWM4MTVcdWM4MTApXHVhY2ZjIFx1YWRmOCBcdWM4MTVcdWI5NThcdWM3YTVcdWM3NDQgXHVjNzg3XHViMjk0IFx1YjNjNFx1Yjg1YyhcdWFjMDRcdWMxMjApXHViNGU0XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM4MTVcdWI5NThcdWM3YTVcdWFjZmMgXHViM2M0XHViODVjXHViOTdjJm5ic3A7XHViYWE4XHVjNzQwIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YjI5NCBcdWMyMWNcdWQ2NThcdWQ1NThcdWIyOTQgXHVhY2JkXHViODVjXHVhYzAwIFx1YmMxY1x1YzBkZFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVkNjE1XHVkMGRjXHVjNzc0XHViYTcwLCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWM4MTVcdWI5NThcdWM3YTVcdWM3NDQgXHVjNzg3XHViMjk0IFx1YWNiZFx1Yjg1Y1x1YjI5NCBcdWQ1NmRcdWMwYzEgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzk4OSwgXHVkMmI4XHViOWFjIFx1YmFhOFx1YzU5MVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViYzg4XHVjNWQwIFx1YWQ1MFx1ZDFiNVx1YWNmY1x1YzVkMCBcdWNkZThcdWM5YzFcdWQ1NWMgXHVjNzI0XHVkNDVjXHViMjk0IFx1YmM4NFx1YzJhNCBcdWIxNzhcdWMxMjBcdWM3NzQgXHViMTA4XHViYjM0IFx1YjljZVx1YjJlNFx1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1NzQmbmJzcDtcdWM3NzRcdWI5N2MmbmJzcDtcdWM4MTVcdWI5YWNcdWQ1NThcdWFlMzBcdWI4NWMgXHViOWM4XHVjNzRjXHViYTM5XHVjNWM4XHViMmU0LiBcdWFjZmNcdWFjMTBcdWQ1NThcdWFjOGNcdWIzYzQsIFx1YzcyNFx1ZDQ1Y1x1YjI5NCBcdWFlMzBcdWM4NzRcdWM1ZDAgXHVjNzg4XHViMzU4IFx1YmM4NFx1YzJhNCBcdWIxNzhcdWMxMjBcdWI0ZTRcdWM3NDQgXHViYWE4XHViNDUwIFx1YzVjNlx1YzU2MCBcdWJjODRcdWI5YWNcdWFjZTAgXHViYzg0XHVjMmE0IFx1YjE3OFx1YzEyMFx1YjRlNFx1Yzc0NCBcdWMwYzhcdWI4NmRcdWFjOGMgXHVhZDZjXHVjMTMxXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmM4NFx1YzJhNCBcdWIxNzhcdWMxMjBcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM4MTVcdWM3NThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWNkOWNcdWJjMWMgXHVjODE1XHViOTU4XHVjN2E1XHVhY2ZjIFx1YjNjNFx1Y2MyOSBcdWM4MTVcdWI5NThcdWM3YTVcdWM3NzQgXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWNkOWNcdWJjMWMgXHVjODE1XHViOTU4XHVjN2E1XHVjNWQwXHVjMTFjIFx1YjNjNFx1Y2MyOSBcdWM4MTVcdWI5NThcdWM3YTVcdWM1ZDAgXHVhYzAwXHVhZTMwXHVhZTRjXHVjOWMwIFx1YmE4NyBcdWFjMWNcdWM3NTggXHVjODE1XHViOTU4XHVjN2E1XHVjNzQ0IFx1YzgxNVx1ZDU3NFx1YzljNCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVhY2JkXHVjNzIwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWNiZFx1YzcyMFx1YzljMFx1Yzc1OCBcdWMyMThcdWM1ZDBcdWIyOTQgXHVjODFjXHVkNTVjXHVjNzc0IFx1YzVjNlx1YzczY1x1YmE3MCwgXHVjNTQ0XHViYjM0IFx1YzgxNVx1Yjk1OFx1YzdhNVx1YjNjNCBcdWFjYmRcdWM3MjBcdWQ1NThcdWM5YzAgXHVjNTRhXHVhY2UwIFx1Y2Q5Y1x1YmMxY1x1YzljMFx1YzVkMFx1YzExYyBcdWIzYzRcdWNjMjlcdWM5YzBcdWI4NWMgXHViYzE0XHViODVjIFx1YWMwOCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWJiM2NcdWI4NjAsIFx1YWNiZFx1YzcyMFx1YzljMFx1Yjk3YyBcdWM5YzBcdWIwOThcdWFjMDBcdWIyOTQgXHVjMjFjXHVjMTFjXHViM2M0IFx1YzcyNFx1ZDQ1Y1x1YWMwMCBcdWM4MTVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNWI0XHViNWE0IFx1YmM4NFx1YzJhNCBcdWIxNzhcdWMxMjBcdWM3NzQgS1x1YWMxY1x1Yzc1OCBcdWM4MTVcdWI5NThcdWM3YTVcdWM3NDQgXHViYzI5XHViYjM4XHVkNTU4XHVhY2UwLCBcdWJjMjlcdWJiMzhcdWQ1NThcdWIyOTQgXHVjODE1XHViOTU4XHVjN2E1XHViNGU0XHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4MTVcdWI5NThcdWM3YTUgMSwgXHVjODE1XHViOTU4XHVjN2E1IDIsICZoZWxsaXA7ICxcdWM4MTVcdWI5NThcdWM3YTUgS1x1Yjc3Y1x1YWNlMCBcdWQ1NjAgXHViNTRjLCBcdWM4MTVcdWI5NThcdWM3YTUgaSgxICZsZTsgaSAmbGU7IEstMSlcdWM2NDAgXHVjODE1XHViOTU4XHVjN2E1IGkrMSBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHViM2M0XHViODVjXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWM4MTVcdWI5NThcdWM3YTUgaVx1YzY0MCBpKzFcdWM3NDQgXHVjNzg3XHViMjk0IFx1YjNjNFx1Yjg1Y1x1YjI5NCZuYnNwO1x1Yzc3NCBcdWJjODRcdWMyYTQgXHViMTc4XHVjMTIwXHVjNzc0IDxzdHJvbmc+XHVjOWMwXHViMDk4XHVhYzAwXHViMjk0PFwvc3Ryb25nPiBcdWIzYzRcdWI4NWNcdWI3N2NcdWFjZTAgXHViZDgwXHViOTc4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFjMTlcdWM3NDAgXHVjODE1XHViOTU4XHVjN2E1XHVjNzQ0IFx1YzVlY1x1YjdlYyBcdWJjODggXHViYzI5XHViYjM4XHVkNTc0XHVjMTFjXHViMjk0IFx1YzU0OFx1YjQxY1x1YjJlNC4gXHVjOTg5LCBcdWNkOWNcdWJjMWNcdWM5YzBcdWM2NDAgXHViM2M0XHVjYzI5XHVjOWMwLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHViYWE4XHViNGUwIFx1YWNiZFx1YzcyMFx1YzljMFx1YjI5NCBcdWIyZTRcdWI5NzggXHVjODE1XHViOTU4XHVjN2E1XHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM3MjRcdWQ0NWNcdWIyOTQgPHN0cm9uZz5cdWJhYThcdWI0ZTAgXHViM2M0XHViODVjXHVjNWQwJm5ic3A7XHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzFcdWM3NTggXHViYzg0XHVjMmE0IFx1YjE3OFx1YzEyMFx1Yzc3NCBcdWM5YzBcdWIwOThcdWFjMDBcdWIzYzRcdWI4NWQ8XC9zdHJvbmc+IFx1YmM4NFx1YzJhNCBcdWIxNzhcdWMxMjBcdWM3NDQgXHVhZDZjXHVjMTMxXHVkNTU4XHVhY2UwIFx1YzJmNlx1YjJlNC4mbmJzcDsoXHViM2M0XHViODVjXHVjNWQwXHVjMTFjIFx1YjE3OFx1YzEyMFx1Yzc3NCBcdWM5YzBcdWIwOThcdWFjMDBcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzQwIFx1YzViNFx1YjVhNCBcdWJjMjlcdWQ1YTVcdWIzYzQgXHVjMGMxXHVhZDAwXHVjNWM2XHViMmU0LikgXHViNjEwXHVkNTVjLCBcdWM3MjRcdWQ0NWNcdWIyOTQgXHViYzg0XHVjMmE0IFx1YjE3OFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjZDVjXHVjMThjXHVkNjU0XHViNDE4XHVhZTMwXHViOTdjIFx1YzZkMFx1ZDU1Y1x1YjJlNC4gXHVjNzI0XHVkNDVjXHViOTdjIFx1YjNjNFx1YzY0MCwgXHViYWE4XHViNGUwIFx1YjNjNFx1Yjg1Y1x1YzVkMCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTU4XHViMDk4IFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWJjODRcdWMyYTQgXHViMTc4XHVjMTIwXHVjNzc0IFx1YzljMFx1YjA5OFx1YWMwMFx1YjNjNFx1Yjg1ZCBcdWQ1NjAgXHViNTRjIFx1YmM4NFx1YzJhNCBcdWIxNzhcdWMxMjBcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1Yjk1OFx1YzdhNVx1Yzc1OCBcdWMyMTggTigyJm5ic3A7JmxlOyZuYnNwO04mbmJzcDsmbGU7IDIwMCwwMDApXHVhYzAwJm5ic3A7XHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwIFx1YzgxNVx1Yjk1OFx1YzdhNVx1Yzc0MCAwXHViZDgwXHVkMTMwIE4tMVx1YWU0Y1x1YzljMCBcdWFjZTBcdWM3MjBcdWQ1NWMgXHViYzg4XHVkNjM4XHViOTdjIFx1YWMwMFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YmM4OFx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzAgXHViM2M0XHViODVjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWI0NTAgXHVjODE1XHViOTU4XHVjN2E1IFx1YzMwZFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWIzYzRcdWI4NWNcdWFjMDAgXHVjNWVjXHViN2VjIFx1YmM4OCZuYnNwO1x1YzhmY1x1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYzg0XHVjMmE0IFx1YjE3OFx1YzEyMFx1Yzc0NCBcdWM4MTVcdWI5YWNcdWQ1ODhcdWM3NDQgXHViNTRjIFx1YjE3OFx1YzEyMFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViOTdjJm5ic3A7XHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCIsInNhbXBsZV9leHBsYWluXzEiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzM3ZDY3M2I2LWM0OWMtNDE4Zi1hMjJiLTI3MjFkNzRjMTU4Y1wvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJoZWlnaHQ6IDE2NXB4OyB3aWR0aDogMzAwcHg7XCIgXC8+PFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMTc4NDIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCdXMgUm91dGUiLCJkZXNjcmlwdGlvbiI6IjxwPlVsc2FuIGlzIGEgYmlnIGNpdHksIGFuZCBidXMgcm91dGVzIGFyZSBjb21wbGljYXRlZC4gWXVucHlvLCB3aG8gZ290IGEgam9iIGF0IHRoZSBUcmFuc3BvcnRhdGlvbiBEaXZpc2lvbiwgZGVjaWRlZCB0byByZWR1Y2UgbWFueSByb3V0ZXMuIFRoZSBleHByZXNzaW9ucyBvZiByb2FkcyBpbiBVbHNhbiBhcmUgZXhwcmVzc2VkIGFzIHN0b3BzIGFuZCByb2FkcyBjb25uZWN0aW5nIHRoZSBzdG9wcy4gVGhlIGdyYXBoIG9mIHRoZSBzdG9wcyBhbmQgdGhlaXIgcm9hZHMgZG9lcyBub3QgaGF2ZSBhIGNpcmN1bGFyIHBhdGgsIGFuZCBhIGJ1cyBsaW5lIGNvbm5lY3RpbmcgdHdvIGRpZmZlcmVudCBzdG9wcyBjYW4gYWx3YXlzIGJlIG1hZGUuIFRoZSBidXMgcm91dGVzLCB3aGljaCBhcmUgdGhlIHBhdGhzIHBhc3NpbmcgdGhyb3VnaCB0aGUgcm9hZHMsIG11c3Qgc2F0aXNmeSB0aGUgZm9sbG93aW5nIGNvbmRpdGlvbnMsIGFuZCBZdW5weW8gd2FudHMgdG8gbWluaW1pemUgdGhlIG51bWJlciBvZiBidXMgcm91dGVzIHRoYXQgc2F0aXNmeSB0aGVzZSBjb25kaXRpb25zLjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlRoZXJlIG11c3QgYmUgYXQgbGVhc3Qgb25lIGJ1cyByb3V0ZSB0aHJvdWdoIGEgcm9hZC48XC9saT5cclxuXHQ8bGk+Q0FOTk9UIG1ha2UgbmV3IHJvYWQuPFwvbGk+XHJcblx0PGxpPlNldmVyYWwgYnVzIHJvdXRlcyBjYW4gcGFzcyBvbiBhIHNpbmdsZSByb2FkLjxcL2xpPlxyXG5cdDxsaT5JdCBkb2VzIG5vdCBtYXR0ZXIgaW4gd2hpY2ggZGlyZWN0aW9uIHRoZSByb3V0ZSBwYXNzZXMuPFwvbGk+XHJcbjxcL29sPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGlzIGdpdmVuIHRoZSBudW1iZXIgb2Ygc3RvcHMgTigyJm5ic3A7JmxlOyZuYnNwO04mbmJzcDsmbGU7IDIwMCwwMDApIGFuZCB0aGUgc3RvcHMgaGF2ZSBhIHVuaXF1ZSBudW1iZXIgZnJvbSAwIHRvIE4tMS48XC9wPlxyXG5cclxuPHA+WW91IHdpbGwgYmUgZ2l2ZW4gdHdvIHBhaXJzIG9mIHN0b3BzIGNvbm5lY3RlZCBieSByb2FkIGZyb20gbGluZSAyIHRvIGxpbmUgTi4mbmJzcDtSb2FkcyBhcmUgbm90IGdpdmVuIGluIGR1cGxpY2F0ZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCBvdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHJvdXRlcyB3aGVuIGFkanVzdGluZyBidXMgcm91dGVzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCIsInNhbXBsZV9leHBsYWluXzEiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzVmNzNjMDU2LTMzNDgtNGJlNy1hNjFlLTJiNzY4MzIyZmQ5ZFwvLVwvcHJldmlld1wvXCIgXC8+PGJyIFwvPlxyXG4mbmJzcDs8XC9wPlxyXG4ifV0=