Even Edges

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/OCT19/hindi/EVEDG.pdf), [Bengali](http://www.codechef.com/download/translated/OCT19/bengali/EVEDG.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/OCT19/mandarin/EVEDG.pdf), [Russian](http://www.codechef.com/download/translated/OCT19/russian/EVEDG.pdf), and [Vietnamese](http://www.codechef.com/download/translated/OCT19/vietnamese/EVEDG.pdf) as well. Chef has a simple undirected graph with $N$ vertices (numbered $1$ through $N$) and $M$ edges. He wants to divide it into $K$ parts (subgraphs) for some integer $K$. First, Chef divides the vertices in the graph into $K$ sets such that each vertex belongs to exactly one set; the subgraphs and sets are numbered $1$ through $K$ such that for each valid $i$, vertices from the $i$th set belong to the $i$th subgraph. Then, Chef checks all the edges in the graph. For an edge connecting vertices $u$ and $v$, if $u$ and $v$ are both in the $i$th set, then this edge belongs to the $i$th subgraph. Otherwise, this edge does not belong to any of these $K$ subgraphs. At the end, Chef checks these $K$ subgraphs. If each subgraph contains an even number of edges, then Chef thinks that this way of dividing the graph is *delicious*. Chef wants to divide the graph in a delicious way such that $K$ is the smallest possible. Find the minimum $K$ and one such way to divide the graph. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains two spaceseparated integers $N$ and $M$.  Each of the next $M$ lines contains two spaceseparated integers $u$ and $v$ denoting that vertices $u$ and $v$ are connected by an edge. ### Output For each test case, print two lines. The first of these lines should contain a single integer ― the minimum $K$. The second line should contain $N$ spaceseparated integers, where for each valid $i$, the $i$th integer denotes the subgraph that vertex $i$ belongs to. If there are multiple solutions, you may output any one. ### Constraints  $1 \le T \le 3,000$  $1 \le M \le 100,000$  $2 \le N \le 100,000$  $1 \le u \neq v \le N$  the graph contains no duplicate edges or selfloops  the sum of $N$ over all test cases does not exceed $10^6$  the sum of $M$ over all test cases does not exceed $10^6$ ### Subtasks **Subtask #1 (30 pts):** $2 \le N \le 10$ **Subtask #2 (70 pts):** original constraints ### Example Input ``` 1 5 5 1 2 1 3 2 3 2 4 3 4 ``` ### Example Output ``` 2 1 2 1 1 2 ``` ### Explanation **Example case 1:** Subgraph $1$ contains vertices $1$, $3$, $4$ and edges $(1,3)$ and $(3,4)$. Subgraph $2$ contains vertices $2$ and $5$, but no edges.Author:  aa98 
Editorial  https://discuss.codechef.com/problems/EVEDG 
Tags  aa98, easy, graph, graphtheory, oct19, r_64 
Date Added:  29042019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 