Orientation of Edges

题意翻译

Vasya有一个图（没有自环，但是可能有重边），图中既有有向边也有无向边，他选择了图中的一个点$s$ ，并希望你能给无向边定向，构造出两个图： 1. 最大化从$s$ 出发，沿有向边移动能够到达的点数。 2. 最小化从$s$ 出发，沿有向边移动能够到达的点数。 这两个询问互相独立，即任意一条无向边在两个图中可以定不同的方向。 ### 输入格式 第一行三个整数$n,m,s(2\le n\le 3\cdot 10^5,1\le m\le 3\cdot 10^{5},1\le s\le n)$ ，分别表示图的点数，边数，和Vasya选好的点$s$ 。 接下来$m$ 行每行三个整数$t_i,u_i,v_i(1\le t_i\le 2,1\le u_i\neq v_i\le n)$ 描述边，其中$t_i$ 是边$i$ 的类型，$u_i,v_i$ 是边$i$ 的两个端点。 - 若$t_i=1$ ，则第$i$ 条边为有向边，方向是$u_i\to v_i$ 。 - 若$t_i=2$ ，则第$i$ 条边为无向边。 保证图中无向边数量不小于$1$ 。 ### 输出格式 两个询问分别输出两行。 对于每个询问，第一行一个数表示定向后的图中从$s$ 出发沿有向边可以到达多少个点。 接下来一行一个由`+`和`-`构成的字符串$S$ （$|S|$ 为原图中无向边条数），第$j$ 个字符$S_j$ 表示给第$j$ 条无向边$(u,v)$ 的定的方向，`+`表示$u\to v$ ，`-`表示$v\to u$ 。 如果询问有多解，输出任意一解。 翻译贡献者UID：50882

题目描述

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: 1. to orient each undirected edge in one of two possible directions to maximize number of vertices reachable from vertex $ s $ ; 2. 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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

2 2 1
1 1 2
2 2 1

输出样例 #1

2
-
2
+

输入样例 #2

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

输出样例 #2

6
++-
2
+-+