English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## 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.
[samples]
[{"iden":"statement","content":"Vasya 有一个包含有向边（定向）和无向边（非定向）的图。两个顶点之间可能存在多条边。\n\nVasya 从图中选取了一个顶点 #cf_span[s]。现在 Vasya 希望制定两个独立的方案：\n\n在两个方案中，每条无向边都必须被赋予一个方向，且两条方案中同一条无向边的方向可以不同。\n\n请帮助 Vasya 找到这两个方案。\n\n第一行包含三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[s]（#cf_span[2 ≤ n ≤ 3·105]，#cf_span[1 ≤ m ≤ 3·105]，#cf_span[1 ≤ s ≤ n]）——图中顶点数、边数，以及 Vasya 选取的顶点。\n\n接下来的 #cf_span[m] 行描述图的边。每行包含三个整数 #cf_span[ti]、#cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ti ≤ 2]，#cf_span[1 ≤ ui, vi ≤ n]，#cf_span[ui ≠ vi]）——边的类型和连接的两个顶点。若 #cf_span[ti = 1]，则该边为有向边，从顶点 #cf_span[ui] 指向顶点 #cf_span[vi]；若 #cf_span[ti = 2]，则该边为无向边，连接顶点 #cf_span[ui] 和 #cf_span[vi]。\n\n保证图中至少存在一条无向边。\n\n前两行应描述使可达顶点数最大化的方案；第三、四行应描述使可达顶点数最小化的方案。\n\n每个方案的描述应以一行开始，包含可达顶点的数量；接下来一行应包含 #cf_span[f] 个符号 '_+_' 和 '_-_'，其中 #cf_span[f] 是初始图中无向边的数量。若输入中的第 #cf_span[j] 条无向边 #cf_span[(u, v)] 应被定向为从 #cf_span[u] 到 #cf_span[v]，则输出 '_+_'；若应被定向为从 #cf_span[v] 到 #cf_span[u]，则输出 '_-_'。无向边的编号顺序与输入顺序一致。\n\n若有多种解，输出任意一种即可。\n\n"},{"iden":"input","content":"第一行包含三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[s]（#cf_span[2 ≤ n ≤ 3·105]，#cf_span[1 ≤ m ≤ 3·105]，#cf_span[1 ≤ s ≤ n]）——图中顶点数、边数，以及 Vasya 选取的顶点。接下来的 #cf_span[m] 行描述图的边。每行包含三个整数 #cf_span[ti]、#cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ti ≤ 2]，#cf_span[1 ≤ ui, vi ≤ n]，#cf_span[ui ≠ vi]）——边的类型和连接的两个顶点。若 #cf_span[ti = 1]，则该边为有向边，从顶点 #cf_span[ui] 指向顶点 #cf_span[vi]；若 #cf_span[ti = 2]，则该边为无向边，连接顶点 #cf_span[ui] 和 #cf_span[vi]。保证图中至少存在一条无向边。"},{"iden":"output","content":"前两行应描述使可达顶点数最大化的方案；第三、四行应描述使可达顶点数最小化的方案。每个方案的描述应以一行开始，包含可达顶点的数量；接下来一行应包含 #cf_span[f] 个符号 '_+_' 和 '_-_'，其中 #cf_span[f] 是初始图中无向边的数量。若输入中的第 #cf_span[j] 条无向边 #cf_span[(u, v)] 应被定向为从 #cf_span[u] 到 #cf_span[v]，则输出 '_+_'；若应被定向为从 #cf_span[v] 到 #cf_span[u]，则输出 '_-_'。无向边的编号顺序与输入顺序一致。若有多种解，输出任意一种即可。"},{"iden":"examples","content":"输入\n2 2 1\n1 1 2\n2 2 1\n输出\n2\n-\n2\n+\n\n输入\n6 6 3\n2 2 6\n1 4 5\n2 3 4\n1 4 1\n1 3 1\n2 2 3\n输出\n6\n++-\n2\n+-+"}]}
**Definitions**
Let $ G = (V, E) $ be a mixed graph with:
- $ V = \{1, 2, \dots, n\} $: set of vertices,
- $ E = E_d \cup E_u $: set of edges, partitioned into
- $ E_d $: directed edges (type 1), each $ (u, v) \in E_d $ is fixed from $ u $ to $ v $,
- $ E_u $: undirected edges (type 2), each $ \{u, v\} \in E_u $ can be oriented in either direction.
Let $ s \in V $ be the source vertex.
Let $ f = |E_u| $, and denote the undirected edges as $ e_1, e_2, \dots, e_f $ in input order.
**Constraints**
1. $ 2 \le n \le 3 \cdot 10^5 $
2. $ 1 \le m \le 3 \cdot 10^5 $
3. $ 1 \le s \le n $
4. Each undirected edge $ e_j = \{u_j, v_j\} $ has $ u_j \ne v_j $
5. $ f \ge 1 $
**Objective**
Find two orientations $ O^+ $ and $ O^- $ of $ E_u $ such that:
- **Maximization Plan**:
- Orient each $ e_j = \{u_j, v_j\} $ as $ u_j \to v_j $ if symbol is `+`, else $ v_j \to u_j $.
- Maximize $ R^+ = |\{ v \in V \mid \text{there exists a directed path from } s \text{ to } v \text{ in } G(O^+) \}| $.
- Output: $ R^+ $ and a string $ S^+ \in \{+, -\}^f $, where $ S^+[j] $ is the orientation of $ e_j $.
- **Minimization Plan**:
- Similarly, orient $ E_u $ to minimize $ R^- = |\{ v \in V \mid \text{there exists a directed path from } s \text{ to } v \text{ in } G(O^-) \}| $.
- Output: $ R^- $ and a string $ S^- \in \{+, -\}^f $, where $ S^-[j] $ is the orientation of $ e_j $.
**Note**: Directed edges $ E_d $ remain fixed.
API Response (JSON)
{
"problem": {
"name": "G. Orientation of Edges",
"description": {
"content": "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 Va",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF883G"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Vasya has a graph containing both directed (oriented) and undirected (non-oriented) edges. There can be multiple edges between a pair of vertices.\n\nVasya has picked a vertex _s_ from the graph. Now Va...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"Vasya 有一个包含有向边（定向）和无向边（非定向）的图。两个顶点之间可能存在多条边。\\n\\nVasya 从图中选取了一个顶点 #cf_span[s]。现在 Vasya 希望制定两个独立的方案：\\n\\n在两个方案中，每条无向边都必须被赋予一个方向，且两条方案中同一条无向边的方向可以不同。\\n\\n请帮助 Vasya 找到这两个方案。\\...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ G = (V, E) $ be a mixed graph with: \n- $ V = \\{1, 2, \\dots, n\\} $: set of vertices, \n- $ E = E_d \\cup E_u $: set of edges, partitioned into \n - $ E_d $: directed edges (typ...",
"is_translate": false,
"language": "Formal"
}
]
}