Balancing Network Revisited

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/FEB20/hindi/BALNET.pdf), [Bengali](http://www.codechef.com/download/translated/FEB20/bengali/BALNET.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/FEB20/mandarin/BALNET.pdf), [Russian](http://www.codechef.com/download/translated/FEB20/russian/BALNET.pdf), and [Vietnamese](http://www.codechef.com/download/translated/FEB20/vietnamese/BALNET.pdf) as well. Consider $N$ parallel wires running from left to right. The wires are numbered $1$ through $N$ from top to bottom. There are $M$ devices called *balancers*, numbered $1$ through $M$ from left to right. For each valid $i$, balancer $i$ connects wires $x_i$ and $y_i$ ($x_i \lt y_i$). Let's call such a structure of wires and balancers a *balancing network*. Each balancer can be directed either upwards or downwards. The directions of all balancers define the state of the balancing network. Consider a token that starts moving to the right along some wire, from a point on that wire which is to the left of all balancers. During this process, the token encounters each balancer exactly once. Whenever the token encounters a balancer $i$, the following happens:  if the token is moving along the wire $x_i$ and balancer $i$ is directed downwards, the token moves down to the wire $y_i$  otherwise, if the token is moving along the wire $y_i$ and balancer $i$ is directed upwards, the token moves up to the wire $x_i$  in all other cases, the token does not move to a different wire  afterwards, the token keeps moving to the right We say that a state of the balancing network:  *transforms* a wire $i$ into a wire $j$, if a token that starts moving along the wire $i$ ends up on the wire $j$ after passing through all $M$ balancers  *unifies* wires $i$ and $j$, if it transforms both of these wires into the same wire (possibly different from each of them)  is $k$*nonunifying*, if there is a set of $k$ distinct wires such that this state does not unify any pair of wires from this set For a given balancing network, please find any $\left\lceil \frac{N}{2} \right\rceil$nonunifying state or determine that there is no such state. ### 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$.  $M$ lines follow. For each $i$ ($1 \le i \le M$), the $i$th of these lines contains two spaceseparated integers $x_i$ and $y_i$. ### Output For each test case:  If there is no $\left\lceil \frac{N}{2} \right\rceil$nonunifying state for the given balancing network, print a single line containing the string `"failure"` (without quotes).  Otherwise, print a single line containing a string with length $M$. This string should describe some $\left\lceil \frac{N}{2} \right\rceil$nonunifying state. For each valid $i$, its $i$th character should be either '^' if the $i$th balancer is directed upwards or 'v' if the $i$th balancer is directed downwards. ### Constraints  $1 \le T \le 10^3$  $2 \le N \le 10^6$  $1 \le M \le 10^6$  $1 \le x_i \lt y_i \le N$ for each valid $i$  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 (7 points):** $M \le 10$ **Subtask #2 (14 points):**  $N \le 10$  $M \le 10^3$  the sum of $M$ over all test cases does not exceed $10^4$ **Subtask #3 (29 points):** $N, M \le 100$ **Subtask #4 (50 points):** original constraints ### Example Input ``` 2 3 3 1 2 2 3 1 3 5 6 1 2 3 4 1 3 2 4 2 3 1 4 ``` ### Example Output ``` ^^^ v^vv^v ``` ### Explanation **Example case 1:** The state where all balancers are directed upwards ("^^^") transforms wire $1$ into itself, wire $2$ into wire $1$ and wire $3$ into wire $2$. We can see that this state does not unify wires $1$ and $3$ (or wires $2$ and $3$), thus it is $2$nonunifying. Another $2$nonunifying state of this balancing network is "^^v". The remaining $6$ states are not $2$nonunifying. **Example case 2:**Author:  alex_2oo8 
Editorial  https://discuss.codechef.com/problems/BALNET 
Tags  alex_2oo8, feb20, hard, observations, tmwilliamlin 
Date Added:  7012020 
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. 