题目背景

小 D 在 NOIP 2025 的清仓甩卖非常成功的甩卖了自己的分数，于是他决定继续追忆一下清仓甩卖。

题目描述

给定一张 $n$ 个点 $m$ 条边的无向图，无重边自环。

边被染成三种颜色，分别为红色，绿色，蓝色。

给定 $r,g,b$，满足 $r+g+b=n-1$，请你找出这张图的一个恰好有 $r$ 条红边，$g$ 条绿边，$b$ 条蓝边的生成树。或报告这样的树不存在。

输入格式

从文件 _sale.in_ 中读入数据。

本题有多组测试数据。

第一行输入一个整数 $T$ 表示测试数据组数。（$1 \le T \le 10$）。

对于每组数据：

第一行输入两个整数 $n,m$，表示这张图点和边的数量（$1 \le n \le 2000, 1 \le m \le 10^4$）。

第二行输入三个整数 $r,g,b$，表示每种边所需的数量（$0 \le r,g,b < n$）。

接下来 $m$ 行，每行输入三个整数 $u_i, v_i, w_i$，分别表示第 $i$ 条边连接的两个节点和这条边的颜色。

保证输入的图无重边，无自环。

• $1 \le u_i, v_i \le n$
• $u_i \ne v_i$
• $\forall i \ne j, \{u_i, v_i\} \ne \{u_j, v_j\}$
• $w_i \in \{0, 1, 2\}$

其中，$0, 1, 2$ 分别对应 $r, g, b$ 三种颜色。

输出格式

输出到文件 _sale.out_ 中。

对于每组数据：

若不存在满足条件的生成树，输出 -1。

否则输出 $n-1$ 行，每行输出两个整数，表示一条生成树上的边，输出时 $(u, v)$ 和 $(v, u)$ 被视作同一条边。

答案可能不唯一，你只需要输出任意一组解。

注意：如果你正确判断了是否存在解，但没有给出一组合法的构造方案，你可以获得该测试点 $25 \%$ 的分数。在该情况下，你需要输出原图的任意一棵生成树。

程序测试方式

试题目录下的 checker.cpp 可以用于测试选手输出的正确性，最终测试时所使用的 checker 与该参考实现有所不同，因此选手解法不应依赖该 checker。

选手可在本题目录下使用如下命令编译得到可执行程序：

g++ checker.cpp -o checker -std=c++14 -O2 -static

鉴于 Windows 系统与 NOI Linux 系统的编译命令差异，在 Windows 环境下，你可以使用如下命令编译得到可执行程序：

g++ checker.cpp -o checker.exe -std=c++14 -O2

对于编译得到的可执行程序，你可以使用如下命令运行可执行程序：

./checker sale.in sale.out sale.ans

鉴于 Windows 系统与 NOI Linux 系统的编译命令差异，在 Windows 环境下，你可以使用如下命令运行可执行程序：

checker.exe sale.in sale.out sale.ans

可执行文件将输出以下格式的数据至标准输出：

第一行包含一个字符串，表示测试的结果。其中，

· ok. 表示选手返回的结果正确。

· wrong answer. 表示选手对解的存在性判断错误。

· points 0.25 partial. 表示选手的方案构造错误，但无解判断正确，可以获得 $25\%$ 的分数。

样例 1 输入

3
4 4
1 1 1
1 2 0
2 3 1
3 4 2
4 1 0
4 4
1 1 1
1 2 0
2 3 1
3 1 2
4 1 0
2 1
1 0 0
1 2 1

样例 1 输出

1 2
2 3
3 4
2 3
3 1
4 1
-1

样例 2

见选手目录下的 _sale/sale2.in_ 与 _sale/sale2.ans_。

样例 3

见选手目录下的 _sale/sale3.in_ 与 _sale/sale3.ans_。

说明/提示

对于全部数据：

$1 \le T \le 10, 2 \le n \le 2000, 1 \le m \le 10^4$，$0 \le r, g, b < n, r + g + b = n - 1$。