ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Championship 2003

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Non-Yekaterinburg Subway

Time limit: 1.0 second
Memory limit: 64 MB
A little town started to construct a subway. The peculiarity of the town is that it is located on small islands, some of them are connected with tunnels or bridges. The mayor is sure that the subway is to be under the ground, that’s why the project must use the less bridges the better. The only request for the subway is that the townsmen could get by metro (may be with changes) from every island to every island. Fortunately, we know that there is enough tunnels and bridges for it. It was decided to construct as less passages from island to island as possible to save money.
Your task given a town plan to determine the minimal possible number of bridges that is necessary to use in the subway construction.


The first line contains three integers separated with a space: N (the number of islands, 1 ≤ N ≤ 10000), K (the number of tunnels, 0 ≤ K ≤ 12000) and M (the number of bridges, 0 ≤ M ≤ 12000). Then there are K lines; each line consists of two integers — the numbers of islands, connected with the corresponding tunnel. The last M lines define bridges in the same format.


the minimal number of bridges necessary for the subway construction.


6 3 4
1 2
2 3
4 5
1 3
3 4
4 6
5 6
Problem Author: Magaz Asanov (prepared Igor Goldberg)
Problem Source: Ural State University championship, October 25, 2003
To submit the solution for this problem go to the Problem set: 1272. Non-Yekaterinburg Subway