No.2900 Star Divine
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もしくは右上の雲マークをクリックしてアカウントを作成してください。