BaoBao 正在参加一场 Kawa 编程语言的在线考试，考试包含 $n$ 道选择题。这场考试并不简单，因为对于每一道题，BaoBao 都需要从 $10^5$ 个可用选项中选出唯一正确的答案！但不用担心，作为著名项目 open-kdk 的活跃贡献者，BaoBao 显然知道所有题目的正确答案。
尽管 BaoBao 是 Kawa 语言的专家，但考试系统的开发者显然不是软件工程方面的专家。考试系统中存在 $m$ 个 Bug，第 $i$ 个 Bug 可以描述为 $(u_i, v_i)$，这意味着 BaoBao 必须为第 $u_i$ 题和第 $v_i$ 题选择相同的选项（即使他选择的选项是错误的！）。
时间有限，考试必须继续进行。开发者们只有时间修复一个 Bug。现在开发者们想知道，对于所有的 $1 \le i \le m$，如果他们修复了第 $i$ 个 Bug，BaoBao 最多能答对多少道题。请编写一个程序来解决这个问题，以便开发者能够选择一个合适的 Bug 进行修复。
输入格式
输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：
第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 10^5, 1 \le m \le 10^5$)，分别表示题目数量和 Bug 数量。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$)，其中 $a_i$ 表示第 $i$ 题的正确答案。
接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$)，表示第 $i$ 个 Bug。
保证所有测试数据的 $n$ 之和与 $m$ 之和均不超过 $10^6$。
输出格式
对于每组测试数据，输出一行，包含 $m$ 个整数 $c_1, c_2, \dots, c_m$，用空格分隔，其中 $c_i$ 表示如果修复了第 $i$ 个 Bug，BaoBao 最多能答对的题目数量。
请不要在每行末尾输出多余的空格，否则你的答案可能会被判定为错误！
样例
输入格式 1
3 7 5 1 2 1 2 1 2 1 1 2 1 3 2 4 5 6 5 7 3 3 1 2 3 1 2 1 3 2 3 2 3 12345 54321 1 2 1 2 1 1
输出格式 1
6 5 5 5 4 1 1 1 1 1 1
说明
下表解释了第一组样例测试数据。
- “Possible Choices”（可能选择）列表示 BaoBao 可以为每道题选择的一组选项，这组选择能使答对的题目数量达到最大；
- “Correct”（正确数量）列表示使用“Possible Choices”列中提供的选项组合所能答对的题目数量。
| Bug 编号 | Possible Choices | Correct |
|---|---|---|
| 1 | (1, 2, 1, 2, 1, 1, 1) | 6 |
| 2 | (2, 2, 1, 2, 1, 1, 1) | 5 |
| 3 | (1, 1, 1, 2, 1, 1, 1) | 5 |
| 4 | (1, 1, 1, 1, 1, 2, 1) | 5 |
| 5 | (1, 1, 1, 1, 1, 1, 1) | 4 |
对于第二组样例测试数据，无论修复哪个 Bug，BaoBao 都必须为这三道题选择相同的选项。由于每道题的正确答案都不同，BaoBao 最多只能答对 1 道题。
对于第三组样例测试数据，请注意，即使开发者修复了第一个 Bug，第二个 Bug 仍然生效，BaoBao 仍然必须为这两道题选择相同的选项。修复第二个 Bug 的情况也是如此。