Bubble Cup V9 F Pokermon League challenge

Points: 20

Time limit: 2.5s

Memory limit: 256M

Problem type

Welcome to the world of Pokermon, yellow little mouse-like creatures, who absolutely love playing poker!

Yeah, right…

In the ensuing Pokermon League, there are $N$ $N$ registered Pokermon trainers, and existing trainer teams. Since there is a lot of jealousy between trainers, there are $E$ $E$ pairs of trainers who hate each other. Their hate is mutual, there are no identical pairs among these, and no trainer hates himself (the world of Pokermon is a joyful place!). Each trainer has a wish list of length $L$ $L$ teams he'd like to join. All the teams are divided into two conferences.

Your task is to divide players into teams and the teams into two conferences, so that:

each trainer belongs to exactly one team
no team is in both conferences
total hate between conferences is at least $\frac E 2$ $\frac{E}{2}$
every trainer is in a team from his wish list

Total hate between conferences is calculated as the number of pairs of trainers from teams from different conferences who hate each other.

Input Specification

The first line of input contains $2$ $2$ non-negative integers:

$N$ $N$ - total number of Pokermon trainers
$E$ $E$ - number of pairs of trainers who hate each other

Each Pokermon trainer is represented by a number between $[1, N]$ $[1, N]$ .

The next $E$ $E$ lines contain $2$ $2$ integers $A$ $A$ and $B$ $B$ indicating that Pokermon trainers $A$ $A$ and $B$ $B$ hate each other.

The next $2N$ $2 N$ lines are in the following format:

Starting with Pokermon trainer $1$ $1$ , for every trainer in consecutive order:

first number $L$ $L$ - a size of Pokermon trainers wish list
in the next line are positive integers $t[i]$ $t [i]$ - the teams Pokermon trainer would like to be on.

Each trainer's wish list will not contain repeating teams.

Teams on the wish lists are numbered in such a way that the set of all teams that appear on at least $1$ $1$ wish list is the set of consecutive positive integers $\{1, 2, 3, \dots, T\}$ ${1, 2, 3, \dots, T}$ .

Output Specification

Contains 2 lines:

The first line contains $N$ $N$ numbers, specifying the team every trainer is in. First for trainer $1$ $1$ , then $2$ $2$ , etc.
The second line contains $T$ $T$ numbers where for every team, starting with team $1$ $1$ , there is an integer specifying the conference ( $1$ $1$ or $2$ $2$ ) of that team.

Constraints

$4 \le N \le 50\,000$ $4 \leq N \leq 50 000$
$2 \le E \le 100\,000$ $2 \leq E \leq 100 000$
$16 \le L \le 20$ $16 \leq L \leq 20$
$1 \le t[i] \le T$ $1 \leq t [i] \leq T$
$1 \le T \le 1\,000\,000$ $1 \leq T \leq 1 000 000$
$1 \le A,B \le N$ $1 \leq A, B \leq N$

Sample Input

Copy

4 3
1 2
2 3
4 1
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 15
16
2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 18
16
2 3 4 5 6 7 8 9 10 11 12 13 14 15 18 19
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 19

Sample Output

Copy

1 2 2 3
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

Explanation

Conference $1$ $1$ contains only team $1$ $1$ , and conference $2$ $2$ contains all other teams. Total hate between conferences is $2$ $2$ which is greater than $\frac E 2 = \frac 3 2 = 1.5$ $\frac{E}{2} = \frac{3}{2} = 1.5$ .

Pokermon trainer $1$ $1$ belongs to team $1$ $1$ , trainers $2$ $2$ and $3$ $3$ to team $2$ $2$ and trainer $4$ $4$ to team $3$ $3$ . Other teams are empty but they have been assigned a conference.

Comments

There are no comments at the moment.