Dense Enough - Testing Approx Problems | Repovive

1012B. Dense Enough

1s256 MB

You are given a simple undirected graph with $n$ vertices and $m$ edges.

For a non-empty set of vertices $S$ , define its score as:

$\frac{e(S)}{|S|}$

where $e(S)$ is the number of edges with both endpoints inside $S$ .

Let $OPT$ be the maximum possible score over all non-empty sets of vertices.

You do not need to find an optimal set. You only need to output any non-empty set of vertices whose score is at least half of $OPT$ .

In other words, if your chosen set is $S$ , your output is accepted if:

$2 \times \frac{e(S)}{|S|} \ge OPT$

Constraints

$1 \le t \le 5$
$1 \le n \le 1000$
$0 \le m \le 50000$
The sum of $n$ over all test cases is at most $1000$
The sum of $m$ over all test cases is at most $50000$
The graph has no self-loops or multiple edges

Input

The input is given in the following format:

t

\left. \begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times t

Output

For each test case, output a non-empty set of vertices.

First, output an integer $k$ , the number of chosen vertices.

Then output $k$ distinct integers $s_1, s_2, \ldots, s_k$ , the chosen vertices.

The output format is:

\left. \begin{array}{l} k \\ s_1 \quad s_2 \quad \cdots \quad s_k \end{array} \right\} \times t

Samples

Input

Explanation

The chosen set is $\{1,2,3\}$ . It contains $3$ internal edges, so its score is $3/3=1$ .

The set $\{1,2,3,4\}$ has $6$ internal edges and score $6/4$ . Therefore the shown output is not optimal, but it is still good enough because $1$ is at least half of $6/4$ .

Output

3
1 2 3

You are given a simple undirected graph with $n$ vertices and $m$ edges.

For a non-empty set of vertices $S$ , define its score as:

$\frac{e(S)}{|S|}$

where $e(S)$ is the number of edges with both endpoints inside $S$ .

Let $OPT$ be the maximum possible score over all non-empty sets of vertices.

You do not need to find an optimal set. You only need to output any non-empty set of vertices whose score is at least half of $OPT$ .

In other words, if your chosen set is $S$ , your output is accepted if:

$2 \times \frac{e(S)}{|S|} \ge OPT$

$1 \le t \le 5$
$1 \le n \le 1000$
$0 \le m \le 50000$
The sum of $n$ over all test cases is at most $1000$
The sum of $m$ over all test cases is at most $50000$
The graph has no self-loops or multiple edges

The input is given in the following format:

t

\left. \begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times t

For each test case, output a non-empty set of vertices.

First, output an integer $k$ , the number of chosen vertices.

Then output $k$ distinct integers $s_1, s_2, \ldots, s_k$ , the chosen vertices.

The output format is:

\left. \begin{array}{l} k \\ s_1 \quad s_2 \quad \cdots \quad s_k \end{array} \right\} \times t

The chosen set is $\{1,2,3\}$ . It contains $3$ internal edges, so its score is $3/3=1$ .

The set $\{1,2,3,4\}$ has $6$ internal edges and score $6/4$ . Therefore the shown output is not optimal, but it is still good enough because $1$ is at least half of $6/4$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

1012B. Dense Enough

Constraints

Input

Output

Samples

1012B. Dense Enough

Constraints

Input

Output

Samples