CF1611E2 Escape The Maze (hard version) （逃离迷宫（困难版））

**此题与 E1 背景设定相同，区别在于问题本身。** Vlad 使用 $n$ 个房间和 $n-1$ 条双向走廊搭建了一个迷宫。迷宫中从任何一个房间 $u$ 都可以通过一连串的走廊到达另一个房间 $v$。因此，所有房间及走廊一起形成了一棵无向树。 他邀请了 $k$ 位朋友一起玩游戏。 他在房间 $1$ 开始游戏，如果他到达了 $1$ 以外的房间，并且**有且仅有**一条走廊通向该房间，那么他就赢了。 他的朋友们被安置在迷宫中不同的房间：编号为 $i$ 的朋友在 $x_i$ 房间，没有两个朋友在同一个房间（即 $\forall i \neq j,x_i \neq x_j$）。在弗拉德获胜之前，如果其中一个朋友在任何房间或走廊遇到弗拉德，那么他的朋友们就赢了。 在一个单位时间里，游戏的每位参与者可以穿过一条走廊。所有参与者**同时**移动。**参与者可以选择不移动。** 每个房间可同时容纳所有参与者。 朋友们知道迷宫的布局，并打算赢得比赛。他们不想花费太多的精力，于是要求您确定他们能否获胜，如果他们能获胜，那么迷宫中必须至少留下多少个人，他们才能一定抓住 Vlad。 换句话说，你需要确定能抓到 Vlad 的朋友的最小子集（按元素个数计算）的元素个数，或者报告这样的子集不存在。

**本题每个测试点包含多组测试数据。** 输入的第一行包含一个整数 $t(1 \le t \le 10^4)$，表示该测试点中的测试数据组数。 **每组测试数据前都有一个空字符串。** 测试数据的第一行包含两个数字 $n,k(1 \le k

输出 $t$ 行，每行包含相应测试用例的答案。 如果 Vlad 无论如何都能赢，则测试用例的答案应为 $-1$ ，否则应为最少的好友数。

### 样例解释与说明 在第一组数据中，即使所有的朋友都留在迷宫里，Vlad 仍然可以获胜。因此，答案是 $-1$。 在第二组数据中，让 $6$ 和 $7$ 房间的朋友离开 Vlad 仍无法获胜。答案是 $2$。 在第三和第四组数据中，只有当 Vlad 的所有朋友都留在迷宫中时，他才能获胜。因此答案为 $1$ 和 $2$。 Translate by DeepL,fixed by [Ascnbeta](https://www.luogu.com.cn/user/767561).