**Problem Link:** contest, practice

**Difficulty:** Easy-Medium

**Pre-requisites:** DFS, BFS, Bipartite Graphs, Graph Traversal

**Problem:**

Given a graph **G** with non-negative values **Y _{j}** assigned to the edges.

Your task is to find the **K**’th lexicographically valid sequence (**X _{1}**,

**X**, …,

_{2}**X**) that satisfies to the following condition:

_{N}Let’s suppose that the **j**’th edge of **G** connects vertices **U _{j}** and

**V**. Then, a non-negative integer

_{j}**Y**equals to

_{j}**X**.

_{Uj}xor X_{Vj}**Explanation:**

Let’s assume, that all the values of **X _{i}** and

**Y**belong to {0, 1}. If it’s not true, then we can consider all the bits seperately(since we are working with

_{j}**XOR**operation) and reduce the problem to the case, when all the values of

**X**and

_{i}**Y**belong to {0, 1}. Let’s also assume, that

_{j}**G**is connected(otherwise, we can solve the problem in each connected component seperately).

Let’s consider some valid sequence (**X _{1}**,

**X**, …,

_{2}**X**). The given graph

_{N}**G**is bipartite and divided into two parts: if

**X**= 0, then

_{i}**i**’th vertex of

**G**belongs to the first part of

**G**, otherwise it belongs to the second part.

What about edges? Let’s suppose that the **j**’th edge of **G** connects vertices **U _{j}** and

**V**. Then, if

_{j}**Y**= 0, then

_{j}**U**and

_{j}**V**belong to the same part of

_{j}**G**, otherwise they belong to different parts. It means, that if we know the value

**X**, then

_{Uj}**X**.

_{Vj}= X_{Uj}xor Y_{j}So, let’s build up an algorithm of finding the least lexicographically valid sequence (**X _{1}**,

**X**, …,

_{2}**X**):

_{N}- Assigning
**X**= 0;_{1} - Starting BFS(or DFS) from the first vertex;
- Calculating the values of
**X**while moving along the edges(_{i}**X**)._{connected with known}= X_{known}xor Y_{the edge between the current vertices}

If we have faced some contradictions during the algorithm(i.e. **X _{V}** should be both 0 and 1 for some vertex

**V**), then there is no valid sequence (

**X**,

_{1}**X**, …,

_{2}**X**) at all, otherwise it’s found by our algorithm.

_{N}As was said before, we can run this algorithm for every bit of **Y _{j}**’s( there are at most 31 of them ) and then merge the results. It’s important to note, that for different bits there could be different partitions of

**G**(i.e. the same vertex

**V**could belong to the first part of

**G**while processing the first bit of

**Y**’s and belong the second part of

_{j}**G**while processing the second bit of

**Y**’s), but that’s OK since there’s no limits for that.

_{j}Ok, we have just considered an **O( (N + M) × log _{2}Y )** algorithm of finding the least lexicographically valid sequence (

**X**,

_{1}**X**, …,

_{2}**X**), but we can do better.

_{N}Let’s solve the problem for all the bits simultaneously, doing exactly the same algorithm as described above. If we have faced some contradictions during the algorithm(i.e. **X _{V}** should be equal to different values at the same time for some vertex

**V**), then there is no valid sequence (

**X**,

_{1}**X**, …,

_{2}**X**) at all, otherwise the least lexicographically valid sequence of

_{N}**X**’s is found by our algorithm.

That’s nice, but we are asked to find the **K**’th lexicographically valid sequence.

Let’s suppose, that (**X _{1}**,

**X**, …,

_{2}**X**) is the least lexicographically valid sequence of

_{N}**X**’s. Then we can just assign each

**X**=

_{i}**X**and get the

_{i}xor (K - 1)**K**’th lexicographically valid sequence of

**X**’s. This little trick works because

**( X**

_{Uj}xor (K - 1) ) xor ( X_{Vj}xor (K - 1) ) = X_{Uj}xor X_{Vj}= Y_{j}.Let’s denote the minimal vertex of a connected component as a vertex with the minimal index among vertices from the component. If **G** is not connected, then let’s find the least lexicographically valid sequence of **X**’s in every connected component separately. After that, let’s find the **K**’th lexicographically valid sequence in the connected component with the maximal possible minimal vertex. It’s not hard to prove, that it’s the **K**’th lexicographically valid sequence for the whole graph **G**.

The total complexity of the solution is **O(N + M)**.

Please, check out Setter’s and Tester’s solutions for your better understanding.

**Setter’s Solution:** link

**Tester’s Solution:** link