CF883G.Orientation of Edges

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.

瓦西娅有一个图，其中既包含有向边（定向边），也包含无向边（非定向边）。任意两个顶点之间可能存在多条边。

瓦西娅从该图中选定一个顶点 $s$。现在他希望制定两个独立的方案：

1. 将每条无向边定向为两个可能方向之一，使得从顶点 $s$ 可达的顶点数量最大化；
2. 将每条无向边定向为两个可能方向之一，使得从顶点 $s$ 可达的顶点数量最小化。

在上述两个方案中，每条无向边都必须被赋予一个方向（即变为有向边），且同一无向边在两个方案中可被赋予不同方向。

请帮助瓦西娅找出这两个方案。

The first line contains three integers n, m and s (2 ≤ n ≤ 3·105, 1 ≤ m ≤ 3·105, 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.

第一行包含三个整数 $n$、$m$ 和 $s$（$2 \leq n \leq 3\cdot10^5$，$1 \leq m \leq 3\cdot10^5$，$1 \leq s \leq n$）——分别表示图中顶点数、边数以及 Vasya 所选的顶点编号。

接下来的 $m$ 行描述图中的边。每行包含三个整数 $t_i$、$u_i$ 和 $v_i$（$1 \leq t_i \leq 2$，$1 \leq u_i,\,v_i \leq n$，$u_i \neq v_i$）——表示边的类型及该边所连接的两个顶点。若 $t_i = 1$，则该边为有向边，方向从顶点 $u_i$ 指向顶点 $v_i$；若 $t_i = 2$，则该边为无向边，连接顶点 $u_i$ 和 $v_i$。

保证图中至少存在一条无向边。

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.

前两行应描述使可达顶点数最多的方案；第三、四行应描述使可达顶点数最少的方案。

每个方案的描述需以一行开头，该行包含可达顶点的数量。方案的第二行应由 f 个符号 '+' 和 '-' 组成，其中 f 是初始图中无向边的数量。若输入中第 j 条无向边 (u, v) 应被定向为从 u 指向 v，则该字符串的第 j 个符号应为 '+'；若应被定向为从 v 指向 u，则应为 '-'。请按输入中给出的顺序对无向边进行编号。

若存在多个可行解，输出任意一个即可。