Vasya has a graph containing both directed (oriented) and undirected (non-oriented) edges. There can be multiple edges between a pair of vertices.

Vasya has picked a vertex s from the graph. Now Vasya wants to create two separate plans:

  to orient each undirected edge in one of two possible directions to maximize number of vertices reachable from vertex s;  to orient each undirected edge in one of two possible directions to minimize number of vertices reachable from vertex s. 

In each of two plans each undirected edge must become directed. For an edge chosen directions can differ in two plans.

Help Vasya find the plans.


-----Input-----

The first line contains three integers n, m and s (2 ≤ n ≤ 3·10^5, 1 ≤ m ≤ 3·10^5, 1 ≤ s ≤ n) — number of vertices and edges in the graph, and the vertex Vasya has picked.

The following m lines contain information about the graph edges. Each line contains three integers t_{i}, u_{i} and v_{i} (1 ≤ t_{i} ≤ 2, 1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}) — edge type and vertices connected by the edge. If t_{i} = 1 then the edge is directed and goes from the vertex u_{i} to the vertex v_{i}. If t_{i} = 2 then the edge is undirected and it connects the vertices u_{i} and v_{i}.

It is guaranteed that there is at least one undirected edge in the graph.


-----Output-----

The first two lines should describe the plan which maximizes the number of reachable vertices. The lines three and four should describe the plan which minimizes the number of reachable vertices.

A description of each plan should start with a line containing the number of reachable vertices. The second line of a plan should consist of f symbols '+' and '-', where f is the number of undirected edges in the initial graph. Print '+' as the j-th symbol of the string if the j-th undirected edge (u, v) from the input should be oriented from u to v. Print '-' to signify the opposite direction (from v to u). Consider undirected edges to be numbered in the same order they are given in the input.

If there are multiple solutions, print any of them.


-----Examples-----
Input
2 2 1
1 1 2
2 2 1

Output
2
-
2
+

Input
6 6 3
2 2 6
1 4 5
2 3 4
1 4 1
1 3 1
2 2 3

Output
6
++-
2
+-+

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def put():
	return map(int, input().split())

def dfs(x, flag=1):
	(s, vis, ans) = ([x], [0] * n, ['+'] * m)
	vis[x] = 1
	while s:
		i = s.pop()
		for (j, k) in graph[i]:
			if vis[j] == 0:
				if k * flag < 0:
					ans[abs(k) - 1] = '-'
				elif k * flag > 0:
					ans[abs(k) - 1] = '+'
				if flag == 1 or k == 0:
					s.append(j)
					vis[j] = 1
	return (''.join(ans), sum(vis))
(n, m, s) = put()
graph = [[] for i in range(n)]
k = 1
for _ in range(m):
	(z, x, y) = put()
	(x, y) = (x - 1, y - 1)
	if z == 1:
		graph[x].append((y, 0))
	else:
		graph[x].append((y, k))
		graph[y].append((x, -k))
		k += 1
m = k - 1
(x, y) = dfs(s - 1, 1)
print(y)
print(x)
(x, y) = dfs(s - 1, -1)
print(y)
print(x)


import sys
input = sys.stdin.readline

def put():
	return list(map(int, input().split()))

def dfs0(x):
	s = [x]
	vis = [0] * n
	ans = ['+'] * m
	vis[x] = 1
	while s:
		i = s.pop()
		for (j, k) in graph[i]:
			if vis[j] == 0:
				if k < 0:
					ans[-k - 1] = '-'
				elif k > 0:
					ans[k - 1] = '+'
				s.append(j)
				vis[j] = 1
	return (''.join(ans), sum(vis))

def dfs1(x):
	s = [x]
	vis = [0] * n
	ans = ['+'] * m
	vis[x] = 1
	while s:
		i = s.pop()
		for (j, k) in graph[i]:
			if vis[j] == 0:
				if k < 0:
					ans[-k - 1] = '+'
				elif k > 0:
					ans[k - 1] = '-'
				if k == 0:
					s.append(j)
					vis[j] = 1
	return (''.join(ans), sum(vis))
(n, m, s) = put()
graph = [[] for i in range(n)]
k = 1
for _ in range(m):
	(z, x, y) = put()
	(x, y) = (x - 1, y - 1)
	if z == 1:
		graph[x].append((y, 0))
	else:
		graph[x].append((y, k))
		graph[y].append((x, -k))
		k += 1
m = k - 1
(x, y) = dfs0(s - 1)
print(y)
print(x)
(x, y) = dfs1(s - 1)
print(y)
print(x)


from collections import defaultdict
import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(7 * 10 ** 4)

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

@bootstrap
def dfs(u):
	vis[u] = 1
	for j in adj[u]:
		if d[j, u] == 1:
			d1[j, u] = '+'
		if d[u, j] == 1:
			d1[u, j] = '-'
		if d3[u, j]:
			if not vis[j]:
				yield dfs(j)
	yield

@bootstrap
def dfs2(u):
	vis[u] = 1
	for j in adj[u]:
		if not vis[j]:
			if d[j, u] == 1:
				d2[j, u] = '-'
			if d[u, j] == 1:
				d2[u, j] = '+'
			yield dfs2(j)
	yield
(n, m, s) = map(int, input().split())
edges = []
adj = [[] for i in range(n + 1)]
d = defaultdict(lambda : 0)
d3 = defaultdict(lambda : 0)
d1 = defaultdict(lambda : '+')
d2 = defaultdict(lambda : '+')
for j in range(m):
	b = list(map(int, input().split()))
	if b[0] == 1:
		adj[b[1]].append(b[2])
		d3[b[1], b[2]] = 1
	else:
		adj[b[1]].append(b[2])
		adj[b[2]].append(b[1])
		d[b[1], b[2]] = 1
		edges.append([b[1], b[2]])
vis = [0] * (n + 1)
dfs(s)
m1 = vis.count(1)
vis = [0] * (n + 1)
dfs2(s)
m2 = vis.count(1)
res1 = []
res2 = []
for j in edges:
	res1.append(d1[j[0], j[1]])
	res2.append(d2[j[0], j[1]])
print(m2)
print(''.join(res2))
print(m1)
print(''.join(res1))