← 返回题目列表

AtCoder · yahoo_procon2018_final_e

E. 建立网络

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

配点 : 1400 点

問題文

潜伏 我有 1 减去 N 有 N 个顶点的有向图。刚开始时,这个图没有边。 斯努克君的工作是向这个图中添加 M 条边,使任意顶点对 (u,v) 关于 u 减去 v 要沿着边走到达。

添加边时使用长度 M 序列 使用 a,b 。 S努克君 a,b 之后(在a,b 之间不能交换元素),使用这些数列向该图中添加 M 条有向边。

潜伏 我有 i 条边,可以添加以下任一边。

  • 頂点 a_i 减去 b_i 的有向边
  • 頂点 b_i 减去 a_i 的有向边

努克君的工作可以完成吗?如果可以,请举例说明如何添加这样的边。

制約

  • 1 \leq N , M \leq 2 \times 10^{5}
  • 1 \leq a_i, b_i \leq N
  • 给出的所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
a_1 a_2 ... a_{M}
b_1 b_2 ... b_{M}

出力

如果斯奴克君的工作可以完成 Yes ,否则 No 请输出。 如果可以完成,请在接下来的 M 行中按照以下格式输出边的添加方法。

x_1 c_1 y_1
:
x_{M} c_{M} y_{M}

在这里,c_i 是 在 > 如果 x_i 减去 y_i 指向的有向边,c_i 是 在 < 如果 y_i 减去 x_i 添加了有向边。 是重新排列 x,y 分别 以 a,b 的数列,以及任意的顶点对 u,v 关于 u 减去 v 就是正确的。


入力例 1

3 6
1 2 3 1 1 1
3 2 1 1 1 2

出力例 1

Yes
1 > 2
1 < 2
1 > 3
3 > 1
1 < 1
2 > 1
  • 通过构建如下面图所示的图,Suneka君可以完成工作。
  • 请注意,即使最终的图包含多重边或自环也没关系。
    8664ee136a2d143a10b345ef6a18017b.png

入力例 2

3 1
1
2

出力例 2

No
  • 无论如何添加边,努克君都无法完成工作。

入力例 3

13 29
2 8 4 5 5 8 2 9 2 5 9 4 3 8 4 2 12 4 4 12 8 8 3 12 3 9 4 8 9
6 1 1 11 12 6 9 12 6 13 10 11 13 6 10 10 11 3 10 13 10 13 7 7 11 7 11 10 12

出力例 3

Yes
2 > 6
12 < 1
5 > 1
4 > 11
2 < 12
12 < 6
4 < 9
3 > 12
8 < 6
9 > 13
4 < 10
3 < 11
4 < 13
2 < 6
8 > 10
5 > 10
4 < 11
12 < 3
8 < 10
9 < 13
4 > 10
9 < 13
8 > 7
8 < 7
5 < 11
2 < 7
9 < 11
8 < 10
3 > 12