← 返回题目列表

AtCoder · agc041_e

E. 平衡网络

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

分数: 1600 点

问题陈述

A 平衡网络 是一个抽象设备,由以下组成 N 电线,被认为是从左到右运行, 和 M 平衡器 连接成对的电线。电线编号为 1 to N 从上到下, 平衡器编号为 1 to M 从左到右。 平衡器 i 连接电线 x_i 和 y_i (x_i < y_i).

pic1-small-2acea94b.png

每个平衡器必须处于以下两种状态之一: up or 向下.

考虑一个令牌在所有平衡器左侧的某个点开始沿着某些电线向右移动。 在此过程中,代币仅通过每个平衡器一次。 每当令牌遇到平衡器时 i,会发生以下情况:

  • 如果令牌沿着电线移动 x_i 和平衡器 i 处于向下状态,代币向下移动以进行连线 y_i 并继续向右移动。
  • 如果令牌沿着电线移动 y_i 和平衡器 i 处于向上状态,代币向上移动至线 x_i 并继续向右移动。
  • 否则,令牌不会改变其移动的线路。

设平衡网络的状态为一个长度的字符串 M,描述所有平衡器的状态。 的 i- 第一个字符是 ^ 如果平衡器 i 处于向上状态,并且 v 如果平衡器 i 处于关闭状态。

平衡网络的状态称为 制服 如果一根电线 w 的存在使得,无论起始线如何, 令牌将始终以电汇结束 w 并沿着它跑到无穷远。任何其他状态都称为 不均匀.

给你一个整数 T (1 \le T \le 2)。回答以下问题:

  • If T = 1,查找网络的任何统一状态或确定它不存在。
  • If T = 2,找到任何不均匀的网络状态或确定它不存在。

请注意,如果您仅正确回答一种问题,您可以获得部分分数。

约束

  • 2 \leq N \leq 50000
  • 1 \leq M \leq 100000
  • 1 \leq T \leq 2
  • 1 \leq x_i < y_i \leq N
  • 所有输入值均为整数。

部分分数 通过满足以下条件的测试集将获得

  • 800 通过满足以下条件的测试集将获得积分 T = 1.
  • 800 通过满足以下条件的测试集将获得积分 T = 2.

输入

输入由标准输入按以下格式给出:

N M T
x_1 y_1
x_2 y_2
:
x_M y_M

输出

打印给定网络的任何统一状态,如果 T = 1,或任何非均匀状态,如果 T = 2。如果所需的状态不存在,则输出 -1.


样本输入 1

4 5 1
1 3
2 4
1 2
3 4
2 3

示例输出 1

^^^^^

这种状态是统一的:无论起始线如何,令牌都以线结束 1.

pic2-small-2acea94b.png

示例输入 2

4 5 2
1 3
2 4
1 2
3 4
2 3

示例输出 2

v^^^^

此状态是不一致的:根据起始线路,令牌可能最终出现在线路上 1 或电线 2.

pic3final-small-2acea94b.png

示例输入 3

3 1 1
1 2

示例输出 3

-1

不存在统一状态。


示例输入 4

2 1 2
1 2

示例输出 4

-1

不存在不均匀状态。