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 space-separated integers $N$ and $M$. - Each of the next $M$ lines contains two space-separated 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$ space-separated 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 self-loops - 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.
|Tags||aa98, easy, graph, graph-theory, oct19, r_64|
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.