시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 1 1 50.000%

문제

Now that we understand (from the previous problem) how fake news spreads through a social network, we can try to leverage this knowledge to create the perfect piece of fake news to reach everyone in the social network. For the context of this problem, designing a piece of news means choosing the best ci, which are now allowed to be fractional numbers.

The model will be exactly the same as in the previous problem (so make sure you have at least read that problem), with two exceptions: (1) The content description of the news story you create (the ci) can be floating point numbers now. (2) The fake news piece can start at multiple individuals, which you (the fake news spammer) get to choose. Note that it must be the same piece of fake news that you start at all these individuals.

In some settings, it will be impossible to create a single piece of fake news that everyone will like; you should note when that happens. Otherwise, output the smallest number of individuals you need to start your fake news piece at to reach everyone.

입력

The first line is the number K of input data sets, followed by K data sets, each of the following form:

The input format is the same as for the previous problem, except you will not be given a line describing a piece of fake news (since you are supposed to create it).

출력

For each data set, output “Data Set x:” on a line by itself, where x is its number. Then, on a line by itself, output the minimum number of people you need to start your fake news at to reach everyone. If it is impossible to reach everyone, output “Impossible” instead.

Each data set should be followed by a blank line.

예제 입력 1

2
6 3
3 2 1 6 2 2 3
0 0 0 0 3 4 1 3
4 0 0 4 3 2 1 5
-2 1 1 1 2 2 5
9 -1 2 15 2 3 4
0 0 0 0 0
3 2
1 1 1 2 2 3
1 0 1 2 3 1
0 1 1 2 2 1

예제 출력 1

Data Set 1:
2

Data Set 2:
Impossible