Coloring Colorable Graphs

Problem code: THREECLR

All submissions for this problem are available.

The Chef has a list of dishes he must prepare and he is able to work on many of them simultaneously (with the help of his employees, of course). For example, he can heat soup, bake a cake, marinate some meat, let some wine aerate, etc. all at the same time since no two of them require a common cooking tool. Unfortunately, his kitchen is dangerously low in its supply of tools and he has no more than one copy of each cooking tool. This means that some dishes cannot be prepared at the same time such as slicing two different cuts of meat since there is only one meat slicer.

So, the Chef has scheduled the preparation of the dishes into rounds. In each round, he and his staff prepare some dishes of which no two require a common cooking tool. For simplicity's sake, he will not start preparing dishes from a certain round until all dishes from the previous round are completed.

The Chef received the orders for today's dishes early in the day and he has had a lot of time to think about how to optimally schedule them. In fact, he even found a way to prepare all of the dishes in only 3 rounds! Unfortunately, he lost the piece of paper that contained this schedule and he has to start preparing dishes right away.

He needs your help and he needs it fast! Your job is to assign, to each dish, a round in the schedule such that no two dishes scheduled in the same round require a common cooking tool. It doesn't matter if it uses more than three rounds. Of course, fewer rounds are preferred, but the Chef would be happy with any schedule right now.

Input

The first line contains in integer T denoting the number of test cases (at most 50). Each test case begins with two integers n and m where n denotes the number of dishes to be prepared and m denotes the number of pairs of dishes that require a common cooking tool. Following this is m lines, each containing two distinct integers u,v between 1 and n. This indicates that dishes u and v require a common cooking tool so they cannot be scheduled in the same round. No pair of dishes will appear more than once in the input.

The input will be such that there is a way to assign each dish to one of three rounds so that no two dishes in the same round require a common cooking tool. Of course, you won't be given this schedule.

Bounds: 1 ? n ? 500 and 0 ? m ? 10,000.

Output

The output for each test case is a single line containing n integers. These integers must be between 1 and n and the i'th such integer indicates the round that dish i is scheduled in. The scheduling must be done so that no two dishes that require a common cooking tool appear in the same round. However, any output that conforms to these constraints will be accepted.

Scoring

The score for a single test case is simply the largest integer that appears in the output for that test case. The total score over all test cases is the sum of the scores for the individual test cases. There are multiple test files, so your final score is the average of the scores over all test files.

Example

Input:
3
4 5
1 2
3 1
1 4
3 2
2 4
10 15
1 2
2 3
3 4
4 5
5 1
6 8
8 10
10 7
7 9
9 6
1 6
2 7
3 8
4 9
5 10
3 2
1 2
2 3

Output:
1 2 3 3
1 2 1 2 3 4 4 3 3 2
1 3 1

Sample Output Score

The score for the first test case is 3 since only three rounds are used. The score for the second test case is 4 since four rounds are used. Note that this is not optimum as the assignment 1 2 3 1 2 2 1 1 3 3 is a valid way to schedule the dishes in only three rounds. Finally, the last test case has score 3. Even though only two rounds are used (rounds 1 and 3), the output specification says that the score will be the largest integer used as a round in the output.

Author: friggstad
Date Added: 5-01-2011
Time Limit: 8 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

i am getting ans as 1 2 1 2 3

shankysodhi @ 2 Feb 2011 12:21 AM

i am getting ans as

1 2 1 2 3 2 1 3 3 2

for 2nd test case 

and

1 2 1

for 3rd

is it correct.....???

if so ..... how come i am getting wrong answer ......

is statement  :  " he even

kirnley @ 2 Feb 2011 01:10 AM

is statement  :  " he even found a way to prepare all of the dishes in only 3 rounds!" true for all values of n??

can i know for which test

kirnley @ 2 Feb 2011 01:27 AM

can i know for which test case my solution fails ?

http://www.codechef.com/viewsolution/441358

even 2nd test case has

reddy4frnds @ 2 Feb 2011 01:23 PM

even 2nd test case has solution 1 2 1 2 3 2 1 3 3 2

and 3rd 1 2 1

if so... I am getting wrong answer for my solution... ??

hey... dont u think the third

gauravsmar8st @ 2 Feb 2011 08:11 PM

hey...

dont u think the third test case can have the output as

1 2 1

1 2 1 2 3 2 1 3 3 2 getting

anksanu1989 @ 2 Feb 2011 08:14 PM 

1 2 1 2 3 2 1 3 3 2

getting this out out for the 2nd test case
getting wrong answer...............

don,t know why this answer fullfills the mentioned requirements


got accepted stupid

anksanu1989 @ 2 Feb 2011 08:32 PM

got accepted

stupid mistake...........:)

i am getting ans as 1 2 1 2 3

paarth @ 2 Feb 2011 08:51 PM

i am getting ans as

1 2 1 2 3 2 3 3 1 1

for 2nd test case 

and

1 2 1

for 3rd

is it correct.....???

if so ..... how come i am getting wrong answer ......

@Ankit Can u help me

paarth @ 2 Feb 2011 08:54 PM

@Ankit Can u help me out....wat was ur mistake...??....

for the same solution , i got

kirnley @ 2 Feb 2011 11:58 PM

for the same solution , i got wrong answer yesterday n today it got accepted.

Am i correct in stating the

johnnykv @ 3 Feb 2011 05:53 AM

Am i correct in stating the the test result for case 3 cannot be "1 3 1"?

No, 1 3 1 is a perfectly

triplem @ 3 Feb 2011 05:58 AM

No, 1 3 1 is a perfectly valid output for the third sample test case.

@admin:- Can we prepare all

saurabheights @ 3 Feb 2011 06:44 PM
@admin:- Can we prepare all of the dishes in only 3 rounds for al test cases?

@Saurabh Khanduja : That's

zac_adm @ 3 Feb 2011 11:07 PM

@Saurabh Khanduja : That's what the problem statement says.

@Ankit: I am also getting

gvnavin @ 4 Feb 2011 12:05 PM

@Ankit: I am also getting wrong answer for the test what you told. can you help me out.

Thanks.

If we can solve (and have to)

shankysodhi @ 4 Feb 2011 11:14 PM

If we can solve (and have to) all the test cases in 3 rounds then why is admin using

1 2 1 2 3 4 4 3 3 2 as an output...... isnt it misleading .....

also in the later section this solution is given score 4.

So should we aim at higher round ....

Please make things clear.

The problem statement doesn't

triplem @ 5 Feb 2011 01:47 AM

The problem statement doesn't say you have to use three rounds, it just says it is possible in three rounds.

@admin: Are  1 2 1 2 3 2 1 3

poker face @ 5 Feb 2011 01:51 AM

@admin: Are  1 2 1 2 3 2 1 3 3 2 for II case and 1 2 1 for III case valid solutions?

why is the problem called

einstein10 @ 5 Feb 2011 01:54 AM

why is the problem called coloring colorable graphs?

why is admin not replying to

sperm_maker @ 5 Feb 2011 08:17 PM

why is admin not replying to above asked questions??

i m also getting wrong but supposed to be correct solutions for 2nd & 3rd case.

plz do reply

There is nothing wrong with

triplem @ 6 Feb 2011 12:49 AM

There is nothing wrong with the judge, and the problem statement is quite clear. If you are getting WA you are making a mistake and you won't get special help.

> No pair of dishes will

burdakovd @ 6 Feb 2011 04:03 PM

> No pair of dishes will appear more than once in the input.

Does it mean that if "u v" appeared then "v u" will not appear?


@ Burdakov Yes. If "u v"

zac_adm @ 7 Feb 2011 08:14 AM

@ Burdakov

Yes. If "u v" appears in the input then "v u" will not appear.

 

@ Others

Your code will be accepted as long as it conforms to the output specification. Wrong answer means that your solution violates the output specification. If your solution is accepted, then it will receive a score based on the scoring mechanism specified in the problem statement. This is the standard way these tie breaking problems are run.

FYI, I usually do not respond to clarifications if their answer is obvious from the problem statement.

I created valid output that

richard_lee @ 8 Feb 2011 02:26 AM

I created valid output that may not be accepted by codechef:

3 2 1 1

1 2 1 2 3 3 3 2 1 1

1 2 1

2 1 3 3

1 2 1 2 3 3 3 2 1 1

2 1 2

 

@ Richard What do you mean

zac_adm @ 8 Feb 2011 11:35 PM

@ Richard

What do you mean "may not be accepted by codechef"? Can you please clarify?

please for the second test

seddik @ 10 Feb 2011 01:40 AM

please for the second test case is:

1212321322 is a valid answer ?!

@adminsContest is not ended,

burdakovd @ 10 Feb 2011 05:22 PM

@admins

Contest is not ended, so solutions are not public now, it is OK.

But when someone makes a comment on his own solution (for example with brief explanation of algorithm, or some tips for future readers), he expects that comment will also be public only after end of the contest.

But in fact these comments (at least partially) are published at "RECENT COMMENTS" section of http://www.codechef.com/FEB11/ during live contest.

Proof:

05:11 PM Feb 10th: Burdakov Daniel commented onBurdakov Daniel's solution to Coloring Colorable Graphs: test
02:01 PM Feb 10th: Arpit commented on Arpit's solution to Coloring Colorable Graphs:   #include<stdio.h> int a[10006][2]; int b[510]; int main() { int...

It didn't make any harm yet, but you shouldn't publish comments for non-public solutions.

I have solved the problem

gunjanbansal @ 10 Feb 2011 10:19 PM

I have solved the problem though.

But whats the score here means ??

I dint get it .. got a correct answer with a probable low score.. Does it change the rankings etc

And i got just 0.324 points

gunjanbansal @ 10 Feb 2011 10:34 PM

And i got just 0.324 points even when the time shows as 3.19 Sec and 3.1 MB memory. Am i missing something.. .Or is the scoring here is required. And 0.008 for a 0.82 sec solution (i cant tell the thing during contest :() . Whats this exactly means ??

Ok i got it from Jan contest

gunjanbansal @ 10 Feb 2011 10:49 PM

Ok i got it from Jan contest tie breaker. It would be worth mentioning that lower the score the more points u get.

i am getting 1 2 1 1 2 2 1 1

ankit_kumar @ 10 Feb 2011 11:29 PM

i am getting

1 2 1 1 2 2 1 1 1 1
1 2 1

for second and third case...

whats wrong??

Is point obtained is

akash_d_learner @ 11 Feb 2011 03:49 AM

Is point obtained is dependend only upon the score obtained in each test cases or it includes time attribute also.

Just the score.

triplem @ 11 Feb 2011 05:12 AM

Just the score.

@Burdakov Daniel - Yes you

admin @ 13 Feb 2011 01:29 AM

@Burdakov Daniel - Yes you are right. Thanks for bringing this to our notice. We shall certainly be looking into this.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions