|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||1024 MB||8||1||1||100.000%|
A company ICPC (International Cable Protection Company) produces a cable protection tool that can be installed in a network switch to monitor whether all cable links connected to it are working properly. Because the protection tool would cause transmission delay, it is not suitable for installation on every switch.
Usually network topology consists of two parts: a backbone and several subnets. The switches on the backbone are linked as a ring structure and each backbone switch is treated as a root of a subnet in which the switches are linked as a tree structure. We call such topology as unicyclic topology. Figure 2 shows an example of a unicyclic topology.
Figure 2: An example of uncyclic topology.
Suppose there are n backbone switches and m subnet switches. The switches are numbered by integers from 0 to m + n − 1. Backbone switches are numbered from 0 to n − 1 in clockwise order and the subnet switches are numbered from n to n + m − 1 where the index of each subnet switch is larger than the index of its parent in the rooted tree structure of the subnet it belongs. Figure 3 shows an example of switch numbering.
Figure 3: An example of switch numbering.
Please write a program for ICPC to decide the minimum number of switches selected for installing cable protection tools that can monitor all the cable links. Figure 4 shows an optimum solution (circled by ellipses) for the given network.
Figure 4: An optimum solution for the given network.
The first line of the input file contains two integers n and m, separated by a space, indicating the numbers of backbone switches and subnet switches respectively. Each of the next n+m lines consists of two integers, separated by a space, indicating the indices of the two end switches of a link.
Output the minimum number of switches selected for installing cable protection tools that can monitor all the cable links.
3 2 0 1 1 2 0 2 1 3 2 4
4 11 0 1 0 3 0 4 0 5 1 2 1 6 2 3 2 9 3 12 6 7 6 8 9 10 10 11 12 13 12 14