M. Sculk Sensors
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Steve has found the perfect location to build his next megabase! Unfortunately, the area he wants to build in is currently occupied by a large network of sculk. Since Steve is busy with collecting materials for his base, he needs your help removing all of the sculk in a safe manner.

The sculk network can be represented by a graph of $$$n$$$ nodes connected by $$$m$$$ edges, where each node is either a sculk sensor (type $$$1$$$) or a sculk shrieker (type $$$2$$$). Initially, all sensors and shriekers are part of a single connected component.

To destroy the sculk network, you can remove nodes one at a time. When a node is removed, all edges connected to that node are removed as well. However, any sensors that were directly adjacent to the removed node enter an activated state. If a shrieker is directly connected to an activated sensor at any moment in time, a Warden will spawn, and the entire location must be evacuated! The sculk network is fully cleared once all nodes have been removed.

Output any node removal order that can be used to clear out the sculk network without spawning a Warden, or report that it is not possible.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 1000)$$$. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 2 \cdot 10^5, n-1 \leq m \leq \min(2 \cdot 10^5, \frac{n(n-1)}2))$$$ — the number of nodes and edges, respectively.

The next line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ $$$(a_i \in \{1, 2\})$$$ — the type of each node, either being a sensor ($$$1$$$) or shrieker ($$$2$$$).

The next $$$m$$$ lines each contain two integers $$$u$$$ and $$$v$$$ $$$(1 \leq u, v, \leq n, u \neq v)$$$ — denoting an edge connecting nodes $$$u$$$ and $$$v$$$.

It is guaranteed that all edges are pairwise distinct, and the graph specified in the input is a single connected component.

It is guaranteed that neither the sum of $$$n$$$ nor the sum of $$$m$$$ exceeds $$$2 \cdot 10^5$$$ across all test cases.

—

Tests in subtasks are numbered from $$$1$$$ — $$$20$$$ with samples skipped. Each subtask is worth $$$5$$$ points.

Tests $$$1$$$ — $$$6$$$ satisfy $$$N, M \leq 20$$$ (note: no additional constraint on sum of $$$N$$$ or $$$M$$$).

Tests $$$7$$$ — $$$8$$$ satisfy $$$N, M \leq 200$$$ (note: no additional constraint on sum of $$$N$$$ or $$$M$$$).

Tests $$$9$$$ — $$$20$$$ satisfy no additional constraints.

Output

For each test case, output a permutation of length $$$n$$$, indicating a valid node removal order that can clear the sculk network without spawning any Wardens.

If there are multiple possible orderings, output any valid ordering.

If it is impossible to accomplish the task, output $$$-1$$$ instead.

Example
Input
4
3 2
2 2 2
1 2
2 3
3 2
2 1 2
1 2
2 3
3 2
1 2 1
1 2
2 3
4 5
1 1 2 2
1 2
1 3
1 4
2 3
2 4
Output
1 2 3 
2 1 3 
1 2 3 
-1
Note

In the first test case, note that there are no sensors, so you can remove the nodes in any order without triggering any shriekers.

In the second test case, you must remove node $$$2$$$ first, as removing either of the shriekers will trigger the sensor at node $$$2$$$, causing the other shrieker to trigger.

In the third test case, note that although removing node $$$2$$$ triggers both sensors, neither of these sensors will cause a shrieker to activate.

In the fourth test case, it can be shown that it is impossible to remove a node without triggering a shrieker.

—

Problem Idea: pilliamw

Problem Preparation: pilliamw

Occurrences: Novice L, Advanced I