NETADMIN - Smart Network Administrator

The citizens of a small village are tired of being the only inhabitants around without a connection to the Internet. After nominating the future network administrator, his house was connected to the global network. All users that want to have access to the Internet must be connected directly to the admin's house by a single cable (every cable may run underground along streets only, from the admin's house to the user's house). Since the newly appointed administrator wants to have everything under control, he demands that cables of different colors should be used. Moreover, to make troubleshooting easier, he requires that no two cables of the same color go along one stretch of street.

Your goal is to find the minimum number of cable colors that must be used in order to connect every willing person to the Internet.


t [the number of test cases, t<=500]
n m k [n <=500 the number of houses (the index of the admin's house is 1)]
[m the number of streets, k the number of houses to connect]
h1 h2 ... hk [a list of k houses wanting to be conected to the network, 2<=hi<=n]
[The next m lines contain pairs of house numbers describing street ends]
e11 e12
e21 e22
em1 em2
[next cases]


For each test case print the minimal number of cable colors necessary to make all the required connections.


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


Illustration to the first example

Warning: large Input/Output data, be careful with certain languages

hide comments
dzyo: 2017-12-04 09:25:42

remember that the size of edge array should be n*n*2 ,or you will got a TLE

Last edit: 2017-12-04 09:36:50
sigma_poet: 2016-01-10 05:48:21

maybe n * n, think it over.

King Pig: 2015-06-02 22:09:29

What is the limit for m, the number of edges?

Last edit: 2015-06-02 22:12:17

Added by:Tomasz Niedzwiecki
Time limit:4.072s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:DASM Programming League 2004, problemset 6