← 返回题目列表

Codeforces · 883/G

G. 边缘方向

中文机器翻译题面 查看原题

Vasya 有一个包含有向(有向)边和无向(无向)边的图。一对顶点之间可以有多条边。

Vasya 从图中选取了一个顶点 s。现在 Vasya 想要创建两个单独的计划:

1. 将每个无向边定向在两个可能方向之一上,以最大化从顶点 s 可到达的顶点数量;
2. 将每个无向边定向在两个可能方向之一上,以最小化从顶点 s 可到达的顶点数量。

在两个计划的每一个中,每个无向边必须变为有向。对于边缘,选择的方向在两个计划中可以不同。

帮助 Vasya 找到计划。

输入

第一行包含三个整数 n、m 和 s (2 ≤ n ≤ 3·105, 1 ≤ m ≤ 3·105, 1 ≤ s ≤ n) — 图中顶点和边的数量,以及 Vasya 选取的顶点。

以下 m 行包含有关图边的信息。每行包含三个整数 ti、ui 和 vi (1 ≤ ti ≤ 2, 1 ≤ ui, vi ≤ n, ui ≠ vi) — 边类型和边连接的顶点。如果 ti = 1,则边是有向的,从顶点 ui 到顶点 vi。如果 ti = 2,则边是无向的,它连接顶点 ui 和 vi。

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

输出

前两行应描述最大化可到达顶点数量的计划。第三行和第四行应该描述最小化可到达顶点数量的计划。

每个计划的描述应以包含可到达顶点数的行开始。计划的第二行应由 f 个符号“+”和“-”组成,其中 f 是初始图中无向边的数量。如果输入中的第 j 个无向边 (u, v) 应从 u 到 v,则打印“+”作为字符串的第 j 个符号。打印“-”表示相反方向(从 v 到 u)。考虑无向边按照输入中给出的顺序进行编号。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #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
+-+