A group of meteorologists examines weather changes in the mountains. They have several weather stations installed that measure different quantities.
The stations are divided into highly reliable and less reliable, depending on the equipment of the stations and also their location in mountainous terrain.
Direct connections are established between certain pairs of stations for data exchange. These connections are either one-way or two-way, depending on
Meteorologists want to equip one of the stations with a backup system for the collected data. They have to determine which it will be. They want to choose one of the highly reliable stations. They require that it is a station for which there are as many highly reliable stations as possible from which data can be transferred to the chosen station (even through less reliable routes). Note that data can be transferred from a station S to a station T if and only if there is a sequence of N ≥ 1 stations S1,..., SN such that S1 = S, SN = T and, for all i = 1,..., N − 1, there is a direct connection which allows transferring data from Si to Si+1.
Figure 1. A scheme of weather stations (nodes) and direct connections (directed edges showing direction of possible data transfer). There are 6 highly reliable stations colored in green. If station 5 is chosen for the backup system installation, it can collect data from 5 highly reliable stations (highlighted with orange circles). The same is true for station 6. The other reliable stations do not allow to collect data from more than 4 reliable stations.
You are given lists of highly reliable as well as less reliable weather stations and a list of direct connections between stations. Calculate the maximum number of highly reliable stations that can be covered by the backup system (including the station with the backup system).
The first input line contains three integers N, M, H, where
N is the number of weather stations, M is the number of connections (here we treat each two-way connection as two one-way connections),
and H is the number of highly reliable stations.
The stations are numbered from 1 to N. The highly reliable stations have numbers from 1 to H.
The list of direct connections is on the next M lines.
Each of those lines contains two integers S1, S2 separated by space. These two integers represent a direct connection
for data transfer from S1 to S2. The pairs representing direct connections are listed in random order.
The value of N does not exceed 4×105, the value of M does not exceed 2×106.
The output contains one text line with one integer representing the number of highly reliable weather stations that can transfer data to an optimally selected highly reliable station equipped with the backup system. Note that the chosen station is supposed to be also counted to the output value.
11 19 6 7 4 7 2 2 7 4 2 2 10 4 10 10 8 8 10 10 1 1 10 8 9 9 3 3 9 1 3 1 5 2 11 11 5 5 6 6 11Output
5The data of Example 1 is depicted in Figure 1.
6 10 4 6 5 3 4 2 5 3 1 1 3 3 6 1 6 5 6 4 3 5 2Output
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to the public data set