Problem:


Score : 1600 points

Problem Statement

A balancing network is an abstract device built up of N wires, thought of as running from left to right,
and M balancers that connect pairs of wires. The wires are numbered from 1 to N from top to bottom,
and the balancers are numbered from 1 to M from left to right.
Balancer i connects wires x_i and y_i (x_i < y_i).

Each balancer must be in one of two states: up or down.

Consider a token that starts moving to the right along some wire at a point to the left of all balancers.
During the process, the token passes through each balancer exactly once.
Whenever the token encounters balancer i, the following happens:

If the token is moving along wire x_i and balancer i is in the down state, the token moves down to wire y_i and continues moving to the right.

If the token is moving along wire y_i and balancer i is in the up state, the token moves up to wire x_i and continues moving to the right.

Otherwise, the token doesn't change the wire it's moving along.

Let a state of the balancing network be a string of length M, describing the states of all balancers.
The i-th character is ^ if balancer i is in the up state, and v if balancer i is in the down state.

A state of the balancing network is called uniforming if a wire w exists such that, regardless of the starting wire,
the token will always end up at wire w and run to infinity along it. Any other state is called non-uniforming.

You are given an integer T (1 \le T \le 2). Answer the following question:

If T = 1, find any uniforming state of the network or determine that it doesn't exist.

If T = 2, find any non-uniforming state of the network or determine that it doesn't exist.

Note that if you answer just one kind of questions correctly, you can get partial score.

Constraints

2 \leq N \leq 50000

1 \leq M \leq 100000

1 \leq T \leq 2

1 \leq x_i < y_i \leq N

All input values are integers.

Partial Score

800 points will be awarded for passing the testset satisfying T = 1.

800 points will be awarded for passing the testset satisfying T = 2.

Input

Input is given from Standard Input in the following format:

N M T
x_1 y_1
x_2 y_2
:
x_M y_M

Output

Print any uniforming state of the given network if T = 1, or any non-uniforming state if T = 2. If the required state doesn't exist, output -1.

Sample Input 1

4 5 1
1 3
2 4
1 2
3 4
2 3

Sample Output 1

^^^^^

This state is uniforming: regardless of the starting wire, the token ends up at wire 1.

Sample Input 2

4 5 2
1 3
2 4
1 2
3 4
2 3

Sample Output 2

v^^^^

This state is non-uniforming: depending on the starting wire, the token might end up at wire 1 or wire 2.

Sample Input 3

3 1 1
1 2

Sample Output 3

-1

A uniforming state doesn't exist.

Sample Input 4

2 1 2
1 2

Sample Output 4

-1

A non-uniforming state doesn't exist.



Sample input:
4 5 1
1 3
2 4
1 2
3 4
2 3


Sample output:
^^^^^

Submission status: Runtime Error

Solution code:
N, M, T = list(map(int,input().split()))
xy = [list(map(int,input().split())) for _ in range(M)]

UP = "^"
DW = "v"

if T == 1:
  x = 10 / 0

else:
  if N == 2:
    print(-1)

  L = [""] * M
  
  D = []
  for i in range(M):
    x, y = xy[i]
    if x <= 3 and y <= 3:
      D.append([i, x, y])
    else:
      L[i] = UP
    
  i = 0
  while i < len(D):
    T = []
    n, x, y = D[i]
    T.append(n)
    j = i + 1
    while j < len(D):
      n, xx, yy = D[j]
      if x == xx and y == yy:
        T.append(n)
        j += 1
      else:
        if x == xx:
          for k in T:
            L[k] = DW
        elif y == yy:
          for k in T:
            L[k] = UP
        elif x == yy:
          for k in T:
            L[k] = DW
        elif xx == y:
          for k in T:
            L[k] = UP
        i = j
        break
    else:
      break
  for k in T:
    L[k] = UP
  print("".join(L))

Submission status: Runtime Error

Solution code:
def join(xs, N):
    n = len(xs)
    r = ""
    s = 0
    for i, x in enumerate(xs):
        x = x.strip()
        t = len(x.split())
        S,E="."*s,"."*(N-t-s)
        for l in x.split():
            r+=S+l+E+"\n"
        s += t
    return r
s7="""
.bc.a..
.bc.a..
..aabba
aab...a
x.baa..
x..b.aa
aa.b.xx
"""
s6="""
..aabx
d...bx
dla...
.lab..
xx.bxx
ddaall"""
s5="""
aa.bx
d..bx
dee.a
i.rra
ijjxx
"""
s4="""
xyzz
xyrr
zzxy
rrxy"""
s3="""
jj.
..j
..j"""

s=[s4,s5,s6,s7]
N=int(input())
if N<3:
    print(-1)
elif N==3:
    print(s3.strip())
elif N<=7:
    print(s[N-4].strip())
else:
    print(join([s[0]]*(N//4-1)+[s[N%4]],N))

Submission status: Runtime Error

Solution code:
n,m,t = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(m)]
now = [0] + [1] * n
goal = [i for i in range(n+1)]
ans = ""
assert t == 2
if n == 2:
  print(-1)
  exit()
for x,y in reversed(xy):
  if now[goal[x]] >= 2:
    ans = "v" + ans
    now[goal[x]] -= 1
    now[goal[y]] += 1
    goal[x] = goal[y]
  else:
    ans = "^" + ans
    now[goal[x]] += 1
    now[goal[y]] -= 1
    goal[y] = goal[x]
print(ans)

Submission status: Runtime Error

Solution code:
n,m,t = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(m)]
now = [0] + [1] * n
goal = [i for i in range(n+1)]
ans = ""
assert n == 2
if n == 2:
  print(-1)
  exit()
for x,y in reversed(xy):
  if now[goal[x]] >= 2:
    ans = "v" + ans
    now[goal[x]] -= 1
    now[goal[y]] += 1
    goal[x] = goal[y]
  else:
    ans = "^" + ans
    now[goal[x]] += 1
    now[goal[y]] -= 1
    goal[y] = goal[x]
print(ans)

Submission status: Runtime Error

Solution code:
n,m,t = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(m)]
now = [0] + [1] * n
goal = [i for i in range(n+1)]
ans = ""
assert n == 2
if n == 2:
  print(-1)
  exit()
for x,y in reversed(xy):
  if now[goal[x]] >= 2:
    ans = "v" + ans
    now[goal[x]] -= 1
    now[goal[y]] += 1
    goal[x] = goal[y]
  else:
    ans = "^" + ans
    now[goal[x]] += 1
    now[goal[y]] -= 1
    goal[y] = goal[x]
print(goal)

Submission status: Runtime Error

Solution code:
N, M, T = map(int, input().split())
if T == 1: exit()
X = []
for _ in range(M):
    x, y = map(int, input().split())
    X.append((x-1, y-1))
X.append((0, 1))
if N == 2:
    print(-1)
    exit()

A = [1] * N
I = [i for i in range(M+1)]
j = -1
k = N
ANS = [] # 0:^ 1:v
for i in range(M):
    j += 1
    x, y = X[i]
    if k > 3:
        ANS.append(0)
        if A[y]: k -= 1
        A[x] += A[y]
        A[y] = 0
        if k == 3:
            L = [i for i in range(N) if A[i]]
            a, b, c = L
            for l in range(M-1)[::-1]:
                if X[l][0] in L and X[l][1] in L:
                    I[l] = l
                else:
                    I[l] = I[l+1]
        continue
    if x in X[I[i+1]]:
        ANS.append(1)
    else:
        ANS.append(0)

print("".join(["^" if a == 0 else "v" for a in ANS]))

Submission status: Runtime Error

Solution code:
N, M, T = map(int, input().split())
if T == 1: print(1//0)
X = []
for _ in range(M):
    x, y = map(int, input().split())
    X.append((x-1, y-1))
X.append((0, 1))
if N == 2:
    print(-1)
    exit()

A = [1] * N
I = [i for i in range(M+1)]
j = -1
k = N
ANS = [] # 0:^ 1:v
for i in range(M):
    j += 1
    x, y = X[i]
    if k > 3:
        ANS.append(0)
        if A[y]: k -= 1
        A[x] += A[y]
        A[y] = 0
        if k == 3:
            L = [i for i in range(N) if A[i]]
            a, b, c = L
            for l in range(M-1)[::-1]:
                if X[l][0] in L and X[l][1] in L:
                    I[l] = l
                else:
                    I[l] = I[l+1]
        continue
    if x in X[I[i+1]]:
        ANS.append(0)
    else:
        ANS.append(1)

print("".join(["^" if a == 0 else "v" for a in ANS]))

Submission status: Runtime Error

Solution code:



from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))


def main():
    n,m,t = mi()
    x = []
    y = []
    ansl = [0 for i in range(n+1)]
    for i in range(m):
        tmpl = li()
        xtmp,ytmp = min(tmpl),max(tmpl)
        x.append(xtmp)
        y.append(ytmp)
    if t == 2:
        print(-1)



    ans = ""
    tmp = [x[-1],y[-1]]
    del x[-1]
    del y[-1]

    ansl[tmp[0]] = 1
    ansl[tmp[1]] = 1
    ans+= '^'

    for i in range(m):
        tmp = [x[-1],y[-1]]
        del x[-1]
        del y[-1]
        flag = True
        if ansl[tmp[0]] == 1:
            ans = 'v'+ans
            ansl[tmp[1]] = 1
            flag = False
        elif ansl[tmp[1]] ==1:
            ans = '^'+ans
            ansl[tmp[0]] = 1
            flag = False
        
        if flag:
            print(-1)
            exit()
        
    for i in range(1,n+1):
        if ansl[i] == 0:
            print(-1)
            exit()

    print(ans)



    


    
main()

Submission status: Runtime Error

Solution code:
N, M, T = map(int, input().split())
if T == 1: print(1//0)
X = []
for _ in range(M):
    x, y = map(int, input().split())
    X.append((x-1, y-1))
X.append((0, 1))
if N == 2:
    print(-1)
    exit()

A = [1] * N
I = [i for i in range(M+1)]
j = -1
k = N
ANS = [] # 0:^ 1:v
for i in range(M):
    j += 1
    x, y = X[i]
    if k > 3:
        ANS.append(0)
        if A[y]: k -= 1
        A[x] += A[y]
        A[y] = 0
        if k == 3:
            L = [i for i in range(N) if A[i]]
            a, b, c = L
            for l in range(M-1)[::-1]:
                if X[l][0] in L and X[l][1] in L:
                    I[l] = l
                else:
                    I[l] = I[l+1]
        continue
    if x in X[I[i+1]]:
        ANS.append(1)
    else:
        ANS.append(0)

print("".join(["^" if a == 0 else "v" for a in ANS]))

Submission status: Runtime Error

Solution code:
n,m,t = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
vstble = [0]*(n+1)
visited = [0]*(n+1)
visited[0] = 1
for i in range(n):
    x = xy[i][0]
    y = xy[i][1]
    graph[x].append(y)
    graph[y].append(x)
stack = [1]
while stack:
    s = stack.pop()
    visited[s] = 1
    for t in graph[s]:
        if visited[t] == 0:
            stack.append(t)
if min(visited) == 0:
    print(-1)
    exit()
ans = []
for i in range(m-1,-1,-1):
    x = xy[i][0]
    y = xy[i][1]
    if vstble[x] == vstble[y] == 0:
        ans.append("^")
        vstble[x] = 1
        vstble[y] = 1      
    elif vstble[x] == 0 and vstble[y] == 1:
        ans.append("v")
        vstble[x] = 1
    elif vstble[x] == 1 and vstble[y] == 0:
        ans.append("^")
        vstble[y] = 1
    else:
        ans.append("^")
ans = ans[::-1]
print(*ans,sep = "")

Submission status: Runtime Error

Solution code:
N,M,T = map(int, input().split())
L = [[int(l) for l in input().split()] for _ in range(M)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
                
    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]

if T == 1:
    uf = UnionFind(N)
    for i in range(M):
        uf.unite(L[i][0]-1, L[i][1]-1)
    
    ans = 0
    for i in range(N):
        if uf.isSameGroup(0, i):
            continue
        ans = -1
        break
    
    if ans == 0:
        uf2 = UnionFind(N)
        X = L[-1][0]-1
        ans = [0]*M
        for i in range(M-1, -1, -1):
            if L[i][0]-1 == X:
                ans[i] = "^"
                uf2.unite(X, L[i][1]-1)
            elif L[i][1] == X:
                ans[i] = "v"
                uf2.unite(X, L[i][0]-1)
            elif uf2.isSameGroup(X, L[i][0]-1):
                ans[i] = "^"
                uf2.unite(X, L[i][1]-1)
            elif uf2.isSameGroup(X, L[i][1]-1):
                ans[i] = "v"
                uf2.unite(X, L[i][0]-1)
            
        print("".join(ans))
    else:
        print(ans)
else:
    print(-2)

Submission status: Runtime Error

Solution code:
N,M,T = map(int, input().split())
L = [[int(l) for l in input().split()] for _ in range(M)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
                
    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]

uf = UnionFind(N)
for i in range(M):
    uf.unite(L[i][0], L[i][1])
    
ans = 0
for i in range(1, N+1):
    if uf.isSameGroup(1, i):
        continue
    ans = -1
    break
    
if ans == 0:
    uf2 = UnionFind(N)
    X = L[-1][0]
    ans = [0]*M
    for i in range(M-1, -1, -1):
        if L[i][0] == X:
            ans[i] = "^"
            uf2.unite(X, L[i][1])
        elif L[i][1] == X:
            ans[i] = "v"
            uf2.unite(X, L[i][0])
        elif uf2.isSameGroup(X, L[i][0]):
            ans[i] = "^"
            uf2.unite(X, L[i][1])
        elif uf2.isSameGroup(X, L[i][1]):
            ans[i] = "v"
            uf2.unite(X, L[i][0])
            
    print("".join(ans))
else:
    print(ans)