{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"There are **N** islands and **M** bridges. All the bridges are setup between two islands and to pass a bridge you have to give a toll of **$1**. The bridges are built in such a way that there is no more than one path among two islands. Now, you want to visit at least **K** different islands. You may choose the starting island of your choice, but you want to visit at least **K** different islands in minimum cost (starting island is considered to be already visited)."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 10)**, denoting the number of test cases.\n\nEach case starts with two integers **N, M (1 \u0026le; N \u0026le; 10\u003csup\u003e5\u003c/sup\u003e, 0 \u0026le; M \u0026lt; N)**. Each of the next **M** lines contains two integers **u v (1 \u0026le; u, v \u0026le; N, u \u0026ne; v)** meaning that there is a bridge between island **u** and **v**. No bridge will be reported more than once.The next line contains an integer **q (1 \u0026le; q \u0026le; 50000)** denoting the number of queries. Each of the next **q** lines contains one integer **K (1 \u0026le; K \u0026le; 10\u003csup\u003e5\u003c/sup\u003e)**."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number first. Then for each query, print the minimum amount of toll you need to pay to visit at least **K** different islands. If it is not possible, print `impossible`."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n2 1\n1 2\n3\n1\n2\n3\n5 4\n1 2\n2 3\n2 4\n2 5\n2\n3\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1:\n0\n1\nimpossible\nCase 2:\n2\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"1. Dataset is huge, use faster I/O methods.\n2. For the first case, for **K \u003d 1**, which ever island we start with, we visit this. So without giving any toll we can visit one island. For **K \u003d 2**, we choose island 1 to start. So we visit island 2 using the only bridge. So it costs $1. For **K \u003d 3**, as there are only 2 islands in total so we cannot visit 3 islands."}}]}