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 +-+