問題文

$x$ 個の青い星と $y$ 個の赤い星があります。また、$m$ 個の辺があり、各辺は青い星と赤い星を結びます。どの星も少なくとも $1$ つの星と隣接していることが保証されます。また、複数の辺が同じ青い星と赤い星の組を結ぶ場合があることに注意してください。

少なくとも $\left\lceil\frac{x+y}{2}\right\rceil$ 個の星が属し、以下の条件を満たす集合を選びたいです。

• 集合に属する任意の青い星について、その星と隣接して、かつ集合に属する赤い星の個数は奇数である。

そのような集合を $1$ つ出力してください。なお、条件を満たす集合は必ず存在することが証明できます。

入力

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

$x\ y\ m$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_m,v_m$

$u_i,v_i$ は $u_i$ 番目の青い星と $v_i$ 番目の赤い星がつながっていることを表す。

• 入力は全て整数
• $1\le \sum x,y,m\le 10^5$
• $x,y,m\geq 1$
• $1\leq u_i\leq x$
• $1\leq v_i\leq y$

出力

各テストケースについて、以下の形式で出力せよ。条件を満たす集合が複数存在する場合、そのうちのどれを出力しても正解となる。

出力する集合に属する青い星の番号を $a_1,a_2,\dots,a_{k_1}$ 、赤い星の番号を $b_1,b_2,\dots,b_{k_2}$ とすると、出力の形式は以下のようになる。

$k_1=0$ または $k_2=0$ の場合は、対応する星の番号の行を空行にしても出力しなくてもよい。

$k_1\ k_2$
$a_1\ a_2\ \dots\ a_{k_1}$
$b_1\ b_2\ \dots\ b_{k_2}$

サンプル

4
1 1 1
1 1
3 3 6
1 1
1 1
3 1
2 3
3 2
3 3
2 3 4
1 1
1 2
2 1
2 3
8 6 10
1 1
1 2
1 3
2 1
3 3
4 4
5 5
6 6
7 2
8 5

1 1
1
1

2 3
1 3
1 2 3

2 1
2 1
1

4 6
1 2 3 4
6 5 4 3 2 1