All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Mike is given an undirected graph G of N vertices and M edges. A non-negative integer Xi is assigned to the i'th vertex of G, for 1 ≤ i ≤ N.
Mike was asked to assign labels to each edge of the graph so that the following condition is satisfied:
Let's suppose that the j'th edge of G connects vertices Uj and Vj. Then, a non-negative integer Yj equals to XUj xor XVj.
This challenge was too easy for Mike and he solved it quickly.
The next day, Mike started to worry that he had solved the problem too quickly and had made a lot of mistakes, so he decided to double-check his answers. To his horror, Mike discovered that all the values of Xi had been lost!
Mike is a very meticulous person and he doesn't like making mistakes, so he decided to create his own values of Xi that still produce the same values of Yj.
Your task is to determine whether it is possible to do so. If it is, you should output the K'th lexicographically valid sequence (X1, X2, ..., XN) that satisfies the above conditions, knowing the structure of G and all the values Yj.
Maybe some of you aren't familiar with some terms in the statement. Here are some articles that could help you understand the problem correctly:
- XOR operation: http://en.wikipedia.org/wiki/Exclusive_or
Also, the stack memory size is quite limited on CodeChef, so a deep recursion may lead to the Runtime Error verdict.
The first line of the input contains the integers N, M and K.
The next M lines describe the edges of G; the j'th line contains three integers Uj, Vj and Yj.
It's guaranteed that G doesn't contain multiple edges and loops.
If there is no valid labelling, or less than K valid labellings, the only line of the output should contain -1. Otherwise, the only line of the output should contain N non-negative integers, denoting the K'th lexicographically valid sequence (X1, X2, ..., XN).
It's guaranteed that in the correct sequence all of the values of Xi won't exceed the 32-bit signed integer limit.
1 ≤ N ≤ 200,000(2 × 105);
0 ≤ M ≤ 300,000(3 × 105);
1 ≤ K ≤ 1,000,000,000(109);
1 ≤ Uj ≠ Vj ≤ N;
0 ≤ Yj < 231.
Input: 5 4 2 1 2 5 1 3 9 2 4 0 2 5 1 Output: 1 4 8 4 5
The first lexicographically valid sequence is equal to (0, 5, 9, 5, 4);
The second lexicographically valid sequence is equal to (1, 4, 8, 4, 5) - that's the one that should be printed out as the answer.
|Tags||bfs, bipartite, cook52, easy-medium, graphs, kostya_by|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.