問題一覧 > 通常問題

No.2900 Star Divine

レベル : / AI推定難易度 : 2350 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 23
作問者 : lgswdn / テスター : 👑 獅子座じゃない人
お気に入りにしたユーザー ProblemId : 11296 / 自分の提出
問題文最終更新日: 2024-09-17 22:52:53
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 447 オムニバス (順位表) の他の問題:

Problem Statement

There are $x$ blue stars and $y$ red stars. There are also $m$ edges, each connecting a blue star and a red star. It is guaranteed that every star is adjacent to at least $1$ star. Note that multiple edges may connect the same pair of a blue star and a red star.

We want to choose a set containing at least $\left\lceil\frac{x+y}{2}\right\rceil$ stars that satisfies the following condition.

  • For every blue star in the set, the number of red stars that are adjacent to that star and belong to the set is odd.

Output $1$ such set. It can be proved that a set satisfying the condition always exists.

Input

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Here, $\mathrm{case}_i$ represents the $i$-th test case. Each test case is given in the following format.
$x\ y\ m$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_m,v_m$

$u_i,v_i$ means that the $u_i$-th blue star and the $v_i$-th red star are connected.

  • All input values are integers.
  • $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$

Output

For each test case, output in the following format. If there are multiple sets satisfying the condition, any of them will be accepted.

Let $a_1,a_2,\dots,a_{k_1}$ be the indices of the blue stars in the set you output, and $b_1,b_2,\dots,b_{k_2}$ be the indices of the red stars in it. The output format is as follows.

If $k_1=0$ or $k_2=0$, the line of the corresponding star indices may be left empty or omitted.

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

Sample

Sample 1
Input
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
Output
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

In the first test case, there are $2$ possible sets satisfying the condition.

  • Take blue star $1$ and red star $1$. In this case, the only blue star in the set is $1$, and it is adjacent to $1$ red star in the set, so the condition is satisfied.
  • Take only red star $1$. In this case, there are no blue stars in the set, so the condition is satisfied.

Regarding the output, you do not need to insert blank lines between test cases.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。